March 2008 - Haskell-Cafe

Re: static constants -- ideas?
by Don Stewart 03 Mar '08

03 Mar '08

jason.dusek: > I have an awkward programming problem -- I need to take a > dictionary, parse it, build a bunch of intermediate lists and > then make maps and tries out of the list. A "programming > problem" because it's taken me a fair amount of effort to pull > together the parser and list generator -- and "awkward" > because a 69000 item list, [(String, [(String, String)])], > does not compile under GHC (stack overflow). (It's not likely > to compile under anything else, either!) Here's an example of the approach Bryan outlined, which does seem to work for files as large as gcc can handle: * generate your big Haskell Map * serialise it with Data.Binary, and Codec.Compression.GZip to a file * compile the data into a C const array, and link that into Haskell * decode it on startup, ressurecting the Haskell data. The C source looks like: const uint8_t beowulf[] = { 31, 139, 8, 0, 0, 0, 0, 0, 0, 3, 124, 189, 75, 150, 46, 54, 93, 193, 96, 144, 241, 168, 172, 238, 214, 0, ... http://code.haskell.org/~dons/code/compiled-constants/cbits/constants.c which is the gzip, Data.Binary encoded version of a Map ByteString Int. Then the Haskell code need only access this array as a Ptr Word8, wrap that as a Bytestring, then run Data.Binary over the result to rebuild the Map. As you can see here: http://code.haskell.org/~dons/code/compiled-constants/Constants.hs I've put a couple of examples of how to access C-side serialised Haskell values in a package here: http://code.haskell.org/~dons/code/compiled-constants/ Cheers, Don

1 0

Failing to make `par`
by Jefferson Heard 03 Mar '08

03 Mar '08

