A tree implementation in Haskell.

Tree.hs

module Tree where

data Tree a
  = Node [Tree a]
  | Leaf a
  deriving (Eq, Show)

instance Functor Tree where
  f `fmap` Leaf value = Leaf $ f value
  f `fmap` Node children = Node $ fmap (fmap f) children

instance Applicative Tree where
  pure = Leaf
  Leaf f <*> x = f <$> x
  Node trees <*> x = Node $ map (<*> x) trees

instance Monad Tree where
  Leaf value >>= f = f value
  Node children >>= f = Node $ map (>>= f) children

instance Foldable Tree where
  foldr accumulate initial (Leaf value) = accumulate value initial
  foldr accumulate initial (Node children) =
    foldr (flip (foldr accumulate)) initial children

instance Traversable Tree where
  traverse f (Leaf value) = Leaf <$> f value
  traverse f (Node children) = Node <$> traverse (traverse f) children