CODEWITHSUNDEEP
classhaskellmonoids
user2999349
user2999349

Reputation: 879

Haskell monoid foldable rose tree

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.

Upvotes: 7

Views: 3187

Answers (4)

vrs
vrs

Reputation: 1982

Although OP says he/she has found the answer, the solution lacks the base case:

instance Foldable Rose where
    fold (a:>[]) = a <> mempty
    fold (a:>b) =  a <> (foldr (<>) mempty (map fold b))

Otherwise an expection about non-exhaustive patterns in function fold will be thrown.

Upvotes: 0

Benjamin Kovach
Benjamin Kovach

Reputation: 3260

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

Upvotes: 5

Petr
Petr

Reputation: 63409

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

Upvotes: 8

user2999349
user2999349

Reputation: 879

It seems like I found the answer to my own question.

Solution:

instance Foldable Rose where
    fold (a:>b) =  a <> (foldr (<>) mempty (map fold b))

Had to first append each of the elements in the list with the head element (and do the same for each of the bound elements to those rose trees), then fold the list together with an non-adjusting element mempty.

Upvotes: 3

Related Questions