April 2009 - Haskell-Cafe

Can't find space leak in external sort with tournament trees (test case attached)
by Denis Bueno 23 Apr '09

23 Apr '09

Hello haskell-cafe, I'm running into what I think is a space leak. I've modified external-sort-0.2 [0] to use tournament trees for merging, and although the block sorting works in constant space, merging seems to produce a space leak. The external sort works by lazily consuming an input list, chopping it up into fixed size blocks, sorting each block in memory and writing each sorted block out to disk. At this point we have a big, on-disk array of k sorted blocks. To produce the final, sorted output list, we lazily read back each block into a tournament tree (a heap of sorts), which should only compare the first element of block to figure out the tree root. The merging algorithm in full is in `tourMerge' [1]. I've confirmed by profiling (with -hc) that the merge step gobbles up memory. I've attached a self-contained program (two haskell source files). It requires binary, mersenne-random*, and ArrayRef from hackage. $ tar xvzf leak.tar.gz leak.hs Data/TournamentTree.hs $ ghc -O --make leak.hs $ ./leak 5000000 # generate 5 million entries in ./entries.tmp, sort them, and output to ./leak.out Writing 5000000 entries to './entries.tmp' Done. Henceforth, if you omit the number argument to leak it will sort './entries.tmp'. Sorting 5000000 entries from './entries.tmp' External block sort using 1000 blocks: -- 5000 entries per block -- 240000 bytes per block 1000--blocks sorted. Merging blocks and writing sorted entries to './leak.out' Depending on how much RAM you have, you may need to tweak the argument to leak and/or numBlocks (at the top of leak.hs) -- a block needs to be able to fit in RAM. If the argument to leak is too low, the sort will succeed and the leak won't be apparent. Otherwise, the OS will kill the process because it allocated too much. Anyone have an idea how I can fix the leak? Denis *Only required to generate the initial input file to sort; it's much faster than System.Random. [0] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/external-sort-0.2 [1] tourMerge is in leak.hs, but I've also inlined it here for convenience. TT is the Data.TournamentTree module, included in the tarball I've attached. tourMerge :: (Ord a) => [[a]] -> [a] tourMerge [] = [] tourMerge blks = let t = {-SCC "TMfromList" #-} TT.fromList blks in tM (TT.minElem t) (TT.deleteMinF t) where tM :: (Ord a) => [a] -> TT.Forest [a] -> [a] tM l f | null f = l | otherwise = let t = TT.tournament f next = TT.minElem t (x, xs) = {-# SCC "TTspan" #-} span (<= head next) l in x ++ (tM next (if null xs then TT.deleteMinF t else (TT.singleton xs : TT.deleteMinF t)))

1 2

Overriding a Prelude function?
by michael rice 23 Apr '09

23 Apr '09

I've been working through this example from: http://en.wikibooks.org/wiki/Haskell/Understanding_monads I understand what they're doing all the way up to the definition of (>>), which duplicates Prelude function (>>). To continue following the example, I need to know how to override the Prelude (>>) with the (>>) definition in my file rand.hs. Michael ============== [michael@localhost ~]$ cat rand.hs import System.Random type Seed = Int randomNext :: Seed -> Seed randomNext rand = if newRand > 0 then newRand else newRand + 2147483647 where newRand = 16807 * lo - 2836 * hi (hi,lo) = rand `divMod` 127773 toDieRoll :: Seed -> Int toDieRoll seed = (seed `mod` 6) + 1 rollDie :: Seed -> (Int, Seed) rollDie seed = ((seed `mod` 6) + 1, randomNext seed) sumTwoDice :: Seed -> (Int, Seed) sumTwoDice seed0 = let (die1, seed1) = rollDie seed0 (die2, seed2) = rollDie seed1 in (die1 + die2, seed2) (>>) m n = \seed0 -> let (result1, seed1) = m seed0 (result2, seed2) = n seed1 in (result2, seed2) [michael@localhost ~]$

6 7

Hac5 roundup
by Martijn van Steenbergen 23 Apr '09

23 Apr '09

Dear Haskell Hackers, Many thanks to all those who attended Hac5! We had a spectacular number of participants: over 50 hackers showed up, representing several countries. Many thanks also to the organising committee and sponsors! Those bagels on Sunday were delicious. :-) Please check out the updated wiki page [1] for: * a nice group photo of most attendants taken by Thomas Davie; * a list of blog posts/galleries/videos of the event; * a list of projects worked on and the progress that was made. Additionally, if you covered Hac5 in some way or contributed to any of the projects, please add your links or progress summary to the page. Thanks, Martijn. [1] http://www.haskell.org/haskellwiki/Hac5

1 0

FRP, integration and differential equations.
by jean-christophe mincke 23 Apr '09

23 Apr '09

In a post in the *Elerea, another FRP library *thread*,* Peter Verswyvelen wrote: *>I think it would be nice if we could make a "reactive benchmark" or something: some tiny examples that capture the essence of reactive systems, and a way to compare each solution's >pros and cons.* * * *>For example the "plugging a space leak with an arrow" papers reduces the recursive signal problem to * * * *>e = integral 1 e* * * *>Maybe the Nlift problem is a good example for dynamic collections, but I guess we'll need more examples.* * * *>The reason why I'm talking about examples and not semantics is because the latter seems to be pretty hard to get right for FRP?* I would like to come back to this exemple. I am trying to write a small FRP in F# (which is a strict language, a clone of Ocaml) and I also came across space and/or time leak. But maybe not for the same reasons... Thinking about these problems and after some trials and errors, I came to the following conclusions: I believe that writing the expression e = integral 1 *something* where e is a Behavior (thus depends on a continuous time). has really two different meanings. 1. if *something *is independent of e, what the above expression means is the classical integration of a time dependent function between t0 and t1. Several numerical methods are available to compute this integral and, as far as I know, they need to compute *something *at t0, t1 and, possibly, at intermediate times. In this case, *something *can be a Behavior. 2. If *something *depends directly or indirectly of e then we are faced with a first order differential equation of the form: de/dt = *something*(e,t) where de/dt is the time derivative of e and *something*(e,t) indicates that *something* depends, without loss of generality, on both e and t. There exist specific methods to numerically solve differential equations between t0 and t1. Some of them only require the knowledge of e at t0 (the Euler method), some others needs to compute *something *from intermediate times (in [t0, t1[ ) *and *estimates of e at those intermediary times. 3. *something *depends (only) on one or more events that, in turns, are computed from e. This case seems to be the same as the first one where the integrand can be decomposed into a before-event integrand and an after-event integrand (if any event has been triggered). Both integrands being independent from e. But I have not completely investigated this case yet... Coming back to my FRP, which is based on residual behaviors, I use a specific solution for each case. Solution to case 1 causes no problem and is similar to what is done in classical FRP (Euler method, without recursively defined behaviors). Once again as far as I know... The second case has two solutions: 1. the 'integrate' function is replaced by a function 'solve' which has the following signature solve :: a -> (Behavior a -> Behavior a) -> Behavior a In fact, *something*(e,t) is represented by an integrand function from behavior to behavior, this function is called by the integration method. The integration method is then free to pass estimates of e, as constant behaviors, to the integrand function. The drawbacks of this solution are: - To avoid space/time leaks, it cannot be done without side effects (to be honest, I have not been able to find a solution without assignement). However these side effects are not visible from outside of the solve function. .. - If behaviors are defined within the integrand function, they are not accessible from outside of this integrand function. 2. Introduce constructions that looks like to signal functions. solve :: a -> SF a a -> Behavior a where a SF is able to react to events and may manage an internal state. This solution solves the two above problems but make the FRP a bit more complex. Today, I tend to prefer the first solution, but what is important, in my opinion, is to recognize the fact that e = integral 1 *something* really addresses two different problems (integration and solving of differential equations) and each problem should have their own solution. The consequences are : 1. There is no longer any need for my FRP to be able to define a Behavior recursively. That is a good news for this is quite tricky in F#. Consequently, there is no need to introduce delays. 2. Higher order methods for solving of diff. equations can be used (i.e. Runge-Kutta). That is also good news for this was one of my main goal in doing the exercice of writing a FRP. Regards, J-C

5 9

Re: [Haskell-cafe] Re: Overriding a Prelude function?
by michael rice 23 Apr '09

23 Apr '09

OK, the 3rd and 4th responses below are the same, which is as it should be. I think we can put this thread to bed. Thanks to all who participated. Michael *Main> rollDie 362354 (3,1795116384) *Main> rollDie 1795116384 (1,523309185) *Main> rollDie 523309185 (4,1311937830) *Main> (rollDie ~>> (rollDie ~>> rollDie)) 362354 (4,1311937830) *Main> --- On Thu, 4/23/09, Heinrich Apfelmus <apfelmus(a)quantentunnel.de> wrote: From: Heinrich Apfelmus <apfelmus(a)quantentunnel.de> Subject: [Haskell-cafe] Re: Overriding a Prelude function? To: haskell-cafe(a)haskell.org Date: Thursday, April 23, 2009, 5:18 AM Achim Schneider wrote: > Well, you obviously need an initial seed: > > rollDie 0xdeadbeef ~>> (rollDie ~>> rollDie) Achim means (rollDie ~>> (rollDie ~>> rollDie)) 0xdeadbeef Regards, apfelmus -- http://apfelmus.nfshost.com _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Re: [Haskell-cafe] Overriding a Prelude function?
by michael rice 23 Apr '09

23 Apr '09

Here's what I get: [michael@localhost ~]$ ghci GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> import Prelude hiding ((>>)) <interactive>:1:0: parse error on input `import' Prelude> ===== I was passing seed0 to rollDie and getting back (r1,seed1) passing seed1 to rollDie and getting back (r2,seed2) passing seed2 to rollDie and getting back (r3,seed3) Just based on the problem text, I would guess that passing rollDie and seed0 to (>>) I would get back (r3,seed3), losing the intermediate random numbers r1 and r2 along the way, at least that's what I understood it to say. So, I know that next I'm probably going to have to do something to remedy that, but I haven't gotten to that next step yet. What is unsugar? Thanks in advance for your patience. Michael --- On Wed, 4/22/09, Dan Weston <westondan(a)imageworks.com> wrote: From: Dan Weston <westondan(a)imageworks.com> Subject: Re: [Haskell-cafe] Overriding a Prelude function? To: "Ross Mellgren" <rmm-haskell(a)z.odi.ac> Cc: "michael rice" <nowgate(a)yahoo.com>, "haskell-cafe(a)haskell.org" <haskell-cafe(a)haskell.org> Date: Wednesday, April 22, 2009, 12:37 PM Be aware that the do unsugars to (Prelude.>>), not your (>>), even if you hide (Prelude.>>): import Prelude hiding ((>>)) m >> f = error "Call me!" main = putStrLn . show $ do [3,4] [5] The desugaring of the do { [3,4]; [5] } is (Prelude.>>) [3,4] [5] = [5,5], whereas you might have hoped for [3,4] >> [5] = error "Call me!" Dan Ross Mellgren wrote: > I think > > import Prelude hiding ((>>)) > > does that. > > -Ross > > On Apr 22, 2009, at 11:44 AM, michael rice wrote: > >> I've been working through this example from: http://en.wikibooks.org/wiki/Haskell/Understanding_monads >> >> I understand what they're doing all the way up to the definition of (>>), which duplicates Prelude function (>>). To continue following the example, I need to know how to override the Prelude (>>) with the (>>) definition in my file rand.hs. >> >> Michael >> >> ============== >> >> [michael@localhost ~]$ cat rand.hs >> import System.Random >> >> type Seed = Int >> >> randomNext :: Seed -> Seed >> randomNext rand = if newRand > 0 then newRand else newRand + 2147483647 >> where newRand = 16807 * lo - 2836 * hi >> (hi,lo) = rand `divMod` 127773 >> >> toDieRoll :: Seed -> Int >> toDieRoll seed = (seed `mod` 6) + 1 >> >> rollDie :: Seed -> (Int, Seed) >> rollDie seed = ((seed `mod` 6) + 1, randomNext seed) >> >> sumTwoDice :: Seed -> (Int, Seed) >> sumTwoDice seed0 = >> let (die1, seed1) = rollDie seed0 >> (die2, seed2) = rollDie seed1 >> in (die1 + die2, seed2) >> >> (>>) m n = \seed0 -> >> let (result1, seed1) = m seed0 >> (result2, seed2) = n seed1 >> in (result2, seed2) >> >> [michael@localhost ~]$ >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org <mailto:Haskell-Cafe@haskell.org> >> http://www.haskell.org/mailman/listinfo/haskell-cafe >

