Isn't this tail recursive?
Jay Cox
sqrtofone@yahoo.com
Tue, 12 Mar 2002 19:06:28 -0600 (CST)
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