-- |
-- Module      : Data.Trees.MTree
-- Copyright   : Rahul Gopinath
-- License     : PublicDomain
-- 
-- Maintainer  : Rahul Gopinath (gopinath@eecs.oregonstate.edu)
-- Stability   : experimental
-- Portability : portable
-- 
-- This Haskell library provides an implementation of a tree data
-- type with meta data in the nodes and content in the leaves.
-- 
module Data.Trees.MTree where

import qualified Data.Bifunctor as Bi
import qualified Data.Bitraversable as Bit
import qualified Data.Traversable as Tr
import qualified Data.Foldable as Fl
import qualified Data.Bifoldable as Bif
import qualified Data.Monoid as Monoid (mappend, mempty, mconcat, Monoid)

import Control.Applicative

-- |
-- | The @MTree m c@ is a tree structure with metadata in the nodes
-- | and metadata and content in the leaves.
data MTree m c = MLeaf { meta :: m,  content :: c }
               | MNode { meta :: m,  trees :: [MTree m c]}
     deriving Show

instance Bi.Bifunctor (MTree) where
  bimap f1 f2 (MLeaf m c) = MLeaf (f1 m) (f2 c)
  bimap f1 f2 (MNode m l) = MNode (f1 m) $ map (Bi.bimap f1 f2) l

instance Bif.Bifoldable MTree where
  bifoldMap f g (MLeaf m c) = f m `Monoid.mappend` g c
  bifoldMap f g (MNode m l) = f m `Monoid.mappend` Fl.foldMap (Bif.bifoldMap f g) l

instance Bit.Bitraversable MTree where
  bitraverse f g (MLeaf m c) = MLeaf <$> f m <*> g c
  bitraverse f g (MNode m l) = MNode <$> f m <*> Tr.traverse (Bit.bitraverse f g) l