3 2

Re: [Haskell-cafe] Re: Overriding a Prelude function?
by michael rice 23 Apr '09

23 Apr '09

I forgot the type signiture on the last last: (~>>) :: (Seed -> (a,Seed)) -> (Seed -> (b,Seed)) -> (Seed -> (b,Seed)) (~>>) m n = \seed0 -> let (result1, seed1) = m seed0 (result2, seed2) = n seed1 in (result2, seed2) ======== With it I get this: *Main> rollDie 362354 ~>> (rollDie ~>> rollDie) <interactive>:1:0: Couldn't match expected type `Seed -> (a, Seed)' against inferred type `(Int, Seed)' In the first argument of `(~>>)', namely `rollDie 362354' In the expression: rollDie 362354 ~>> (rollDie ~>> rollDie) In the definition of `it': it = rollDie 362354 ~>> (rollDie ~>> rollDie) *Main> Michael --- On Wed, 4/22/09, Achim Schneider <barsoap(a)web.de> wrote: From: Achim Schneider <barsoap(a)web.de> Subject: [Haskell-cafe] Re: Overriding a Prelude function? To: haskell-cafe(a)haskell.org Date: Wednesday, April 22, 2009, 9:52 PM michael rice <nowgate(a)yahoo.com> wrote: > OK, I changed the operator from (>>) to (~>>). When I try to use it I > get this: > > [michael@localhost ~]$ ghci rand > GHCi, version 6.10.1: http://www.haskell.org/ghc/__ :? for help > Loading package ghc-prim ... linking ... done. > Loading package integer ... linking ... done. > Loading package base ... linking ... done. > [1 of 1] Compiling Main________________________ ( rand.hs, interpreted ) > Ok, modules loaded: Main. > *Main> rollDie ~>> (rollDie ~>> rollDie) > > <interactive>:1:0: > ______ No instance for (Show (Seed -> (Int, Seed))) > __________ arising from a use of `print' at <interactive>:1:0-32 > ______ Possible fix: > __________ add an instance declaration for (Show (Seed -> (Int, Seed))) > ______ In a stmt of a 'do' expression: print it Well, you obviously need an initial seed: rollDie 0xdeadbeef ~>> (rollDie ~>> rollDie) -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Re: [Haskell-cafe] Re: Overriding a Prelude function?
by michael rice 22 Apr '09

