Isn't this tail recursive?

[Jyrinx]

Aha! Gotcha. Thanks for the explanation.

I suppose that, in general, for tail recursion to work right, the
accumulator has to be evaluated strictly (as is how my code was fixed)?

Jyrinx
jyrinx_list@mindspring.com

On Tue, 2002-03-12 at 09:34, 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.
> 
> 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
> > 
> 
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell