# Haskell/Solutions/Foldable

← Back to Foldable

## Deconstructing foldr

1.

## The Foldable class

1.
A summary of the answers. Subtle issues are explained in the notes just below.
| Fold | mempty | mappend | Preliminary function | newtype from Data.Monoid | Notes |
| product | 1 | (*) | | Product | |
| concat | | (++) | | | |
| concatMap f | | (++) | f | | |
| all p | True | (&&) | p | All | |
| elem x | False | (||) | (== x) | Any | |
| length | 0 | (+) | const 1 | Sum | |
| traverse_ f | pure | (*>) | void . f | | See [i] |
| mapM_ f | return | (>>) | void . f | | See [i] |
| safeMaximum | Nothing | max' Nothing m = m max' m Nothing = m max' (Just x) (Just y) = Just (max x y) | | | See [ii] |
| find p | Nothing | leftmost Just | \x -> if p x then Just x else Nothing | First | See [iii] |
| composeL f | id | flip (.) | flip f | Dual . Endo | See [iv] |
Notes:
[i]: The monoid here is of type Applicative f => f. The function void (defined as fmap (const) in Data.Functor) is needed to convert the inner values of the actions to, thereby discarding the inner values. This conversion is not needed with an implementation in terms of foldr (as the actual one is); however, for a foldMap that isn't the generic one using Endo, we would need to either discard the results using void (as done above) or create a wrapper which forgets the result type. The latter trick (a rather advanced one, in fact) uses a feature called existential quantification, and might look like this:
While this is a stylish solution, it creates a host of complications − we can't use newtype nor records, and we still need one fmap (const) for extracting the final action. So take this approach merely as a curio.
On a more reasonable note, mapM_ only differs from traverse_ in the type signature, as return = pure and (>>) = (*>). That also mean the observations above apply to it as well.
[ii]: max :: Ord a => a -> a -> a evaluates to the largest of its two arguments, and max' :: Ord a => Maybe a -> Maybe a -> Maybe a is similar but involves Maybe. The usage of Maybe here is just a trick to add an extra value of Nothing to the type a so that max' can become a legal mappend. Nothing, as mempty, is the identity of max', and hence acts as a value that is less than or equal to all values in a (e.g. something like negative infinity for the integers). This monoid may be implemented with the wrapper Max as follows (and in fact something like this is used internally in the default implementation of maximum from Data.Foldable).
Note that liftA2 max cannot be used as mappend, since liftA2 max Nothing x = Nothing, and therefore Nothing is not the identity of liftA2 max as required by the monoid laws.
[iii]: By "leftmost Just", we mean:
The mirrored alternative would be:
They are implemented through the First and Last newtype wrappers from Data.Monoid respectively.
[iv]: That is a condensed version of the solution to the foldl exercise in Higher-order functions. Dual is a Data.Monoid wrapper which flips the mappend of a wrapped Monoid.

## List-like folding

1a.
1b.
It is impossible to implement treeDepth using Foldable. Folding a tree like a list destroys information about the structure of the branches. That can be clearly displayed by finding a pair of trees with different structures but which are converted to equal lists by toList.

## More facts about Foldable

1a.
1b.
1c.