Haskell monoid foldable rose tree

Question

I need to make a foldable instance for a Rose tree data structure:

data Rose a = a :> [Rose a]
    deriving (Eq, Show)

With the following monoid and rose-related class/instances:

instance Functor Rose where
    fmap f (a :> bs) = (f a) :> (map (fmap f) bs)

class Monoid a where
    mempty ::           a
    (<>)   :: a -> a -> a

instance Monoid [a] where
    mempty = []
    (<>)   = (++)

What I tried:

instance Foldable Rose where
    fold (a:>b) =  a <> (foldMap fold b)

However this is not working properly, for the system check I get the error:

*** Failed! Exception: 'Prelude.undefined': 
[] :> []

But I'm not sure why it doesn't work, could anyone help me out?

Thanks in advance!

Best Regards, Skyfe.

Answer 1

Your implementation of fold was correct, there is no reason to change it.

The problem is that fold isn't sufficient to define Foldable. From the documentation:

class Foldable t where Source

Data structures that can be folded.

Minimal complete definition: foldMap or foldr.

So you must define either foldMap or foldr (or both). Defining foldMap is easier and more natural (and also more effective in many cases). So you should write something like:

import Data.Foldable
import Data.Monoid

data Rose a = a :> [Rose a]
    deriving (Eq, Show)

instance Foldable Rose where
    foldMap f (x :> xs) = f x <> foldMap (foldMap f) xs

Answer 2

This is only tangentially related, but if you realize that Rose Trees are the same as Cofree [] from Control.Comonad.Cofree, then you can get a Foldable instance "for free" from the foldable instance of [] like so:

import Control.Comonad.Cofree
import Data.Foldable as F

type RoseTree = Cofree []

Load it up into GHCi:

λ> let tree = 1 :< [1 :< [], 2 :< [], 3 :< []] :: RoseTree Int
λ> :t F.foldr (+) 0 tree
F.foldr (+) 0 tree :: Int
λ> F.foldr (+) 0 tree
7

You can also just derive Foldable, or write your own implementation (like you've done).