Jules Bean wrote:

On 10 Dec 2004, at 15:34, Robert Dockins wrote:

...

So it should get "flattened," but it still doesn't run in constant space because the "x" parmeter isn't strict, so it will accumulate a bunch of closures like (((((((0)+1)+1)+1)+1)+1).... To make it strict, do something like this:

Isn't this what the strictness analyser is for? Doesn't GHC know that + for Int is strict in both arguments, and therefore it shouldn't accumulate a great big thunk like that?

Jules

Doesn't look like.... -------------- cnt.hs ------------------------ countlines = aux 0 where aux x [] = x aux x (_:ls) = aux (x+1) ls countlines' = aux 0 where aux x [] = x aux x (_:ls) | x `seq` False = undefined | otherwise = aux (x+1) ls ----------------------------------------------- $ /cygdrive/c/ghc/ghc-6.2.2/bin/ghci.exe ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.2.2, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. Prelude> :load cnt.hs Compiling Main ( cnt.hs, interpreted ) Ok, modules loaded: Main. *Main> countlines [1..100000] 100000 *Main> countlines [1..1000000] *** Exception: stack overflow *Main> countlines' [1..1000000] 1000000 *Main>

Thanks to all for the good info. I see what tail recursion is now. Robert's example above leads me to a couple questions: I had actually written my countlines like Robert's before the other one I mailed in and mine overflowed the stack just like his. According to people's responses, this one really is tail recursive, isn't it? If so why does it not get flattened out? countlines = aux 0 where aux x [] = x aux x (_:ls) = aux (x+1) ls countlines' = aux 0 where aux x [] = x aux x (_:ls) | x `seq` False = undefined | otherwise = aux (x+1) ls Lastly, I've not seen the seq operator shown here in Robert's countlines' before. What does it do?

On 10 Dec 2004, at 16:35, Ben Rudiak-Gould wrote:

Jules Bean wrote:

...

On 10 Dec 2004, at 15:34, Robert Dockins wrote:

...

So it should get "flattened," but it still doesn't run in constant space because the "x" parmeter isn't strict, so it will accumulate a bunch of closures like (((((((0)+1)+1)+1)+1)+1).... To make it strict, do something like this:

Isn't this what the strictness analyser is for? Doesn't GHC know that + for Int is strict in both arguments, and therefore it shouldn't accumulate a great big thunk like that?

It doesn't know that about (+) :: Num a => a -> a -> a. The original poster's code didn't mention Int anywhere, so GHC probably had to assume the worst.

Forcing it to Int doesn't help though :( Jules

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 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)?

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 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 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 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

--

---- Georg Martius, Tel: (+49 34297) 89434 ---- ------- http://www.flexman.homeip.net ---------

Hi everyone, I had the idea that, instead of using 'seq', one might check for parity: countLines2 aux (_:l) | even aux = ... | odd aux = ... that prevents stack overflow, but is much slower than countLines1 aux (_:l) | aux `seq` False = ... | otherwise = ... I also tried countLines3 aux (_:l) | even aux || odd aux = ... | otherwise = ... and countLines4 aux (_:l) | even aux || True = ... | otherwise = ... which also are slower than countLines1. Well, checking for parity takes time, so that is no real surprise. What somehow puzzles me is that, compiling with -O, all versions of countLines are equally fast, if I give the type countLines :: Int -> [a] -> Int, but if I replace Int with Integer, the plain version without guards and the 'seq' version are equally fast whereas the parity-check versions are equally fast among themselves but slower than plain. If I omit the type-declaration, all versions perform differently, plain producing stack overflow, countLines1 being by far the fastest, countLines4 coming in second, then countLines3 and last countLines2. If I give the type Int -> [a] -> Int and use interpreted code, plain overflows, countLines1 is by far the fastest, but then things change. Now countLines2 comes in second, third is countLines4, relatively close, last, at a distance, is countLines3. (Qualitatively the same, but slower, without type-declaration). With type Int -> [a] -> Int, but compiled without -O, the results are (for countLinesX 0 [1 .. 1500000]) plain : stack overflow, 1 : 0.43 secs, 2 : 1.10 secs, 3 : 1.26 secs, 4 : 0.93 secs. Now obviously -O does a good job (though 'seq' isn't so bad even without -O), but why does checking for parity take extra time for Integer and not for Int? And why does compilation without -O change the order of versions 2-4 ? If anybody knows, mind telling me? Thanks in advance, Daniel Am Freitag, 10. Dezember 2004 22:37 schrieb Jules Bean:

On 10 Dec 2004, at 20:33, GoldPython wrote:

...

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

That's presumably the answer. GHC's strictness analyser *can* cope with this situation but only under -O... whereas most of us where testing under ghci...

Confirmation from one of the Simons?

Jules

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Georg Martius wrote:

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.

This isn't quite right. It's more accurate to say that seq ties together the evaluation of its arguments, so that the left argument is evaluated whenever (and just before) the right argument is. In particular, (x `seq` x) is the same as x. Your expression let x' = x + 1 in x' `seq` y `seq` x' evaluates x' redundantly; it's (almost) semantically equivalent to let x' = x + 1 in y `seq` x' which is equivalent to y `seq` (x + 1) which, in this instance, might as well just be x + 1 since the strictness problem is unrelated to the list elements passed in y. In fact there's nothing you can do inside either argument to foldl to make the accumulation strict, because the arguments aren't used until the whole list has already been processed and the huge intermediate thunk has already been built. You need a separate "strict foldl" function, usually called foldl', which was unaccountably omitted from the prelude. If GHC does manage to compile a use of foldl into strict code, it's because of its internal strictness analyzer, not because of any explicit calls to seq. Because I'm a cautious guy, I actually tried compiling both versions with ghc -O to check that I was right -- and I'm wrong! GHC does treat them differently. It even treats countLines' ls = foldl (\x y -> let x' = x + 1 in x' `seq` y `seq` x' ) 0 ls differently from countLines' ls = foldl (\x y -> let x' = x + 1 in y `seq` x' ) 0 ls The latter overflows the stack, the former doesn't. I have no idea what's going on here. Simon PJ? Simon M? -- Ben