CODEWITHSUNDEEP
haskellfunctional-programminglazy-evaluationfold
user200783
user200783

Reputation: 14346

Does Haskell have an eager version of `foldr`?

The Foldr Foldl Foldl' wiki page describes the differences between foldr and foldl. Both process lists from left-to-right, but foldr accumulates the result from right-to-left whereas foldl does so from left-to-right.

The page goes on to discourage the use of foldl in favor of the eager version foldl', which is more efficient.

Is there a corresponding eager version of foldr, presumably called foldr'? If so, is there a reason that it isn't mentioned on the wiki page?

Upvotes: 4

Views: 211

Answers (3)

K. A. Buhr
K. A. Buhr

Reputation: 51109

A quick Hoogle search shows that there is, indeed, a foldr' defined in Data.Foldable.

I assume the reason it isn't mentioned on the linked page is that it isn't relevant to the problem of stack overflows discussed there. When calculating a sum using foldr (+) 0 on a large list, the stack overflow that may occur isn't a result of lazy application of the operator (+). Rather, it occurs because a fundamental feature of a right fold (whether strict or lazy) is that the most deeply nested application of the operator occurs at the end of the list. For an operator like (+) that requires evaluation of both operands to yield any sort of result, this means that either foldr or foldr' must build up an O(n) stack of continuations before getting to the end of the list where the (+) operator can start to do "real work".

Upvotes: 4

dfeuer
dfeuer

Reputation: 48611

Both foldr and foldl' are extremely useful for lists. Neither foldl nor foldr' is often useful for lists. But these days, those functions are actually methods of the Foldable class, and they are useful for some instances. To take an extreme example, consider snoc lists:

data SL a = SL a :> a | Nil
infixl 5 :>

instance Foldable SL where
  foldMap _ Nil = mempty
  foldMap f (xs :> x) = foldMap f xs <> f x

  foldl _ b Nil = b
  foldl f b (xs :> x) = f (foldl f b xs) x

  foldr' _ n Nil = n
  foldr' c n (xs :> x) =
    let n' = c x n
    in n' `seq` foldr' c n' xs

For snoc lists, foldl and foldr' are really useful, while foldr and foldl' are pretty much useless!

Many Foldable containers can make good use of all four of these methods. For example, Data.Set.Set, Data.Map.Map k and Data.Sequence.Seq can each be folded perfectly well in either direction.

import Data.Sequence (Seq)
import qualified Data.Sequence as S

toForwardList :: Seq a -> [a]
toForwardList = foldr (:) []

toReverseList :: Seq a -> [a]
toReverseList = foldl (flip (:)) []

The forward and reverse conversions are equally efficient and equally lazy.

Upvotes: 0

chi
chi

Reputation: 116174

There's no need for foldr', sonce one can always use foldr f with a strict f to achieve the same goal.

We could define it...

foldr' f a xs = foldr f' a xs
  where f' x y = seq x (seq y (f x y))

... but it's simpler to pass a strict f at the call point instead, if needed.

Upvotes: 9

Related Questions