I've used Control.Parallel and Control.Parallel.Strategies extensively in the past, and I thought I knew what I was doing. I declared the following function: findSupernodes' :: S.Set Name -> Int -> Tree -> Protein.Tree -> S.Set Name findSupernodes' set size (Node i _ _ s il ir) (Protein.Node _ pl pr _ g) | S.size g > size = (Name (fromIntegral i)) `S.insert` set | otherwise = leftNodes `S.union` rightNodes where leftNodes = (findSupernodes' set size il pl) rightNodes = (findSupernodes' set size il pl) findSupernodes' set size (Leaf _ _) (Protein.Gene _ _ _) = set and then simply wrote the following as an initial stab at parallelizing it, because actually calling this function causes the program to execute an absurd number of string comparisons: findSupernodes = findSupernodes' S.empty findSupernodes' :: S.Set Name -> Int -> Tree -> Protein.Tree -> S.Set Name findSupernodes' set size (Node i _ _ s il ir) (Protein.Node _ pl pr _ g) | S.size g > size = (Name (fromIntegral i)) `S.insert` set | otherwise = leftNodes `par` rightNodes `seq` leftNodes `S.union` rightNodes where leftNodes = (findSupernodes' set size il pl) rightNodes = (findSupernodes' set size il pl) findSupernodes' set size (Leaf _ _) (Protein.Gene _ _ _) = set The thing is, these two functions don't return the same thing. The parallel version is returning an empty set, while the sequential version returns what it should return. Any clue what I did wrong? -- Jeff

1 0

ICFP08 Final CFP
by Matthew Fluet (ICFP Publicity Chair) 03 Mar '08

03 Mar '08

Final Call for Papers ICFP 2008: International Conference on Functional Programming Victoria, BC, Canada, 22-24 September 2008 http://www.icfpconference.org/icfp2008 Submission deadline: 2 April 2008 ICFP 2008 seeks original papers on the art and science of functional programming. Submissions are invited on all topics from principles to practice, from foundations to features, from abstraction to application. The scope includes all languages that encourage functional programming, including both purely applicative and imperative languages, as well as languages with objects and concurrency. Particular topics of interest include * Applications and Domain-Specific Languages * Foundations * Design * Implementation * Transformation and Analysis * Software-development Techniques * Functional Pearls * Practice and Experience Important Dates (at 09:00 Apia time, UTC-11) ~~~~~~~~~~~~~~~ Submission: 2 April 2008 Author response: 21 May 2008 Notification: 16 June 2008 Final papers due: 7 July 2008 Call for Papers (full text) ~~~~~~~~~~~~~~~ http://www.icfpconference.org/icfp2008/cfp/cfp.html The submission URL will be available from the above page shortly. Program Chair ~~~~~~~~~~~~~ Peter Thiemann Albert-Ludwigs-Universität Georges-Köhler-Allee 079 79110 Freiburg, Germany Email: icfp08(a)informatik.uni-freiburg.de Phone: +49 761 203 8051 Fax: +49 761 203 8052 Mail sent to the address above is filtered for spam. If you send mail and do not receive a prompt response, particularly if the deadline is looming, feel free to telephone and reverse the charges.

1 0

STAMP benchmark in Haskell?
by Tom Davies 03 Mar '08

03 Mar '08

I'm experimenting with STM (in CAL[1] rather than Haskell) and want to run the STAMP[2] benchmarks. Is there a Haskell translation available, or can anyone suggest a better/different benchmark suite for STM? Thanks, Tom [1] http://openquark.org/Open_Quark/Welcome.html [2] http://stamp.stanford.edu/

3 2

coerce (safe!)
by Krzysztof Skrzętnicki 03 Mar '08

03 Mar '08

Well, it is simply > coerce :: a -> b > coerce _ = undefined so coerce is simply empty function. But still, it is possible to write a function of type (a->b). Well, possibly I didn't write anything particularly new, but please excuse me for I'm still in sort of a shock after I've discovered it. Yet this function reminds me how little I know so I have a question for you. I didn't took any lectures in Category Theory (for I'm still just a student, and I won't for there are none in my institute), but are there any good (e)books you would recommend for a (future) computer scientist? Regards Christopher Skrzętnicki

6 5

Parody of Darcs patch theory from 1981
by Paul Johnson 02 Mar '08

02 Mar '08

I was looking through my old copy of "The Devil's DP Dictionary" by Stan Kelly-Bootle, and came across the entry for Stepwise Refinement. I thought "I've seen this before: this is a parody of Darcs patch theory". It included the Null patch, chains of patches, inverse patches, and pseudo-inverse patches. But the book was published in 1981. I've got the pages scanned, but I can't upload them to Wikimedia because they are still in copyright. However I'm quite sure that limited distribution would fall into "fair use" (non-commercial, small part of work, no impact on market, academic relevance). The total file size is about 520kBytes. Assuming people would like to see them, does anyone have any ideas beyond "email to requestors"? Paul.

3 3

A mini haskell (in 244 lines of python)
by Tim Newsham 02 Mar '08

02 Mar '08

For education and fun I wrote a small untyped non-strict lambda calculus evaluator in python. One of the goals was to keep it fairly small and simple, and to do most of the work in the implemented scripting language itself. For that reason, I added macros to allow things like "let" and "letrec" to be defined as syntactic sugar easily outside of the evaluation engine itself. The result is 244 lines of python, a small prelude that implements tuples, lists and the state monad, and some small example scripts. The prelude and scripts are heavily influenced by Haskell, the main differences being a much simpler syntax, lack of pattern matching and lack of a type system. Data structures aren't supported but are implemented fairly easily using lambda expressions as described in http://www.cs.nott.ac.uk/~nhn/TFP2006/Papers/03-JansenKoopmanPlasmeijer-Eff… This is all available at http://www.thenewsh.com/%7Enewsham/lambda/ as extracted package and .tgz. The README file has documentation including small examples. Accompanying scripts provide more complete examples, such as: [WITHLIST [LET from2 (iter (add 1) 2) [LET primes (nubBy (\x \y (eq (mod y x) 0)) from2) (traceList Val (take 10 primes)) ]]] which calculates the first 10 primes. Exercise to the reader: I bet the evaluator could all be written much more compactly in Haskell. Tim Newsham http://www.thenewsh.com/~newsham/

1 0

Generating a random list
by Milos Hasan 02 Mar '08

02 Mar '08

Hi, so let's say I want to generate a list of N random floats. The elegant way of doing it would be to create an infinite lazy list of floats and take the first N, but for N = 1,000,000 or more, this overflows the stack. The reason is apparently that the take function is not tail-recursive, and so it uses O(N) stack space.. What is the right way to do this? Sure, I could write my own tail-recursive generator function. But this seems to be an instance of a more general problem - how to avoid algorithms linear in stack space when dealing with large lists. Thanks a lot! Milos

7 12

"Wrong kind" when attempting to build a monad for a circular list of functions
by Aaron Altman 02 Mar '08

02 Mar '08

Hi everybody. I'm working towards a better understanding of Haskell monads the only way I know how: by working through an example. I am working on an AI agent that will perform a finite series of actions before starting the sequence over again. I figured a circular list of functions that shifts as you apply them would be the way to do it. Here is my test code: ----------------------------- import Control.Monad runActionAndIterate :: [a -> a] -> a -> (a, [a -> a]) runActionAndIterate (currentAction:actionList) actionInput = (currentAction actionInput, concat [actionList, [currentAction]]) shiftActionList :: [a -> a] -> [a -> a] shiftActionList (currentHead:rest) = concat [rest, [currentHead]] newtype CircularFuncList funcList arg = CircularFuncList (funcList -> arg -> (arg, funcList)) instance Monad (CircularFuncList funcList arg) where return a = CircularFuncList (\funcList a -> (a, funcList)) CircularFuncList currentFuncList currentArg >>= argTransform = let result = argTransform $ (head currentFuncList) currentArg newFuncList = map argTransform $ shiftActionList currentFuncList in CircularFuncList newFuncList result ----------------------------- I get an error that CircularFuncList funcList arg has kind * while Monad is looking for * -> *. This is a first attempt so it may be I'm a ways off from a monad that implements a circular list of functions. That is the goal though. What advice can you offer? Thanks, Aaron Altman

5 8

.cabal problem
by Galchin Vasili 02 Mar '08

02 Mar '08

Hello, I am trying to install a package on my Linux Ubuntu machine. It chokes build-depends: base, directory because directory dependency is unresolvable. Do I have to specify "extra-libs" so that correct library space is searched? Actually I tried this and it didn't help. ?? Regards, Vasya

2 2