- Haskell-Cafe - Haskell.org

collection library in Haskell
by Alexandru D. Salcianu 21 Nov '03

21 Nov '03

Hello! Can somebody recommend me a good collection library in Haskell? I'm interested in more than one Set implementation, one FiniteMap implementation etc. (we already have this in the standard Haskell'98 library). What I'm searching for is a library where I have the Set, FiniteMap etc. specifications (i.e., typeclasses), and several implementations (i.e., instances) for them. E.g., we can have a list-based implementation of Set (for small sets), but also a tree-based implementation (for larger sets). So, I would like a library with something like this -- sa is a type corresponding to sets of a's -- requires multi-parameter typeclasses class (Eq a) => Set a sa where addSetElem :: sa -> a -> sa -- add an element to a set searchElem :: sa -> a -> Bool -- search an element in a set ... -- list based Set implementation instance (Eq a) => Set a [a] where ... -- ordered-tree Set implementation instance (Ord a) => Set a (OrdTree a) where ... and so on. Furthermore, I'm interested in a library that can be compiled / interpreted by a mainstream tool, e.g., ghc, hugs etc. I've already started writting such a library (mainly for didactic purposes), but I would like to know if an enstablished collection library already exists. Thanks, Alex

4 4

Resolving Ambiguous Types
by Jared Warren 21 Nov '03

21 Nov '03

Thanks to Tom Pledger, Brian Boutel, and Keith Wansbrough for helping me with my last type problem, but now I have another one: :) ----- I understand why it is impossible to infer the intermediate type in `show . read`, but I was hoping someone could help me grasp why this (and only this) is problematic: > class Fooable a where foo :: a > instance Fooable Char where foo = '0' > class Barable a where bar :: a -> String > instance Barable Char where bar = const "Zero" `bar foo` generates an ambiguous type error; but anyone can deterministically see that there is only one intermediate type that satisfies the classes. Why can't the compiler figure it out? Are there any compiler directives, language extensions, or Template Haskell tricks I can use to make the compiler smarten up? (The requirements of my project rule out explicit type signatures.) If not, does anyone know if Chameleon's type system can avoid this problem? Thanks for your help, ~ Jared Warren <warren(a)cs.queensu.ca> Computing Science, Queen's University

2 1

Re: Partially ordered collections (revisited)
by Tom Pledger 21 Nov '03

21 Nov '03

Graham Klyne writes: : | Ah, yes. I've grown a little wary of foldl, but I see it's | appropriate in this case. As it's part of the standard prelude, I | personally have no qualms about depending upon it ... or should I? (Hope you don't mind my returning this to haskell-cafe.) Most of foldl's bad reputation comes from stack overflows, because it builds deeply nested suspensions such as foldl f z [1..99] --> f (... (f (f z 1) 2) ...) 99 *regardless* of the strictness of f. Contrast that with foldr foldr f z [1..99] --> f 1 (foldr f z [2..99]) which enters f straight away. Your particular f, i.e. add, is strict in both its parameters, so I don't think the choice between foldl and foldr will affect whether you get stack overflows. However, if you do get stack overflows, try a strict folding function, such as a copy of Hugs's Prelude.foldl' (not exported). - Tom

1 0

Partially ordered collections (revisited, again)
by Graham Klyne 20 Nov '03

20 Nov '03

Further to my previous message: [[ I've taken the suggestions made by Tom and Robert and combined them into a new module with some supporting functions and test cases. A copy is attached, in case it's of use to anyone. ]] I've tightened the maxima function code in response to a comment from Tom, and added some more partial-ordering comparison primitives. Updated code is attached: -- $Id: PartOrderedCollection.hs,v 1.4 2003/11/20 18:35:59 graham Exp $ (I just had a session trying to use the sourceforge CVS, but I can't find out how to get my combination of WinCVS and SSH tunnelling working.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

AW: GHC and Panther (Mac OS X 10.3)
by Markus.Schnell＠infineon.com 20 Nov '03

20 Nov '03

