Menu
New Haskell programmer will soon enough go to sources to see how foldr is implemented. Well, the code used to be simple (don't expect newcomers to know about OldList or FTP).
How does the new code work?
-- | Map each element of the structure to a monoid,
-- and combine the results.
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
-- | Right-associative fold of a structure.
--
-- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z
638
Haskell : foldr. Description: it takes the second argument and the last item of the list and applies the function, then it takes the penultimate item from the end and the result, and so on. See scanr for intermediate results.
To recap, with foldr , the purpose of the function argument is to take the first element of the list and the results of having folded the rest of the list, and return the new value. With foldl , the function argument takes a default value, the first element of the list, and returns a new default value.
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.
foldr takes two arguments: A combining function and an identity value. It then returns a function that takes a list and returns an accumulated value. In this case, a -> b -> b is still the combining function and b is the identity value.
I'll just mention the parts that are not in the answer @duplode linked.
First, those implementations you list are default methods. Every Foldable type needs to provide its own specific version of at least one of them, and lists ([]) provide foldr, which is implemented pretty much as it always has been:
foldr k z = go
where
go [] = z
go (y:ys) = y `k` go ys
(Which is, for efficiency, a bit different from the Haskell report version.)
Also, a slight change in the Foldable default since duplode's answer is that strange #. operator, used internally in GHC's Data.Foldable code. It's basically a more efficient version of . that works only when the left function is a newtype wrapper/unwrapper function. It's defined using the new newtype coercion mechanism, and gets optimized into essentially nothing:
(#.) :: Coercible b c => (b -> c) -> (a -> b) -> (a -> c)
(#.) _f = coerce
{-# INLINE (#.) #-}
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
