Isn't this tail recursive?

[Hal Daume III]

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
>