On Tue, 12 Mar 2002, 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.
I hate to say it, but my understanding of it is that it isnt so simple (which could be good or bad depending upon your view). I guess he best i can describe it is that it will force a to weak head normal form (which is the same as being reduced completely for expressions with only integers, or whatever...) For instance, forcing x=(map f) $! [1..] will essentially force [1.. to (1: (thunk generating [2..]) just before the (map f) is applied. I think. Ok maybe that was a bad example but I can't really think of a good one right now. You might add something that it isn't the (+) operator thats generating the thunks. It is the fact (and only this!) that (+) isn't being forced. I always got confused how (+) could be strict in both arguments, at least for the primitives Float, Integer, and the like, yet still apparently generate a bunch of thunks, like in your expression ((((((0+4)+5)+8)+10)+14)+20). Appearances can be deceiving. But, once that outermost expression is forced, the forcing moves down toward the innermost expression and then the whole expression implodes into a value. I guess the confusion was I somehow conjectured that the application of a strict function to a value would cause haskell to apply that function strictly, when in fact it should not and does not and I was plainly wrong. Here is a short "proof" bottom::[Int] bottom=bottom --bottom = _|_ y = const 3 -- const v = \x -> v main=print (y (head bottom)) If my conjecture was right, main would not terminate. (head is a strict function being applied to _|_ ). However we know that since y = \x -> 3, y will not force x, therefore main will print 3. However... all one needs to do is to change the above to. main=print (y $! (head bottom)) _|_ should be, propagated to main by the following deductions: head _|_ = _|_, y $! _|_ = _|_, print _|_ = _|_. thus main = _|_. Ooh, interesting. I tried that in ghc 5.00 and in fact ghc is smart enough to detect bottom here! It says
[jay@localhost haskell]$ ./a.out
Fail: <<loop>>
awesome! I feel like I am rambling to no end. alright. I hope I haven't been too confusing here. All in all I do like your explanation though. Oh, and after I went to the trouble to write this, I see that you did correct yourself. All my work all for naught! Maybe somebody will get something from my ramblings. Thanks, Jay Cox