Two examples of Foldable for mutually recursive datatypes

FoldMutRec.hs

module FoldMutRec where

-- Note: DeriveFoldable could be used, but I am providing
-- hand-written instances to better illustrate the mechanics.

import Data.Monoid

data Forest a = Forest [Tree a]
data Tree a = Node a (Forest a)

instance Foldable Forest where
  foldMap f (Forest ts) = foldMap (foldMap f) ts

instance Foldable Tree where
  foldMap f (Node x ts) = f x <> foldMap f ts

data Even a = Nil | ECons a (Odd a)
data Odd a = OCons a (Even a)

instance Foldable Even where
  foldMap f Nil          = mempty
  foldMap f (ECons x os) = f x <> foldMap f os

instance Foldable Odd where
  foldMap f (OCons x es) = f x <> foldMap f es

-- Example use with monoids from Data.Monoid:
--
-- foldMap (Last . Just) (Node 'f' (Forest [Node 'o' (Forest []), Node 'o' (Forest [])])) = Last { getLast = Just 'o' }
-- foldMap Sum (ECons 1 (OCons 2 Nil)) = Sum { getSum = 3 }