22 Apr '09

I'm just copying code from this web page: http://en.wikibooks.org/wiki/Haskell/Understanding_monads ================ Using their initial seed I get this: *Main> rollDie 362354 ~>> (rollDie ~>> rollDie) <interactive>:1:0: Couldn't match expected type `t -> (t1, t2)' against inferred type `(Int, Seed)' In the first argument of `(~>>)', namely `rollDie 362354' In the expression: rollDie 362354 ~>> (rollDie ~>> rollDie) In the definition of `it': it = rollDie 362354 ~>> (rollDie ~>> rollDie) *Main> =================== Passing their initial seed through successive calls to rollDie: *Main> rollDie 362354 Loading package old-locale-1.0.0.1 ... linking ... done. Loading package old-time-1.0.0.1 ... linking ... done. Loading package random-1.0.0.1 ... linking ... done. (3,1795116384) *Main> rollDie 1795116384 (1,523309185) *Main> rollDie 523309185 (4,1311937830) <== ISN'T THIS SUPPOSED TO BE THE RESULT? *Main> Michael --- On Wed, 4/22/09, Achim Schneider <barsoap(a)web.de> wrote: From: Achim Schneider <barsoap(a)web.de> Subject: [Haskell-cafe] Re: Overriding a Prelude function? To: haskell-cafe(a)haskell.org Date: Wednesday, April 22, 2009, 9:52 PM michael rice <nowgate(a)yahoo.com> wrote: > OK, I changed the operator from (>>) to (~>>). When I try to use it I > get this: > > [michael@localhost ~]$ ghci rand > GHCi, version 6.10.1: http://www.haskell.org/ghc/__ :? for help > Loading package ghc-prim ... linking ... done. > Loading package integer ... linking ... done. > Loading package base ... linking ... done. > [1 of 1] Compiling Main________________________ ( rand.hs, interpreted ) > Ok, modules loaded: Main. > *Main> rollDie ~>> (rollDie ~>> rollDie) > > <interactive>:1:0: > ______ No instance for (Show (Seed -> (Int, Seed))) > __________ arising from a use of `print' at <interactive>:1:0-32 > ______ Possible fix: > __________ add an instance declaration for (Show (Seed -> (Int, Seed))) > ______ In a stmt of a 'do' expression: print it Well, you obviously need an initial seed: rollDie 0xdeadbeef ~>> (rollDie ~>> rollDie) -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

