- Beginners - Haskell.org

Performance of parallel mergesort
by Jon Harrop 27 Dec '09

27 Dec '09

I took the parallel merge sort described here: http://martin.sulzmann.googlepages.com/AMP-Spring2008-intro.pdf and added a simple test: main :: IO () main = do putStrLn $ show $ sum $ mergesort $ [sin x | x <- [1.0 .. 1000000.0]] Compiled it with GHC 6.8.2 from Debian testing and ran it with various +RTS -N<n> arguments to measure its performance and obtained the following results on an 8 core: $ ghc --make -O2 -threaded mergesort.hs -o mergesort [1 of 1] Compiling Main ( mergesort.hs, mergesort.o ) Linking mergesort ... $ time ./mergesort +RTS -N1 -0.117109518058233 real 0m9.723s user 0m9.461s sys 0m0.232s $ time ./mergesort +RTS -N2 -0.117109518058233 real 0m13.574s user 0m15.225s sys 0m0.140s $ time ./mergesort +RTS -N3 -0.117109518058233 real 0m13.185s user 0m15.529s sys 0m0.184s $ time ./mergesort +RTS -N4 -0.117109518058233 real 0m13.251s user 0m15.829s sys 0m0.336s $ time ./mergesort +RTS -N5 -0.117109518058233 real 0m13.093s user 0m16.929s sys 0m0.164s $ time ./mergesort +RTS -N6 Segmentation fault real 0m5.711s user 0m7.408s sys 0m0.136s That segfault must be due to a bug in GHC so I thought perhaps a newer version of GHC might fix the segfault but I installed GHC 6.10.4 from Sid and now I get: $ ghc --make -O2 -threaded mergesort.hs -o mergesort Binary: Int64 truncated to fit in 32 bit Int ghc: panic! (the 'impossible' happened) (GHC version 6.10.4 for i386-unknown-linux): Prelude.chr: bad argument Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug I'll try the haskell-platform package next. Are these known problems? -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e

4 7

Enumerated types
by legajid 27 Dec '09

27 Dec '09

Hello, I have some trouble evaluating Enum class. Following is my source: data Authors= Buzzati | Werber | Verne | Ray | Asimov | Voltaire deriving (Enum, Show) auths=[Buzzati .. Verne] ++ enumFrom Ray pref=take 3 auths -- 1 disp_pref=mapM_ (putStrLn) pref auth1 = Buzzati auth2 = succ auth1 -- Werber auth3 = pred Asimov -- Ray num_auth4=fromEnum Verne -- 2 -- 2 toEnum main= display Buzzati display x = do putStrLn (show x) display (succ x) -- 3 end of enum 1. could'nt match expected type [Char] against inferred type Authors I would like to display each data constructor name on one line , giving : Buzzati Werber Verne How can i translate data from one type to another (Authors to [Char])? 2. Like fromEnum gives data constructor index, is it possible with toEnum (or other way) to get the nth constructor of the given type ? eg : 2 applied to Authors (not in scope ?) would give Verne 3. tried to take 'succ' of last tag in enumeration How to detect the end of an enumeration ? Can i get the maxbound index ? Thanks, Didier.

4 5

Maybe and IO
by legajid 27 Dec '09

27 Dec '09

Hi, My purpose is to get data from the keyboard and return a maybe value, saying "nothing" if the data entered is invalid. I get a message "could'nt match expected IO Integer against inferred type maybe integer" on line x<- getdata Why should x be Maybe ? getdatanum is, but getdata is not. Is it possible to write only one function rather than 2 distinct ones ? Thanks for your help, Didier. Here's my code getdata :: IO Integer getdata=do x<-getLine let xn=read x ::Integer return xn getdatanum :: Maybe Integer getdatanum = do x <- getdata {- if x < 5 then do return (Just x) else do return Nothing -} return (Just x)

2 1

parser for expressions
by John Moore 27 Dec '09

27 Dec '09

Hi, What I'm trying to do is create a parser so as when I enter say 1+1 it will return Add(Val 1)(Val 1). A couple of questions do I have to state three basic parser. As in item, fail, synbol and then combine them with below. And by the way the one below seems to be all wrong. parse :: String -> expr parse expr = [(expr,string)] expr :: Parser value expr = do t <- term do char '+' e <- expr return Add (Val t)(Val e) +++ return t (+++) :: Parser a -> Parser a -> Parser a t +++ w inp = case t inp of [] -> w inp [(v,out)] -> [(v,out)] This is what I mean by item fail and symbol type Parser s a = [s] -> [(a,[s])] item [] = [] item (c:cs) = [(c,cs)] pFail :: Parser s a pFail = \cs -> [] pSymbol :: Eq s => s -> Parser s s pSymbol a (b:bs) |a == b = [(b,bs)] |otherwise = [] I know this is a bit of a mess, but could someone explain where I should start and if I should use any of the code above. Also to point out I want to write the complete parser without using prelude and other built in functions as I will be changing as I go. John

