Search code examples
haskellfold

Question about the Foldable Maybe instance

Source: Hutton, Graham. "Programming in Haskell" (p. 267)

  1. Show how the Maybe type can be made foldable and traversable, by giving explicit definitions for fold, foldMap, foldr, foldl and traverse.

I did foldr definition. For the purposes of checking my solution, I found online this code:

 -- foldr :: (a -> b -> b) -> b -> Maybe a -> b
    foldr _ _ Nothing = mempty
    foldr f v (Just a) = f a v

It seems the acumulator should be returned in the base case (instead of mempty). Is that right ?

Solution

  • Yes, the code you're looking at is bogus and won't even compile. It should do what you said:

    foldr _ v Nothing = v

    Note that you don't really need to do all this manual work, except as an exercise. You could just write

    {-# language DeriveTraversable #-}
module MyModule where
import Prelude hiding (Maybe (..))
data Maybe a = Nothing | Just a
  deriving (Show, Eq, Ord, Functor, Foldable, Traversable)

    and be done with it. If you don't want to rely on a language extension, then you still only have to write one method: traverse. You can write

    import Prelude hiding (Maybe (..))
import Data.Traversable

data Maybe a = Nothing | Just a deriving (Show, Eq)

instance Foldable Maybe where
  foldMap = foldMapDefault
instance Functor Maybe where
  fmap = fmapDefault
instance Traversable Maybe where
  traverse _ Nothing = _1 -- fill in the blanks
  traverse f (Just a) = _2

    In the case of Maybe, this should produce optimal definitions of all the class methods. For some types, you'll need to write some methods by hand to get optimal results. For example, the default generally won't give a good definition of <$ for recursive types.