[Haskell-cafe] Flattening tail recursion?

[GoldPython]

Just compiled this with -O and it ran with no stack overflow.
Evidently, no `seq` needed for this one. Using ghc 6.2.2.

countLines l = countLines' 0 l
countLines' n [] = n
countLines' n (_:ls) = countLines' (n + 1) ls






On Fri, 10 Dec 2004 20:32:07 +0100, Georg Martius
<mai99dgf at studserv.uni-leipzig.de> wrote:
> Hi Will,
> 
> you probably get confused with stack overflow through non-tail recursive function and stack overflow because you accumulate all intermediate values in the closure. It was allready posted before, that you need to enforce the evaluation of the + in order to get the function run in constant space. The thing is, that it is harder to achieve than I expected it to be.
> 
> countLines' ls = foldl (\x y -> let x' = x + 1 in x' `seq` y `seq` x' ) 0 ls
> 
> will run in constant space, but just if compiled with -O (ghc-6.2.1). The seq function forces the evaluation of its first argument (at least to Head Normal Form). The second one is just passed through. To be honest I don't understand why I need the optimisation option and why I do need to force the evaluation of y ?!. I find this really hard to figure out and I think the strictness analyser could be a bit more eager :-).
> 
>        Georg
> 
> 
> 
> 
> On Fri, 10 Dec 2004 13:55:03 -0500, GoldPython <goldpython at gmail.com> wrote:
> 
> > I did this:
> >
> > countLines ls = foldl (\x y -> x + 1) 0 ls
> >
> > Still overflows.
> >
> >
> > On Fri, 10 Dec 2004 19:07:04 +0100 (MEZ), Henning Thielemann
> > <iakd0 at clusterf.urz.uni-halle.de> wrote:
> >>
> >>
> >>
> >> On Fri, 10 Dec 2004, Robert Dockins wrote:
> >>
> >> > >    countLines [] = 0
> >> > >    countLines (_:ls) = 1 + countLines ls
> >> > >
> >> > > I would have thought that this was tail recursive and would be
> >> > > flattened into iteration by the compiler. Can anyone explain why?
> >> >
> >> > countlines = aux 0
> >> >     where aux x [] = x
> >> >           aux x (_:ls)
> >> >                 | x `seq` False = undefined
> >> >                 | otherwise     = aux (x+1) ls
> >> >
> >> > The `seq` causes the x to be evaluated, so it should run in constant space.
> >>
> >> Is it also possible to do that with 'foldl'?
> >>
> >> Why is Prelude.length not defined this way (according to the Haskell98
> >> report)?
> >>
> >>
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> 
> 
> --
> 
> ---- Georg Martius,  Tel: (+49 34297) 89434 ----
> ------- http://www.flexman.homeip.net ---------
>