Aha! Gotcha. Thanks for the explanation. I suppose that, in general, for tail recursion to work right, the accumulator has to be evaluated strictly (as is how my code was fixed)?
Jyrinx [EMAIL PROTECTED] On Tue, 2002-03-12 at 09:34, Hal Daume III wrote: > Here's the basic idea. Suppose we have the function: > > > sum [] acc = acc > > sum (x:xs) acc = sum xs (acc+x) > > This is tail recursive, but not strict in the accumulator argument. What > this means is that the computation will be performed lazily, so sum > [4,5,8,10,14,20] 0 will go like this: > > > sum [4,5,8,10,14,20] 0 = > > sum [5,8,10,14,20] (0+4) = > > sum [8,10,14,20] ((0+4)+5) = > > sum [10,14,20] (((0+4)+5)+8) = > > sum [14,20] ((((0+4)+5)+8)+10) = > > sum [20] (((((0+4)+5)+8)+10)+14) = > > sum [] ((((((0+4)+5)+8)+10)+14)+20) = > > ((((((0+4)+5)+8)+10)+14)+20) > > this computation in the accumulator argument won't be evaluated until you > try to print it or something, which will reduce it and perform the > computation. this means that for a list of length n, the the sum > computation will grow in size O(n). what you need is to make sure that > the computation is done strictly and that is done using seq or $!, as in: > > > sum2 [] acc = acc > > sum2 (x:xs) acc = sum2 xs $! (acc+x) > > this means that "acc+x" will be computed at each step, so the accumulator > will hold only the integer (or whatever type) and not the thunk (the > computation). > > the type of "$!" is the same as "$": > > > $! :: (a -> b) -> a -> b > > the sematics of $! are: > > > f $! a = f a > > but the difference is that $! causes "a" to be reduced completely, so it > won't build a huge thunk. > > at least that's my understanding; i'm willing to be corrected :) > > - Hal > > -- > Hal Daume III > > "Computer science is no more about computers | [EMAIL PROTECTED] > than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume > > On 11 Mar 2002, Jyrinx wrote: > > > > > Normal -> countAll' cs 0 nl (nw + newWord) (nc + 1) > > > > White -> countAll' cs 1 nl nw (nc + 1) > > > > Newline -> countAll' cs 1 (nl + 1) nw (nc + 1) > > > > > > > > > make this something like > > > > > > ... > > > > > > Normal -> nw' `seq` nc' `seq` countAll' cs 0 nl nw' nc' > > > White -> nc' `seq` countAll' cs 1 nl nw nc' > > > Newline-> nl' `seq` nc` `seq` countAll' cs 1 nl' nw nc' > > > where nw' = nw + newWord > > > nc' = nc + 1 > > > nl' = nl + 1 > > > > Cool! That did the trick ... (runs on very little memory *and* time now > > ... very cool) I've read through the other responses (thanks all!), and > > I'm still not exactly sure what's going on ... I'm relatively new to > > Haskell, and my understanding of laziness is hardly rigorous; in > > general, how should I know where I need to use seq, and what I need to > > use it on? Is there a paper I should read? (I've got Hudak's book, but > > it does everything lazily IIRC) > > > > Jyrinx > > [EMAIL PROTECTED] > > > > _______________________________________________ > Haskell mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
