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 _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell