May 2014 - Beginners - Haskell.org

parallelizing a function for generating prime numbers
by Norbert Melzer 18 May '14

18 May '14

Hi there! I am trying to enhence the speed of my Project Euler solutions… My original function is this: ```haskell problem10' :: Integer problem10' = sum $ takeWhile (<=2000000) primes where primes = filter isPrime possiblePrimes isPrime n = n == head (primeFactors n) possiblePrimes = (2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..] ]) primeFactors m = pf 2 m pf n m | n*n > m = [m] | n*n == m = [n,n] | m `mod` n == 0 = n:pf n (m `div` n) | otherwise = pf (n+1) m ``` Even if the generation of primes is relatively slow and could be much better, I want to focus on parallelization, so I tried the following: ```haskell parFilter :: (a -> Bool) -> [a] -> [a] parFilter _ [] = [] parFilter f (x:xs) = let px = f x pxs = parFilter f xs in par px $ par pxs $ case px of True -> x : pxs False -> pxs problem10' :: Integer problem10' = sum $ takeWhile (<=2000000) primes where primes = parFilter isPrime possiblePrimes isPrime n = n == head (primeFactors n) possiblePrimes = (2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..] ]) primeFactors m = pf 2 m pf n m | n*n > m = [m] | n*n == m = [n,n] | m `mod` n == 0 = n:pf n (m `div` n) | otherwise = pf (n+1) m ``` This approach was about half as slow as the first solution (~15 seconds old, ~30 the new one!). Trying to use `Control.Parallel.Strategies.evalList` for `possiblePrimes` resulted in a huge waste of memory, since it forced to generate an endless list, and does not stop… Trying the same for `primeFactors` did not gain any speed, but was not much slower at least, but I did not expect much, since I look at its head only… Only thing I could imagine to parallelize any further would be the takeWhile, but then I don't get how I should do it… Any ideas how to do it? TIA Norbert

4 4

Re: [Haskell-beginners] Space leak while reading from a file?
by Jan Snajder 15 May '14

15 May '14

From: Bob Ippolito <bob(a)redivi.com> > I don't know why I ended up looking at an old version of Data.Text but the > copy function has been around for a year, since 0.11.3.0. > http://hackage.haskell.org/package/text-1.1.1.2/docs/Data-Text.html#copy ? > you'll want to use it for this use case. Great, thanks, that solved the problem! Best, Jan

1 0

"99 Haskell Problems" solutions page formatting
by Eduard Nicodei 15 May '14

15 May '14

Hello everybody! I apologize if I'm sending this email to the wrong mailing list / group. If so, does anybody know where I should be asking wiki-related questions? I think Haskell is a wonderful language and I would like to help the community in whatever way I can. Currently I was looking at the 99 Haskell problems from the wiki, trying to solve them in as many ways as possible: http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems I have noticed there is a note saying that some of the solutions could do with reformatting. Indeed I have noticed that the solution pages aren't very consistent. I edited "the solutions for problem nr. 4" page: http://www.haskell.org/haskellwiki/99_questions/Solutions/4 I added headlines, separated the alternative solutions into logical groups and there was one (the Prelude implementation) which was mentioned twice. Could somebody please have a look over the changes and confirm I didn't do anything wrong please? I have read the wiki editing guide, but I am unsure if this a good format to use for the "Solutions" pages. Many thanks! Eduard Nicodei

2 1

Problem with installing SDL
by Julian Drube 14 May '14

14 May '14

Hi, i'm trying to install the SDL package with: cabal install sdl but the following error is showing up: Graphics/UI/SDL/Events.hsc:56:23: Module ‘Data.Typeable’ does not export ‘Typeable(typeOf)’ cabal: Error: some packages failed to install: SDL-0.6.5 failed during the building phase. The exception was: ExitFailure 1 GHC version is 7.8.2 Thanks in advance for any ideas Julian

3 4

Learning Haskell with the help of trees
by Michal Kawalec 14 May '14

14 May '14

Hi, I am beginning to learn Haskell, and I decided to try to implement a tree. Its code is available at https://gist.github.com/anonymous/dd3eaa8bc36025d7751c I would need some help with implementing the delete element procedure. I have a feeling I am doing something very unhaskelly there. Also, when deleting a node having two children, how do I run two actions (swap the values and delete the successor)? Also, I would be delighted if you could take a look on the style and similar aspects, as they are best addressed at the beginning. Thanks, Michal

3 4

Addition of "Float" and "Int".
by Venu Chakravorty 14 May '14

14 May '14

