From 98329e0a3dd4f78b5d815ac3896272ec70904901 Mon Sep 17 00:00:00 2001
From: Eugen Wissner <belka@caraus.de>
Date: Thu, 11 Dec 2025 10:28:11 +0100
Subject: Add remaining haskell book exercises

---
 Haskell-book/21/instances/src/Tree.hs | 44 +++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
 create mode 100644 Haskell-book/21/instances/src/Tree.hs

(limited to 'Haskell-book/21/instances/src/Tree.hs')

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
-- 
cgit v1.2.3