1 files changed, 44 insertions, 0 deletions
diff --git a/Haskell-book/21/instances/src/Tree.hs b/Haskell-book/21/instances/src/Tree.hs
new file mode 100644
index 0000000..5c0740c
--- /dev/null
+++ b/Haskell-book/21/instances/src/Tree.hs
@@ -0,0 +1,44 @@
+module Tree where
+
+import Data.Monoid
+import Test.QuickCheck
+import Test.QuickCheck.Checkers
+import Test.QuickCheck.Classes
+
+-- Solution:
+-- https://www.reddit.com/r/HaskellBook/comments/7w7bqn/ch_21_is_this_a_sane_instance_of_traversable/
+
+data Tree a = Empty
+            | Leaf a
+            | Node (Tree a) a (Tree a)
+            deriving (Eq, Show)
+
+instance Functor Tree where
+    fmap _ Empty = Empty
+    fmap f (Leaf x) = Leaf $ f x
+    fmap f (Node x y z) = Node (fmap f x) (f y) (fmap f z)
+
+-- foldMap is a bit easier and looks more natural, but you can do
+-- foldr too for extra credit.
+instance Foldable Tree where
+    foldMap _ Empty = mempty
+    foldMap f (Leaf x) = f x
+    foldMap f (Node x y z) = (foldMap f x) <> (f y) <> (foldMap f z)
+
+instance Traversable Tree where
+    traverse f Empty = pure Empty
+    traverse f (Leaf x) = Leaf <$> f x
+    traverse f (Node x y z) = Node <$> (traverse f x) <*> (f y) <*> (traverse f z)
+
+instance Arbitrary a => Arbitrary (Tree a) where
+    arbitrary = do
+        x <- arbitrary
+        y <- arbitrary
+        z <- arbitrary
+        frequency [ (1, return Empty)
+                  , (2, return $ Leaf y)
+                  , (3, return $ Node x y z)
+                  ]
+
+instance Eq a => EqProp (Tree a) where
+    (=-=) = eq