Haskell/Solutions/Foldable

← Back to Foldable

Deconstructing foldr

1.

-- We start from:
foldMap g = mconcat . fmap g
foldMap g = foldr mappend mempty . fmap g -- mconcat definition
-- Which can be simplified to:
foldMap f = foldr (mappend . f) mempty
-- Or, more pointfully:
foldMap f xs = foldr (\x z -> f x <> z) mempty xs

-- Alternatively (via the definition of foldr):
foldMap _ []     = mempty
foldMap g (x:xs) = g x <> foldMap g xs

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:

{-# LANGUAGE ExistentialQuantification #-} -- First line of the source file.

-- forall a. causes the type to be forgotten.
data NoResults f = forall a. NoResults (f a)   

runNoResults :: Applicative f => NoResults f -> f ()
runNoResults (NoResults u) = const () <$> u

instance Applicative f => Monoid (NoResults f) where
    mempty                            = NoResults (pure ())
    NoResults u `mappend` NoResults v = NoResults (u *> v)

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).

newtype Max a = Max { unMax :: Maybe a }

instance Ord a => Monoid (Max a) where
  mempty                              = Max Nothing
  Max Nothing  `mappend` x            = x
  x            `mappend` Max Nothing  = x
  Max (Just x) `mappend` Max (Just y) = Max $ Just $ max x y

-- safeMaximum can then be written
safeMaximum = unMax . foldMap (Max . Just)

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:

Just x `mappendFirst` _      = Just x
_      `mappendFirst` Just y = Just y
_      `mappendFirst` _      = Nothing

The mirrored alternative would be:

_      `mappendLast` Just y = Just y
Just x `mappendLast` _      = Just x
_      `mappendLast` _      = Nothing

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.

instance Foldable Tree where
    foldMap f t = case t of
        Leaf x       -> f x
        Branch tl tr -> foldMap f tl <> foldMap f tr

1b.

-- Using the catamorphism
-- treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeDepth :: Tree a -> Int
treeDepth = treeFold (\dl dr -> 1 + max dl dr) (const 0)

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.

instance (Monoid a, Monoid b) => Monoid (a,b) where
    mempty                      = (mempty, mempty)
    (x1, y1) `mappend` (x2, y2) = (x1 `mappend` x2, y1 `mappend` y2)

1b.

-- For given a and b
-- f :: (Monoid a, Monoid b) => a -> b
-- If f is a monoid homomorphism, then
-- f mempty = mempty
-- f (x <> y) = f x <> f y
fst (mempty, mempty) = mempty -- Target
fst (mempty, mempty) -- LHS
mempty -- Q.E.D

fst ((x1, y1) <> (x2, y2)) = fst (x1, y1) <> fst (x2, y2)
fst (x1 <> x2, y1 <> y2) = x1 <> x2
x1 <> x2 = x1 <> x2 -- Q.E.D

1c.

foldMap f &&& foldMap g = foldMap (f &&& g) -- Target
-- f &&& g = \x -> (f x, g x)
(\x -> (foldMap f x, foldMap g x)) = foldMap (\x -> (f x, g x)) -- Target 2
-- Target 2 holds if the following hold:
fst . (\x -> (foldMap f x, foldMap g x)) = fst . foldMap (\x -> (f x, g x)) -- Target 3a
snd . (\x -> (foldMap f x, foldMap g x)) = snd . foldMap (\x -> (f x, g x)) -- Target 3b
-- From Target 3a, using the monoid homomorphism property:
fst . (\x -> (foldMap f x, foldMap g x)) = foldMap (fst . (\x -> (f x, g x)))
foldMap f = foldMap f -- OK
-- From Target 3b, using the monoid homomorphism property:
snd . (\x -> (foldMap f x, foldMap g x)) = foldMap (snd . (\x -> (f x, g x)))
foldMap g = foldMap g -- OK
-- Q.E.D (both Target 3a and Target 3b hold.)