Binary tree

b-tree.hs

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show

bt = Branch (Leaf 42) (Branch (Leaf 1) (Leaf 2))

fmap' :: (a -> b) -> Tree a -> Tree b
fmap' f (Leaf x) = Leaf (f x)
fmap' f (Branch l r) = Branch (fmap' f l) (fmap' f r)

foldMap' :: Monoid m => (a -> m) -> Tree a -> m
foldMap' f (Leaf x) = f x
foldMap' f (Branch l r) = foldMap' f l `mappend` foldMap' f r

traverse' :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
traverse' k (Leaf x) = Leaf <$> k x
-- traverse' k (Leaf x) = pure Leaf <*> k x
traverse' k (Branch l r) = Branch <$> traverse' k l <*> traverse' k r
-- traverse' k (Branch l r) = pure Branch <*> traverse' k l <*> traverse' k r

instance Functor Tree where
  fmap = fmap'

instance Foldable Tree where
  foldMap = foldMap'

instance Traversable Tree where
  traverse = traverse'