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 | hdaume@isi.edu 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 jyrinx_list@mindspring.com