Hello everyone, I am just starting with Haskell so please bear with me. Here's my question: Consider the below definition / output: Prelude> :t (+) (+) :: (Num a) => a -> a -> a What I understand from the above is that "+" is a function that takes two args which are types of anything that IS-AN instance of "Num" (Int, Integer, Float, Double) and returns an instance of "Num". Hence this works fine: Prelude> 4.3 + 2 6.3 But I can't understand why this doesn't work: Prelude> 4.3 + 4 :: Int <interactive>:1:0: No instance for (Fractional Int) arising from the literal `4.3' at <interactive>:1:0-2 Possible fix: add an instance declaration for (Fractional Int) In the first argument of `(+)', namely `4.3' In the expression: 4.3 + 4 :: Int In the definition of `it': it = 4.3 + 4 :: Int I expected that the second addition would work as both "Float" and "Int" are instances of "Num". Is it that since both the formal args are defined as "a" they have to be exactly the same instances? Had "+" been defined something like: (+) :: (Num a, Num b) => a -> b -> a my second addition would have worked? Please let me know what I am missing. Regards, Venu Chakravorty.

5 4

Space leak while reading from a file?
by Jan Snajder 12 May '14

12 May '14

Dear all, I'm trying to implement a simple file-based database. I apparently have a space leak, but I have no clue where it comes from. Here's the file-based database implementation: http://pastebin.com/QqiqcXFw The idea to have a database table in a single textual file. One line equals one table row. The fields within a row are whitespace separated. The first field is the key. Because I'd like to work with large files, I don't want to load the whole file into memory. Instead, I'd like to be able to fetch the rows on demand, by keys. Thus I first create an index that links keys to file seeks. I use the readerT to add the index to the IO monad. For testing, I use a dummy table produced as follows: import System.IO import Text.Printf import Control.Monad row = unwords [printf "field%03d" (i::Int) | i <- [1..999]] main = do forM_ [1..250000] $ \i -> putStrLn $ printf "row%06d %s" (i::Int) row This generates a 2.1G textual file, which I store on my disk. The testing code: import FileDB import qualified Data.Text as T import Text.Printf import Control.Applicative import Control.Monad import Control.Monad.Trans import System.IO import System.Environment main = do (f:_) <- getArgs t <- openTable f runDB t $ do ks <- getKeys liftIO $ do putStrLn . printf "%d keys read" $ length ks putStrLn "Press any key to continue..." getChar forM_ ks $ \k -> do Just r <- getRow k liftIO . putStrLn $ printf "Row \"%s\" has %d fields" (T.unpack k) (length r) When I run the test on the 2.1GB file, the whole program consumes 10GB. 6GB seem to be allocated after the index is built (just before entering the forM_ function). The remaining 4GB are allocated while fetching all the rows. I find both things difficult to explain. 6GB seems too much for the index. Each key is 9 characters (stored as Data.Text), and I have 250K such keys in a Data.Map. Should this really add up to 6GB? Also, I have no idea why fetching all the rows, one by one, should consume any additional memory. Each row is fetched and its length is computed and printed out. I see no reason for the rows to be retained in the memory. Here's the memory allocation summary: > 1,093,931,338,632 bytes allocated in the heap > 2,225,144,704 bytes copied during GC > 4,533,898,000 bytes maximum residency (26 sample(s)) > 3,080,926,336 bytes maximum slop > 10004 MB total memory in use (0 MB lost due to fragmentation) > > Tot time (elapsed) Avg pause Max pause > Gen 0 2171739 colls, 0 par 45.29s 45.26s 0.0000s 0.0030s > Gen 1 26 colls, 0 par 1.50s 1.53s 0.0589s 0.7087s > > INIT time 0.00s ( 0.00s elapsed) > MUT time 279.92s (284.85s elapsed) > GC time 46.80s ( 46.79s elapsed) > EXIT time 0.68s ( 0.71s elapsed) > Total time 327.40s (332.35s elapsed) > > %GC time 14.3% (14.1% elapsed) > > Alloc rate 3,908,073,170 bytes per MUT second > > Productivity 85.7% of total user, 84.4% of total elapsed Btw., I don't get the "bytes allocated in the heap" figure, which is approx. 1000 GB (?). I'm obviously doing something wrong here. I'd be thankful for any help. Best, Jan

4 4

How do I do inheritance in haskell?
by Dimitri DeFigueiredo 08 May '14

08 May '14

Hi! I am trying to understand how to "factor out" common functionality in haskell. (All the code is available here https://github.com/defigueiredo/inheritance-in-haskell [1]) I am receiving orderbook data from a Bitcoin Exchange, through their JSON API (available at https://www.bitstamp.net/api/order_book/ [2]) I have a generic JSON parser that parses the text response and gives me back a generic JSON object I called Jvalue. This data type represents any JSON object and is defined as follows. (see json.org for full JSON specs) ------------------ import qualified Data.Map as Map data Jvalue = Jobject (Map.Map String Jvalue) | Jarray [Jvalue] | Jstring String | Jnumber Double | Jbool Bool | Jnull deriving Show ------------------- Now, I have to convert this (if possible) into an OrderBook type. An orderbook is basically two lists. One list of the orders placed by people who want to buy, the "bids", and the other with the orders of people who want to sell, the "asks". Each order specifies what price should be paid and how many bitcoins to buy/sell (the volume). The functions for generating the lists of bids and asks are essentially the same. However, they might need to know if they are creating bids or asks. So, I may need to pass a parameter with that information. I can make that parameter a function or a type (or I may not need it). These three different ideas give rise to 3 different ways to define the orderbook: 1) We can make each Order a type with two constructors (my initial idea): ------------------- newtype Volume = Volume Double deriving (Show) newtype Price = Price Double deriving (Show) data Order = Bid {price::Price, volume::Volume} | Ask {price::Price, volume::Volume} deriving (Show) data OrderBook = OrderBook{ bids::[Order] , asks::[Order] } deriving (Show) ------------------- 2) We can make Bid and Ask types themselves ------------------- newtype Volume = Volume Double deriving (Show) newtype Price = Price Double deriving (Show) data Order = Order {price::Price, volume::Volume} deriving (Show) newtype Bid = Bid Order deriving Show newtype Ask = Ask Order deriving Show data OrderBook = OrderBook{ bids::[Bid] , asks::[Ask] } deriving (Show) ------------------- 3) We can make Order a class ------------------- newtype Volume = Volume Double deriving (Show) newtype Price = Price Double deriving (Show) class Order a where makeOrder :: String -> String -> a data Ask = Ask {aprice::Price, avolume::Volume} deriving (Show) instance Order Ask where makeOrder = makeAsk data Bid = Bid {bprice::Price, bvolume::Volume} deriving (Show) instance Order Bid where makeOrder = makeBid data OrderBook = OrderBook{ bids::[Bid] , asks::[Ask] } deriving (Show) -- makeAsk and MakeBid defined later ------------------- It is not clear to me which one of these should be used and, most importantly, which criteria should be used to choose between them. I wrote up the code to do the conversion of the Jvalue object into an OrderBook in the 3 different ways. (The third one came out of a discussion from a haskell meetup group.) (All the code is available here https://github.com/defigueiredo/inheritance-in-haskell [1]) Any insights on how to choose between them would be *greatly* appreciated! Thanks, Dimitri Links: ------ [1] https://github.com/defigueiredo/inheritance-in-haskell [2] https://www.bitstamp.net/api/order_book/

6 6

Pattern Matching & Binding
by Ari King 08 May '14

08 May '14

Hi, I've posted (on http://pastebin.com/R5MPNaHs) code I'm working on to practice reading/writing CSV and interacting with DBs. I'd appreciate help in better understanding how to destructure (pattern match) lists/vectors (see line 28 in post) and the difference in "binding" via let/where and <-. I'd also appreciate suggestions on how to improve the code put together thus far to make it more idiomatic. Thanks. Best, Ari

3 4

Parsec Many Mishap
by Walter Askew 06 May '14

06 May '14

I am trying to use parsec to turn strings like this: “#newch The Period #txt It was the best of times #newpar #txt it was the worst of times” into data structures like this: [NewChapter “The Period”, Text "It was the best of times”, NewParagraph, Text "it was the worst of times”] My current attempt returns this, however: [NewChapter "The Period "] That is, my current implementation only parses out the first item in the string and does not find the remaining items. I’m not sure why that is. I’d suspect I am misusing parsec’s “many” or “manyTill” somehow, but it isn’t clear to me why my use of “many" results in only single item lists. My code is pasted below — any suggestions? This is my first exploration of parsec, so any general suggestion on using the library are welcome (for instance, I do note that I end up double-parsing the strings “#newch, #txt and #newpar because both nextCommand and the newChapter newText and newPar parsers all parse those same strings, but I’m not sure how to avoid that elegantly.) Thanks for your help! parser = many command command = newChapter <|> newTxt <|> newPar newChapter = do try (string "#newch") spaces chapterName <- text return (NewChapter chapterName) newTxt = do try (string "#txt") spaces content <- text return (Text content) newPar = do try (string "#newpar") spaces return NewParagraph text = manyTill anyChar nextCommand nextCommand = try (string "#newch") <|> try (string "#txt") <|> try (string "#newpar") <|> eof *> return ""

2 2