Menu
Consider these various attempts at something that works like last:
Prelude> import Data.Foldable
Prelude Data.Foldable> foldr const undefined (reverse [1,2,3])
3
Prelude Data.Foldable> foldr' const undefined (reverse [1,2,3])
3
Prelude Data.Foldable> foldl (flip const) undefined [1,2,3]
3
Prelude Data.Foldable> foldl' (flip const) undefined [1,2,3]
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
undefined, called at <interactive>:5:21 in interactive:Ghci4
It makes sense to me that foldl and foldr both work, since they aren't strict in their accumulator, and it makes sense to me that foldl' doesn't, since it is. But why does foldr' work? Isn't it supposed to be strict in its accumulator too?
384
Difference Between foldl and foldr The difference is that foldl is tail-recursive, whereas foldr is not. With foldr and non-optimized patterns, proc is applied to the current value and the result of recursing on the rest of the list. That is, evaluation cannot complete until the entire list has been traversed.
Only foldr is lazy and can be used for codata/infinite streams. While foldl is tail-recursive (enhanced with strict application foldl' can avoid stack overflow). This is why foldr should be used by default in Haskellin order preserve laziness across function composition.
So we can see why foldr sometimes works on infinite lists when foldl doesn't: The former can lazily convert an infinite list into another lazy infinite data structure, whereas the latter must inspect the entire list to generate any part of the result.
Foldr — foldr is a higher-order function in Haskell with the following type signature: foldr :: (a -> b -> b) -> b -> [a] -> b. The easiest way to think about foldr is that it takes a list, and replace the : operator with the given function, and the empty list with the given value.
One consequence is that a foldl' (unlike foldr) applied to an infinite list will be bottom; it will not produce any usable results, just as an express reverse would not. Note that foldl' (flip (:)) []==reverse. foldl' often has much better time and space performance than a foldr would for the reasons explained in the previous sections.
The other very useful fold is foldl'. It can be thought of as a foldr with these differences: foldl' conceptually reverses the order of the list. One consequence is that a foldl' (unlike foldr) applied to an infinite list will be bottom; it will not produce any usable results, just as an express reverse would not.
And in contrast to Python’s reduce function, foldl first has to build the entire thunk chain before it can start reducing that thunk chain. This means that we have to allocate memory on the heap for all elements of the list until the thunk chain is finally established. Only then can we start reducing the thunk chain.
In Haskell, foldl' is way more efficient than foldl because you don’t have to first build up a huge thunk chain before you can finally start reducing the expression. As I said, with foldl you have to first allocate memory on the heap for every single list item until you have the finished thunk chain.
For reference, the instance Foldable [] overrides foldr, foldl, foldl', but not foldr' (source):
instance Foldable [] where
elem = List.elem
foldl = List.foldl
foldl' = List.foldl'
foldl1 = List.foldl1
foldr = List.foldr
{- ... -}
foldr' is defined by default as (source):
foldr' :: (a -> b -> b) -> b -> t a -> b
foldr' f z0 xs = foldl f' id xs z0
where f' k x z = k $! f x z
Note that there is only a strictness annotation on the result of f. So the initial accumulator is not forced.
This suggests a different implementation which does force the accumulator:
foldr'' :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr'' f = foldr (\x z -> f x $! z)
(Edited: the previous version was specialized to lists.)
I have no idea why one was chosen over the other. Probably an oversight,
and it would be more consistent for foldr' to not use the default implementation in the Foldable [] instance.
As an aside, the default definition of foldl' is also different from the list one in the same way:
-- Default (class Foldable t where ...)
foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
where f' x k z = k $! f z x
-- List implementation
foldl' :: forall a b . (b -> a -> b) -> b -> [a] -> b
foldl' k z0 xs =
foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> z `seq` fn (k z v))) (id :: b -> b) xs z0
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
