foldr in Haskell

[toughwimp11]

Does anyone know why foldr in Haskell is not defined in a tail-recursive manner? It seems like it's be more efficient to have a foldr sort of like this:

foldr0 f init [] [] = init
foldr0 f init (x:xs) [] = foldr0 f (f x init) xs []
foldr0 f init xs (y:ys) = foldr0 f init (y:xs) ys

foldr f init xs = foldr0 f init [] xs

rather than:

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

although the code is a bit more complicated I guess. Any ideas?

 

[dinkumthinkum]

What you are doing is effectively reversing the list first, before folding.

Remember that

foldr op init xs

is supposed to produce the equivalent of

  x1 op (x2 op (x3 op (x4 op ... (xn op z) ... )))

and that Haskell is a lazy language that can handle infinite data structures.

So the simple demo which shows that your function is not equivalent to the real foldr is this:

take 10 $ foldr (:) [] [1..]

the real foldr outputs a list from 1 to 10. Your foldr goes on an infinite loop as it attempts to reverse the infinite list 1 to infinity.

In general, here's a tip: use foldr most of the time unless you're absolutely sure you will not gain any advantage from laziness (partially computed folds). If you want a strict fold, use foldl' from the Data.List package. That is tail-recursive, and it forces every iteration as well.

For example, you don't gain anything from partially computed summation of numbers (except a waste of memory as the delayed computation is aggregated), so to sum up a list of numbers you should do

sum' ns = foldl' (+) 0 ns

it is a long-standing and well-known problem that the Haskell report defines the sum function with foldl, but this gets the worst of both laziness and strictness. Use sum' as defined above instead.