hustle trees

trees.hs

module TreeFolds where

data Tree a
  = Leaf a
  | Branch (Tree a) (Tree a)
  deriving (Eq, Ord, Read, Show)

instance Foldable Tree where
  foldMap f (Leaf a)     = f a
  foldMap f (Branch l r) = foldMap f l `mappend` foldMap f r

data Tree2 a
  = Leaf2 a
  | Branch2 (Tree2 a) (Tree2 a)
  deriving (Eq, Ord, Read, Show)

instance Foldable Tree2 where
  foldMap f (Leaf2 a)     = f a
  foldMap f (Branch2 l r) = foldMap f r `mappend` foldMap f l

family :: Tree String
family = Branch (Branch (Leaf "aa") (Leaf "bb")) (Branch (Leaf "cc") (Leaf "dd"))

family2 :: Tree2 String
family2 = Branch2 (Branch2 (Leaf2 "aa") (Leaf2 "bb")) (Branch2 (Leaf2 "cc") (Leaf2 "dd"))

folds1 :: (String, String)
folds1 = (foldl (++) "" family, foldr (++) "" family)
-- ("aabbccdd","aabbccdd")

folds2 :: (String, String)
folds2 = (foldl (++) "" family2, foldr (++) "" family2)
-- ("ddccbbaa","ddccbbaa")