module Data.LTree (LTree (..), LForest, unfoldLTree, unfoldLTreeM) where
import Prelude hiding (mapM);
import Control.Applicative;
import Control.Monad hiding (mapM);
import Data.Foldable;
import Data.Traversable;
data LTree v a = Stem (LForest v a) | Leaf a;
type LForest v a = v (LTree v a);
instance (Eq a, Eq (LForest v a)) => Eq (LTree v a) where {
Leaf x == Leaf y = x == y;
Stem ss == Stem ts = ss == ts;
_ == _ = False;
};
instance Functor v => Functor (LTree v) where {
fmap f (Leaf x) = Leaf (f x);
fmap f (Stem ts) = Stem (fmap (fmap f) ts);
};
instance Functor v => Applicative (LTree v) where {
pure x = Leaf x;
(<*>) (Leaf f) (Leaf x) = Leaf (f x);
(<*>) (Leaf f) (Stem ts) = Stem (fmap (fmap f) ts);
(<*>) (Stem ss) t = Stem (fmap (<*> t) ss);
};
instance Foldable v => Foldable (LTree v) where {
foldMap f (Stem ts) = foldMap (foldMap f) ts;
foldMap f (Leaf x) = f x;
};
instance Traversable v => Traversable (LTree v) where {
traverse f (Stem ts) = fmap Stem (traverse (traverse f) ts);
traverse f (Leaf x) = fmap Leaf (f x);
};
unfoldLTree :: Functor v => (b -> Either a (v b)) -> b -> LTree v a;
unfoldLTree f = either Leaf (Stem . fmap (unfoldLTree f)) . f;
unfoldLTreeM :: (Monad m, Traversable v) => (b -> m (Either a (v b))) -> b -> m (LTree v a);
unfoldLTreeM f y = f y >>= either (return . Leaf) (liftM Stem . mapM (unfoldLTreeM f));