September 2001 - Haskell-Cafe

Re: controlling resource usage
by D. Tweed 11 Sep '01

11 Sep '01

On Fri, 7 Sep 2001, Richard Uhtenwoldt wrote: > Finally, are we all in agreement that it would be a great thing if > someone invented a Haskell-like language as good as Haskell at hiding > resource usage when resource usage is unimportant, but that made it > easier to control resource usage than Haskell does when resource usage > is important? Of course it's not just in functional languages that performance demands can require rewriting shorter, more comprehensible code in less obvious ways. (My favourite example of something so completely non-intuitive is the Intel example from within a Sieve of Eratosthenes program that for(i=0;i<lim/step;++i){ prime[i*step]=0; } can on some processor setups be slower than for(i=0;i<lim/step;++i){ if(prime[i*step]!=0){ prime[i*step]=0; } } due to cache coherency issues.) In that context, there was an old suggestion of Don Knuth's that program source code should in the idealized future not just contain the final, optimized code (with perhaps the original code in comments) but as a kind of set of layers each representing the same semantic program but with increasing orders of optimisation, and links between `things' annotated with a label placed by the programmer explaining why the transformation between an unoptimised version `thing' and an optimised `thing'. The nice bit about this would be that the development environment would be equipped with a subsystem that could almost always establish (possibly using the the label on the link) if the two things had the same semantic effect, and a naive system that could try and produce (maybe using brute force pattern modification) the changes to the optimised version corresponding to changes to the unoptimised version. The nice thing about this is that it would allow changes to the code (due to say changing requirements, or ideas for better algorithms) to be made first to the simple version and then the areas of the optimised version that needed changing would be automatically brought to the programmers attention. (The system for trying to change the optimised code automatically is just there to stop the system becoming really annoying every time you do something something like int i=1; _______\ int i=2; int j=2; / int j=1; to the unoptimised code. The reason I think this would be a good idea is because I don't really object that much to having to optimise code that's performance critical, I just dislike the way that I never manage to keep both the original and optimised version in sync and so end up having to maintain the optimised code directly. I suspect that such a system is still at least 25 years away from feasiblity though :-( ___cheers,_dave________________________________________________________ www.cs.bris.ac.uk/~tweed/pi.htm |tweed's law: however many computers email: tweed(a)cs.bris.ac.uk | you have, half your time is spent work tel: (0117) 954-5250 | waiting for compilations to finish.

4 7

Reproducing lazy evaluation in Scheme
by David Barton 10 Sep '01

10 Sep '01

All right, I know this is a stupid question. I know the models of evaluation in call by name and call by value languages; however, I am kind of puzzled by trying to reproduce call by name in a call by value language using force and delay. If I put a delay around the right side of each equation and around each expression in a function call (*all* function calls?), and a force call around each variable reference, would that get me call by name semantics? Am I completely screwed up here? Is something more necessary? I'm trying to get the gumption up to try a proof by substitution of this idea, but I cringe at the formula manipulation....... Dave Barton <*> dlb(a)averstar.com )0( http://www.averstar.com/~dlb

1 0

Pickling
by Mark Carroll 09 Sep '01

09 Sep '01

Am I right in thinking that there aren't currently any standard libraries for converting values to bitstreams and back, to be saved in files or squirted over network sockets or whatever to be resurrected later or elsewhere? I'd guess it would be hard to write, too - I've not noticed any introspection. How do people normally efficiently pass complex Haskell data structures to other co-operating Haskell processes? (I am thinking of something a bit like Java's serialisation.) -- Mark

5 6

Algebraic types and `objects'
by S.J.Thompson 06 Sep '01

06 Sep '01

To follow up Cagdas Ozgenc's message of Wednesday, I have attached a series of files which show a gradual transformation (or refactoring) of an algebraic type of shapes into a Shape type, built using type classes and existential types, which more corresponds to an OO approach. Hope this is useful. Simon

1 0

algebric types and db integration
by Cagdas Ozgenc 05 Sep '01

05 Sep '01

Hi, I am wondering how one would store instances of algebric types in a database. For example: data Shape = Circle Float | Rectangle Float Float | Triangle Float Float Float All three constructors are representing different schemas. Hence I won't be able to store them in a single table. I think algebric types seem to represent an inheritance hierarchy in terms of OO terms, Shape being the base class, and Circle, Rectangle, Triangle being its subclasses. Is this a correct way of looking at it? How do you suggest I conceptually map it to a relational database? Thanks

2 1

Using Set: Hypergraph type
by Eray Ozkural 04 Sep '01

04 Sep '01

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Greetings all! I'm a new Haskell user. I've used Haskell for a number of small hacks and I can say that this is a brilliant language. I was just working on a hypergraph implementation in haskell. A hypergraph, for those not familiar with it, is a family of sets which are subsets of a vertex set X. I went straight along the mathematical definition, and I decided to try the Edison library that came along with my ghc-5.00.2 Without further ado, here is the code: type Hypergraph n = Set (Set n) - -- hgraph constructor - -- takes a list of edges hgraph edge_list = unionManySets (map mkSet edge_list) My trouble is that this does not seem to work well. Perhaps it's my lack of experience wih Edison, but the types do not seem to be right and the following expression fails to evaluate: Hypergraph> elementOf (mkSet [1]) (hgraph [ [1,2], [1] ]) I expect "True" in response to this query. Anyway, I think this is not ghc specific. (I enabled -fglasgow-exts, no difference. I get a lot of type errors...) What do you think is wrong with this code? It now seems to me that I may not be able to use Edison for my ADT, so how would you recommend me to go about coding this mathematical definition? All I need is to be able to define a set of sets in a convenient way; it also has to be halfway efficient. Should I implement this with lists, or is there an alternative set implementation which allows me to accomplish a decent hypergraph definition? [*] Regards, [*] I could also use a mix of arrays and lists it seems, similar to the edge list and pin list representations used in imperative code. But that does not give me the interface a set implementation would :) - -- Eray Ozkural (exa) <erayo(a)cs.bilkent.edu.tr> Comp. Sci. Dept., Bilkent University, Ankara www: http://www.cs.bilkent.edu.tr/~erayo GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE7lKJQfAeuFodNU5wRAtyBAJ0SCRLAV5u4IBkt3B2VIYB04l9LNACeNL0Y GE9TPhrWoPY6rH58ZDSdweg= =IdNC -----END PGP SIGNATURE-----

3 7

Re: Using Set: Hypergraph type
by Marcin 'Qrczak' Kowalczyk 04 Sep '01

04 Sep '01

Tue, 4 Sep 2001 21:12:41 +0300, Eray Ozkural <erayo(a)cs.bilkent.edu.tr> pisze: > Thanks for the suggestion, but isn't this a bit inefficient? Ordinarily one > would like to compare two elements of a set by reference, not by content. There is no such thing in Haskell. mkSet [mkSet [1, 2]] is indistinguishable from mkSet [mkSet [1, 2]] even if {1,2} sets were created independently. Whether representations of particular mkSet [1, 2] objects are shared is an implementation detail. Well, there are compiler-dependent unsafe functions which could detect sharing, but they are not normally used. Functional programming is about values, not about objects with identities. You could implement a "tagged object" type, like data Tagged a = Tagged Integer a give objects unique numbers as they are created, and make Eq and Ord instances which compare these numbers only, ignoring the real value. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0

Re: Using Set: Hypergraph type
by Marcin 'Qrczak' Kowalczyk 04 Sep '01

04 Sep '01

Tue, 4 Sep 2001 20:28:55 +0300, Eray Ozkural <erayo(a)cs.bilkent.edu.tr> pisze: > Okay, I guess I got it now. The (types of) elements of a Set ought > to be instances of Ord. So I presume Edison supports only flat sets. You can add an inefficient implementation of Ord (Set a) yourself: instance Ord a => Ord (Set a) where compare s1 s2 = compare (toOrdList s1) (toOrdList s2) toOrdList seems to be exported only module Collection. If more than one module does this, they can't be used together. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0

some problem question
by karan babuta 02 Sep '01

02 Sep '01

hi there i am having some problem with the haskell question. if u can help me in that will really be appreciated. thanks for help. MY PROBLEM IS WITH THE SEPERATING THE SHAPES IN A GRID waiting for a sooner reply.THANKS here is the question: A rectangular grid is list of list of Char, where all inner lists are of the same length ie. type Grid = [[Char]] . Inside this grid, white space will be denoted by a '.' and filled pixels will be denoted by '*'. For example, a grid containing a square may look like square :: Grid square = ["............", "............", "...****.....", "...****.....", "...****.....", "...****.....", "............" ] The shapes can be anywhere inside the grid and they can can be of any size > 2 x 2 . That is, the only restriction on the size of the shape is a minimum of 2 x 2 area on the grid. And in cases of non-square, the shape will at least occupy 4 pixels. You can assume that no shape given will be smaller than this and that the shapes given will distinctly fall into one of the categories and will not be ambiguous. There is no restriction on the size of the grid itself, but obviously, it must fully contain the shape(s). There can be either one or two shape(s) inside a grid, but if there are two shapes in the grid, then they are guarenteed to be at least 1 pixel apart, and that they can be separated by cutting the grid either horizontally or vertically. twoTriangles :: Grid twoTriangles = ["....................", "....................", "...........*********", ".....*......*******.", "....***......*****..", "...*****......***...", "..*******......*....", "...................."] Shapes The following shapes are allowed inside a grid : RECTANGLE - The very same rectangle as we all know it. It will not be rotated. TRIANGLE - If it looks like a triangle, then it's a triangle. Note that this means the length of the three edges can be different, and it can be rotated in any way. (You'll notice that this is a very ambiguous definition of a triangle. Within the restraints of this specification, including that (1) all shapes given will be valid. (2) there are only three shapes to be identified. and (3) definition of the other shapes are unambiguous and rigid. You should think about how you can identify the triangle using the simplist way you can think of.) DIAMOND - Any thing that has a shape like [".............", ".............", ".............", ".....*.......", "....***......", "...*****.....", "..*******....", "...*****.....", "....***......", ".....*.......", "............."] To make this easy, a diamond will have horizontal symmetry as well as vertical symmetry. Tasks You are to write the following functions: areaOfOneShape:: Grid -> Int For the shape in the grid, you should count the number of pixels it occupies. (ie, count the number of '*' for each shape), and return the count. recogniseOneShape:: Grid -> String The input Grid will be as describe above, with only ONE shape in the grid, and the output String should be the name of the shapes, eg, "RECTANGLE" Note: You MUST capitalise the name of the shapes in the string you returned, and you MUST spell the name of the shapes correctly The ONLY names of the shapes allowed are the ones described above in the Shapes section PROBLEM: separateShapes :: Grid -> [Grid] The input Grid will contain either one or two shapes. You are to separate the shapes into separate Grids, where each contains a whole shape respectively; ie, if there are two shapes in the original Grid, then you should return two Grids containing a shape each. If there is only one shape in the orignal Grid, then you should just return a list containing a single Grid. The Grids returned must also be rectangular. areaOfShapes :: Grid -> [Int] You should return the area of the shapes. If there is only one shape, then the output will just be a list with one Int. If there are two shapes, then the output will be a list of two Int. The order of the integer returned does not matter. You should (but you don't have to) write this function using functions already defined above. recogniseShapes :: Grid -> [String] Give a Grid containing one or two shapes, return a list of String of the names of the shapes. If there are two shapes, then you can return the name of the two shapes in any order you like. Eg, If there is a triangle and a diamond in the grid, then you should return ["TRIANGLE", "DIAMOND"] (the order of the names does not matter). If there is just a single shape, then you just return a list with a single string, eg, ["RECTANGLE"]. You should (but you don't have to) write this function using functions already defined above. ____________________________________________________________ Do You Yahoo!? Get your free @yahoo.co.uk address at http://mail.yahoo.co.uk or your free @yahoo.ie address at http://mail.yahoo.ie

2 1

Re: hiding import, tuple instances
by Ashley Yakeley 01 Sep '01

01 Sep '01

At 2001-08-31 13:59, I wrote: >At 2001-08-31 09:27, Marcin 'Qrczak' Kowalczyk wrote: > >>> How do I define functions that work on all tuples? >> >>You can't, and this is unfortunate. > >You can make your own 'tuples' using cons = (,) and nil = (). Then you >can use multi-parameter classes to manipulate them. See, for instance, <http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/truth-framework/Source/Type Calc/ListType.hs?rev=HEAD&content-type=text/vnd.viewcvs-markup> ListType> concatenate ('p',(3,(False,()))) ("Hello",(7,())) ('p',(3,(False,("Hello",(7,()))))) -- Ashley Yakeley, Seattle WA

1 0