Menu
foldr and foldMap can be used to define each other as I understand. But how is that possible, as the latter uses monoids, while the former does not? Do we have any guarantees that the stuff the foldr works on can have a monoid?
944
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.
Haskell, in turn, has two fundamental functions representing reducing, or, as we call it, folding – foldl and foldr – that differ in the order of the folding. foldl reduces elements of a container from left to right (as reduce in other languages usually does), while foldr reduces from right to left.
foldr :: (a -> b -> b) -> b -> [a] -> b
Note that a -> b -> b is a -> (b -> b). Functions b -> b form a monoid under composition.
Note how this resembles
foldMap :: (..omitted..) => (a -> m) -> f a -> m
The only difference is that foldMap doesn't use the "zero" argument of type b of fold and returns an m, which in terms of foldr would be b->b. Now just apply one to the other and you've recovered foldr from foldMap.
96
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