try using (sudo) gcc-select 2 Cheers, Markus > -----Ursprüngliche Nachricht----- > Von: haskell-cafe-bounces(a)haskell.org > [mailto:haskell-cafe-bounces@haskell.org] Im Auftrag von Thomas Davie > Gesendet: Donnerstag, 20. November 2003 02:07 > An: haskell-cafe(a)haskell.org > Betreff: GHC and Panther (Mac OS X 10.3) > > > Hi, > I've just upgraded to OS X 10.3 and have been having some > problems > with ghc. I'm using ghc 5.04.3 because it is compatible with > hat - I'm > doing a uni project on hat at the moment, so it's critical that it > works. When I attempt to build hmake using ghc I get a whole > load of > errors like these: > > ghc -DUSE_READLINE=1 -L/sw/lib/ -lreadline -I/sw/include -package > lang -c -o > /Users/tatd100/Documents/Work/Project/Tools/hmake-3.08/targets > /powerpc- > Darwin7/obj/hmake/QSort.o QSort.hs > slow-fast dropthrough not mangled > _sAi_entry: > addi r0,r22,12 > cmplw cr7,r0,r23 > ble- cr7,L11 > lis r2,ha16(L_MainCapability$non_lazy_ptr) > lwz r2,lo16(L_MainCapability$non_lazy_ptr)(r2) > lwz r29,12(r2) > b L12 > L11: > lwz r15,0(r22) > lwz r16,4(r22) > lwz r17,8(r22) > addi r22,r22,12 > lis r2,ha16(L_sAi_fast3$non_lazy_ptr) > lwz r29,lo16(L_sAi_fast3$non_lazy_ptr)(r2) > L12: > mtctr r29 > bctr > .align 2 > .section __TEXT,__text,regular,pure_instructions > > Which eventually drop down to one error that kills the whole process: > > ghc -DUSE_READLINE=1 -L/sw/lib/ -lreadline -I/sw/include -package > lang -c -cpp -o > /Users/tatd100/Documents/Work/Project/Tools/hmake-3.08/targets > /powerpc- > Darwin7/obj/hmake/Compat.o Compat.hs > Compat.hs:1: parse error on input `#' > make[1]: *** > [/Users/tatd100/Documents/Work/Project/Tools/hmake-3.08/targets/ > powerpc-Darwin7/obj/hmake/Compat.o] Error 1 > make: *** [targets/powerpc-Darwin7/hmake-ghc] Error 2 > > I'm guessing that there's some binary compatibility issues here... > Could it be panther using gcc3.3? > > Thanks > > Bob > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

3 2

RE: Aggressive inlining
by Simon Peyton-Jones 20 Nov '03

20 Nov '03

Sounds as if you might need Template Haskell http://research.microsoft.com/~simonpj/papers/meta-haskell/ Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Blue | Steel | Sent: 19 November 2003 22:43 | To: haskell-cafe(a)haskell.org | Subject: Aggressive inlining | | I'm working on a parlor trick. | | I would like to solve a 3-SAT problem at compile time, | so that the executable is super fast. | | Consider | --------------------------------------------------- | formula (x1,x2,x3) = (x1 || x2) && x3 | | tf = [True, False] | | assignments = [(x1,x2,x3)|x1<-tf,x2<-tf,x3<-tf] | | solutions = filter formula assignments | | main = do print solutions | --------------------------------------------------- | | Theoretically, a compiler could optimize this to | --------------------------------------------------- | main = do print [(True,True,True),...] | --------------------------------------------------- | | Is this actually possible in GHC? I've played with | inline pragmas and looked at -ddump-..., but I haven't | made much progress. | | Of course, the goal is to replace "formula" with a | formula that takes a 30-tuple instead of a triple and | really let GHC crank. | | Thanks for any help. | | | __________________________________ | Do you Yahoo!? | Protect your identity with Yahoo! Mail AddressGuard | http://antispam.yahoo.com/whatsnewfree | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

GHC and Panther (Mac OS X 10.3)
by Thomas Davie 20 Nov '03

20 Nov '03

Hi, I've just upgraded to OS X 10.3 and have been having some problems with ghc. I'm using ghc 5.04.3 because it is compatible with hat - I'm doing a uni project on hat at the moment, so it's critical that it works. When I attempt to build hmake using ghc I get a whole load of errors like these: ghc -DUSE_READLINE=1 -L/sw/lib/ -lreadline -I/sw/include -package lang -c -o /Users/tatd100/Documents/Work/Project/Tools/hmake-3.08/targets/powerpc- Darwin7/obj/hmake/QSort.o QSort.hs slow-fast dropthrough not mangled _sAi_entry: addi r0,r22,12 cmplw cr7,r0,r23 ble- cr7,L11 lis r2,ha16(L_MainCapability$non_lazy_ptr) lwz r2,lo16(L_MainCapability$non_lazy_ptr)(r2) lwz r29,12(r2) b L12 L11: lwz r15,0(r22) lwz r16,4(r22) lwz r17,8(r22) addi r22,r22,12 lis r2,ha16(L_sAi_fast3$non_lazy_ptr) lwz r29,lo16(L_sAi_fast3$non_lazy_ptr)(r2) L12: mtctr r29 bctr .align 2 .section __TEXT,__text,regular,pure_instructions Which eventually drop down to one error that kills the whole process: ghc -DUSE_READLINE=1 -L/sw/lib/ -lreadline -I/sw/include -package lang -c -cpp -o /Users/tatd100/Documents/Work/Project/Tools/hmake-3.08/targets/powerpc- Darwin7/obj/hmake/Compat.o Compat.hs Compat.hs:1: parse error on input `#' make[1]: *** [/Users/tatd100/Documents/Work/Project/Tools/hmake-3.08/targets/ powerpc-Darwin7/obj/hmake/Compat.o] Error 1 make: *** [targets/powerpc-Darwin7/hmake-ghc] Error 2 I'm guessing that there's some binary compatibility issues here... Could it be panther using gcc3.3? Thanks Bob

