Skip to content

Instantly share code, notes, and snippets.

@lgastako
Created September 17, 2017 05:09
Show Gist options
  • Save lgastako/88818df467a5ded086491fd4d8a8dbac to your computer and use it in GitHub Desktop.
Save lgastako/88818df467a5ded086491fd4d8a8dbac to your computer and use it in GitHub Desktop.
hustle trees
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment