On Thu, Mar 26, 2009 at 03:23:01PM -0700, Michael Mossey wrote:
But back to the gist of my question last night: I am aware that most examples of recursion presented in the books so far do their processing "as the recursion unwinds." In other words:
length :: [a] -> Int length [] = 0 length (x:xs) = 1 + length xs
This function goes deeper and deeper into the recursion before doing any calculation, then does all the sums "on the way back out."
Right, this is equivalent to length = foldr (+) 0 and results in expressions like (1 + (1 + (1 + (1 + ...)))), which isn't good in this particular case, since none of the additions can be performed until the very end of the list is reached, and all the sums are indeed done "on the way back out". There are some cases, however (such as when the result is some data structure that can be computed lazily, like another list) when this is exactly what you want.
Being an imperative programmer, I keep trying to write loops that accumulate "on the way down", like this:
length' :: Int -> [a] -> Int length' s [] = s length' s (x:xs) = length' (s+1) xs
length :: [a] -> Int length xs = length' 0 xs
And this is equivalent to length = foldl (+) 0 and results in expressions like (((((0 + 1) + 1) + 1) + 1) + ... ). This looks better at first glance, since the sums can start accumulating as you go. However, since Haskell is lazy, this particular version is no better, because the sums won't be evaluated until the result is needed anyway: instead of accumulating a number, you end up accumulating a giant thunk (unevaluated expression) which is only evaluated when its result is finally needed, after the call to length has already finished! So as long as you don't call length on really long lists, you might as well use your first version---if you're going to blow the stack on long lists anyway, you might as well do it in a more natural style. =) But read on... What we'd like is some way to force the accumulator to be evaluated as we recurse down the list---and this is exactly what the foldl' function (from Data.List) does, by introducing a bit of strictness. So the best way to write length is actually length = foldl' (+) 0. Whenever you see this 'accumulator' pattern over lists---some recursive function which recurses over a list while accumulating some small summary value---think foldl'.
I suppose both forms are valid, but the first form seems to be most natural in most situations I've encountered in the exercises.
The first is indeed more natural. Generally speaking, if you find yourself using accumulating parameters, there's probably a simpler way to do it, or some library function that already does exactly what you want to do. But it takes experience to learn and recognize such situations. -Brent