2 2

Design Question: fmap with two lists
by jonathanGfischoff＠gmail.com 27 Dec '09

27 Dec '09

I have a class that is basically: data TwoLists = TL {doubleList :: [Double], intList :: [Int]} Almost all of the operations of this type map, fold, etc on one of the lists or the other, and then return a new instance of the type. So I am implementing to functions dFmap, and iFmap. I actually would like all of the list functions, but I don't want to reimplement them. So my question is, what is the haskell way of handling a type like this. Is there some sort of TwoTypeTraversable I should be deriving from? Essential is there a Haskell idiom for this situation. -Jonathan

3 4

Performance of parallel mergesort
by Jon Harrop 26 Dec '09

26 Dec '09

For some reason all traffic from this beginners list stopped reaching me after the 13th of December. Thanks for the response, Antoine. I've tried to install more recent versions of GHC (6.10 and 6.12) but I cannot get either of them to work at all. GHC 6.8 generates code that segfaults and the GHC 6.10 from Debian testing cannot compile anything for me. So I thought I'd try GHC 6.12. That isn't in any repo so I decided to build it from source. I uninstalled all other GHCs to give it a fresh start. The GHC page says "Stop, install the Haskell Platform" but the Haskell Platform says you must install GHC first, so I've got a nice circular dependency right from the start! So I tried installing GHC 6.12 from source but that requires GHC to be installed. So I installed GHC 6.8 (the one that segfaults) using apt again from Debian. That seems to have built a GHC 6.12 that I can run from the command line but it cannot compile that program because it doesn't have parallel stuff. So I thought I'd install the Haskell Platform. Unfortunately, the Haskell Platform configure script gives the nonsensical error that I must "upgrade" from GHC 6.12 down to GHC 6.10. I was getting pretty run down by this point so I just told it to sod off using the --enable-unsupported-ghc-version command line option. The Haskell Platform's configure script then completed but building it failed with: [21 of 21] Compiling Graphics.UI.GLUT ( Graphics/UI/GLUT.hs, dist/build/Graphics/UI/GLUT.p_o ) Registering GLUT-2.1.1.2... Setup: GLUT-2.1.1.2: dependency "OpenGL-2.2.1.1-182b091280ce0de861295bc592bae77c" doesn't exist (use --force to override) Error: Building the GLUT-2.1.1.2 package failed make: *** [build.stamp] Error 2 I have glut and use it all the time from OCaml without a hitch so I've no idea what the problem is here. Oh well, I just discovered that installing GHC 6.12 has at least fixed GHC 6.10 so it can now compile and run that mergesort. Oh FFS, spoke too soon: $ time ./mergesort +RTS -N8 Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize' to increase it. real 0m38.801s user 4m0.851s sys 0m1.308s -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e

4 7

Finding the height of a simple binary tree
by Matt Young 26 Dec '09

26 Dec '09

Hi guys! Just so we are all on the same page, this problem is an exercise from the end of Chapter 3 in the book Real World Haskell (#8). The problem calls for me to write a function to figure out the height of our user defined binary tree type. Here is the type: --chapter3 binary tree recursive type data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Show) With this type, we'd create a tree with no leaves like: Node "tree" Empty Empty, and a tree with a single leaf like Node "tree2" = Empty (Node "leaf" Empty Empty) Being new to Haskell, I'm not sure how to traverse this binary tree type that the book has given. No doubt we'll be using some crafty recursion to get this done. So to summarize what I'd like to know, 1) what is the best way to figure out the height of this binary tree type that I have, or rather any binary tree in general? 2) How do I translate that into Haskell code. Verbose explanations are appreciated. Thanks guys! -- -Matthew

5 5

Re: Applicability of FP unchanging things to real world changing things
by Stephen Blackheath [to Haskell-Beginners] 25 Dec '09

25 Dec '09

Glurk, You wrote: > I think a lot of people, looking at the real world, would answer, yes, it > clearly IS the same book, now in a different state. And yes, I CAN step into > the same river twice. This is how people see and think about the real world. I think this is a really interesting question, and I may be too new at functional programming myself to do it justice. I've been doing a lot of Haskell in a short time, so my experience is fairly intuitive and this email is part of the process of making it more conscious. Here's one way to structure the library: lend :: BookID -> Library -> Library actOn :: Request -> Library -> (Library, [Result]) actOn (Lend bookID) lib = (lend bookID lib, []) ... -- | A library is a transformation from Request events (e.g. 'lend') to Result events (e.g. overdue book email), -- implemented using lazy lists. library :: Library -> [Request] -> [Result] library lib0 reqs = concat $ snd $ mapAccumL (\lib req -> actOn req lib) lib0 reqs Now, are we mutating a library, or are we not? In spite of what the more Zen-oriented Haskellers might say, it seems to me we are. Call me uneducated but I can't really see what is actually wrong with the idea of mutation of state over time, where the abstraction is appropriate. Perhaps the point is that in Haskell, this is one of many ways of looking at it. Perhaps the essential difference here is that the library goes round in an "eddy" with an inflow of events influencing it as it goes round (and producing an outflow of Result events). This difference accounts for more than it seems to. (Trying to put my finger on it...) it's a much more restricted activity than mutating state outright, that means that if you change your code locally (e.g. re-write the I/O parts), your chance of breaking things is minimal to zero. > I guess that brings up another point - that eventually we are drawn into > monads, which to me seems a bit unfortunate, because it seems that it leads us > back to imperative programming with mutable state... In many situations where I could use a state monad I don't (though I went through a stage of using them). My advice would be just write the code straight, and if the state management gets complex, a state monad may be warranted, or some better way may present itself. The great beauty of Haskell is that you have a lot of choices when a situation like this arises, and going for a state monad before you've examined the alternatives potentially restrict them. In the library example, if Library is a complicated data structure, you might want to have some lift functions that allow functions that affect only parts of the library to be lifted into a 'Library -> Library' type, e.g. liftDueDates :: (DueDates -> DueDates) -> Library -> Library liftDueDates f lib = lib { libDueDates = f (libDueDates lib) } Or to take the concept further ... There may be situations where you want to do some process where there are a number of parts of the library you want to work with, but conceptually some other way of viewing it makes sense. The "Haskell Way" would be to take the right parts of Library and create a new data structure that reflects the conception better. (In FP you often abstract things using data where you would use code in imperative languages.) If some output from that process has to contribute to a modified Library, then implement that as yet another transformation. Putting things back together like this is the extra work that Haskell makes you do - but the benefits outweigh the costs. So I'd say this: If you write your code in really plain Haskell, you'll tend towards a functional approach (e.g. why pass Library when it's better to transform library in some way first?). In that process, a state monad might suggest itself as a way of making the code more readable, but the thinking is still "plain Haskell". Then you're using a state monad with "right mindfulness" so to speak. Way of looking at it #2: If you are using a state monad because it's easier for you to understand the code that way, that's probably the wrong reason to use one. If you're using it because your straightforward Haskell is looking a bit unreadable, and the state monad tidies it up, then that's probably the right reason to use one. Way of looking at it #3: Your data needs to go through transformations from one form to another. In functional programming, you turn that process into a flow of data (or a sequence of transformations) from one form into another. If the flow loops, it starts to look a bit like mutating state, but in a way that's really only a surface appearance. One difference between state monads and mutating state in place (as done in OO languages) is that (in my experience) even with a state monad, the state mutation never really gets a chance to dominate the program. Haskellers have a saying "don't fear the monad - only IO is impure" that's applicable here. However, it's true that monads can lead to bad code, so they need to be used only where they're actually appropriate. I had an example of an excellent use for a monad recently: A parser where looking up an XML tag by its id string is abstracted as a continuation (so it can use IO if it wants) and it needs the ability to bail out if there's a parse error. A monad allowed me to write this code purely and cleanly. Another difference (state monad vs. mutating in place) is that a state monad can never lead to race conditions. Steve

2 1

Einstein's Problem
by Patrick LeBoutillier 23 Dec '09

23 Dec '09

Hi all, I've been working hard at trying to solve Einstein's problem (http://www.davar.net/MATH/PROBLEMS/EINSTEIN.HTM) if an efficient manner using Haskell. I have posted my solution here: http://haskell.pastebin.com/m3ff1973a This exercise has been a real eye opener for me, especially for learning to work with the Maybe and List monads. I'm looking for suggestions for making the "test" function nicer. In order to make my solution fast, I generate my test cases incrementally, thereby elimating most of the cases early on. However the function looks funny (deeply nested). I'm also open to any comments about making better use of the different Haskell idioms. Thanks a lot, Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

2 3

Pure Regex.PCRE Possible? (PLEAC, Fix Style)
by Volkan YAZICI 23 Dec '09

23 Dec '09

Hi, I'm trying to implement FixStyle[1] program of PLEAC[2] for Haskell. (It's missing in the Haskell version of PLEAC.) For this purpose, I needed regular expressions. (Now, I have two problems!) Despite, my code is, IMHO, quite purely functional, Regex.PCRE.String functions totally mess up the design with impure functions they introduce even for really simple string matching stuff. If you'd check out the sources[3], you'll see below impure functions. transDictRegex :: IO PCRE.Regex matchRegex :: String -> IO (String, String, String) translate :: String -> IO String However, if I'm not mistaken, above functions _should_ be absolutely pure. Is it possible to encapsulate impure PCRE functions into their pure equivalents? BTW, why are PCRE functions impure? Regards. [1] http://pleac.sourceforge.net/pleac_perl/strings.html [2] http://pleac.sourceforge.net/ [3] http://hpaste.org/fastcgi/hpaste.fcgi/view?id=14422

4 7