How do I write Foldable instance for this type?

user_637669 0
Viewed 335

I have the following data type defined:

data SynthesisTreeResult comp a = CompNode (comp a) [SynthesisTreeResult comp a]
                                | InputLeaf Location

I want to be able to turn it into a list of type [comp a] using toList, which requires an instance of Foldable.

I tried to write an instance by implementing foldMap:

class Foldable f where
  foldMap :: Monoid m => (a -> m) -> f a -> m

However, since comp :: * -> *, I have to write instance Foldable (SynthesisTreeResult comp) where ..., which causes foldMap to have following type 

foldMap :: Monoid m => (a -> m) -> SynthesisTreeResult comp a -> m

But I need

foldMap :: Monoid m => (comp a -> m) -> SynthesisTreeResult comp a -> m

to be able to fold it.

Is it possible? Maybe I need to impose Functor on comp?

fold typeclass haskell
2 Answers

Thanks to @Willem Van Onsem hint, I figured out the proper instance:

instance Foldable comp => Foldable (SynthesisTreeResult comp) where
  foldMap f (CompNode comp children) = mappend (foldMap f comp) $ mconcat $ map (foldMap f) children
user_6376690

Given your comment that you want a comp a instead of an a, you need to make a minor change to your type:

data SynthesisTreeResult t = CompNode t [SynthesisTreeResult t]
                           | InputLeaf Location

That's necessary because the type that comes out of foldMap is always the last type parameter of the type that went in. Fixing the usages of your type is easy; just change SynthesisTreeResult Foo Bar to SynthesisTreeResult (Foo Bar) everywhere. With that change, here's your Foldable instance:

instance Foldable SynthesisTreeResult where
    foldMap f (CompNode x xs) = f x <> foldMap (foldMap f) xs
    foldMap _ (InputLeaf _) = mempty

If that change to your type isn't acceptable, then you can't use Foldable to get what you want, and you need to write your own toList method, which you could do like this:

myToList :: SynthesisTreeResult comp a -> [comp a]
myToList (CompNode x xs) = x:concatMap myToList xs
myToList (InputLeaf _) = []
user_75090650
Related