2 1

Functional Code Generation
by Brandon Michael Moore 20 Nov '03

20 Nov '03

I think I remeber seeing a paper about techniques for writing code generators in Haskell targeting stack based bytecodes that encoded bytecode sequences in a way that the typechecker could give you some sanity guarantees, and then talked a bit about using dynamic programming for optimizing bytecode sequences. I haven't turned up anything searching Google and CiteSeer (though I don't really know good words to search for), so I'm hoping someone here remembers. A friend of mine is implementing a Scheme -> OCaml bytecode compiler for a class and I think some of the ideas from that paper would help, whatever they were. Thanks Brandon

3 2

Aggressive inlining
by Blue Steel 20 Nov '03

20 Nov '03

I'm working on a parlor trick. I would like to solve a 3-SAT problem at compile time, so that the executable is super fast. Consider --------------------------------------------------- formula (x1,x2,x3) = (x1 || x2) && x3 tf = [True, False] assignments = [(x1,x2,x3)|x1<-tf,x2<-tf,x3<-tf] solutions = filter formula assignments main = do print solutions --------------------------------------------------- Theoretically, a compiler could optimize this to --------------------------------------------------- main = do print [(True,True,True),...] --------------------------------------------------- Is this actually possible in GHC? I've played with inline pragmas and looked at -ddump-..., but I haven't made much progress. Of course, the goal is to replace "formula" with a formula that takes a 30-tuple instead of a triple and really let GHC crank. Thanks for any help. __________________________________ Do you Yahoo!? Protect your identity with Yahoo! Mail AddressGuard http://antispam.yahoo.com/whatsnewfree

1 0

Re: Haskell Server Pages
by Niklas Broberg 20 Nov '03

20 Nov '03

I am part of a project working on an implementation of an HSP system, very much inspired by the paper you mention by Eric Meijer and Daan Leijen. It is our goal to make a complete HSP system with a model for HTML in Haskell, a pre-processor, and a runtime system/plugins for various web servers. The ETA is set to May -04, until then you can follow our progress at http://www.dtek.chalmers.se/~d00nibro/hsp/ There is a simple version of a pre-processor available from our Download page, but use it at your own risk ;) /Niklas _________________________________________________________________ MSN 8 with e-mail virus protection service: 2 months FREE* http://join.msn.com/?page=features/virus

1 0