foldl is tail recursive, so how come foldr runs faster than foldl?

I wanted to test foldl vs foldr. From what I've seen you should use foldl over foldr when ever you can due to tail reccursion optimization.

This makes sense. However, after running this test I am confused:

foldr (takes 0.057s when using time command):

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl (takes 0.089s when using time command):

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

It's clear that this example is trivial, but I am confused as to why foldr is beating foldl. Shouldn't this be a clear case where foldl wins?

Edit Report

I don't think anyone's actually said the real answer on this one yet, unless I'm missing something (which may well be true and welcomed with downvotes).

I think the biggest different in this case is that foldr builds the list like this:

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))

Whereas foldl builds the list like this:

((([0] ++ [1]) ++ [2]) ++ ... ) ++ [999888]) ++ [999999]) ++ [1000000]

The difference in subtle, but notice that in the foldr version ++ always has only one list element as its left argument. With the foldl version, there are up to 999999 elements in ++'s left argument (on average around 500000), but only one element in the right argument.

However, ++ takes time proportional to the size of the left argument, as it has to look though the entire left argument list to the end and then repoint that last element to the first element of the right argument (at best, perhaps it actually needs to do a copy). The right argument list is unchanged, so it doesn't matter how big it is.

That's why the foldl version is much slower. It's got nothing to do with laziness in my opinion.

answered 2013-03-14T05:39:30.017

foldl is tail recursive, so how come foldr runs faster than foldl?

1 Answer

Your Answer