Isn't this tail recursive?
Jyrinx
jyrinx_list@mindspring.com
12 Mar 2002 19:52:40 -0800
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