Isn't this tail recursive?

[Jay Cox]

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