WHNF versus HNF (was: Optimizing unamb by determining the "state" of a thunk?)
by Peter Verswyvelen 22 Apr '09

22 Apr '09

I'm having difficulty to understand the difference between WHNF and HNF. Is this explanation<http://encyclopedia2.thefreedictionary.com/Weak+Head+Normal+Form> the correct one? Or is WHNF and HNF equivalent in Haskell land? The GHC documentation of seq says: Evaluates its first argument to head normal form, and then returns its second argument as the result. Let's try in GHCi *Main> let f = trace "\\x" $ \x -> ((trace "\\y" $ \y -> trace "y" y + trace "x" x) $ trace "2" 2) *Main> f `seq` () \x () *Main> That did not evaluate anything inside the body of the first lambda, so according to the article, seq reduces to weak head normal form, not hnf...

4 3

Trouble with type signatures and type families
by Stephan Friedrichs 22 Apr '09

22 Apr '09

Hi, consider the following code: ---------------------------- class Foo f where type Bar f :: * type Baz f :: * from :: Bar f -> Baz f to :: Baz f -> Bar f data Tree a b c = Empty | Tree b c (Tree a b c) (Tree a b c) --singleton :: (Foo f) => Bar f -> Tree a (Bar f) (Baz f) singleton x = Tree x (from x) Empty Empty ---------------------------- what type does 'singleton' have? ghci-6.10.2 says: > :t singleton singleton :: forall f a. (Foo f) => Bar f -> Tree a (Bar f) (Baz f) which is no surprise. But when I uncomment the type signature in the above code sample, loading it to ghci gives the following error: > :r [1 of 1] Compiling Main ( T.hs, interpreted ) T.hs:14:22: Couldn't match expected type `Baz f1' against inferred type `Baz f' In the second argument of `Tree', namely `(from x)' In the expression: Tree x (from x) Empty Empty In the definition of `singleton': singleton x = Tree x (from x) Empty Empty T.hs:14:27: Couldn't match expected type `Bar f' against inferred type `Bar f1' In the first argument of `from', namely `x' In the second argument of `Tree', namely `(from x)' In the expression: Tree x (from x) Empty Empty Failed, modules loaded: none. I don't get it... what's wrong, I just copied the inferred type? //Stephan -- Früher hieß es ja: Ich denke, also bin ich. Heute weiß man: Es geht auch so. - Dieter Nuhr

2 2