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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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 > > <[EMAIL PROTECTED]> 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 > > [EMAIL PROTECTED] > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > -- > > ---- Georg Martius, Tel: (+49 34297) 89434 ---- > ------- http://www.flexman.homeip.net --------- > _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe