blob: 5c0740cd73e2a45f935df0843160b03b2d126df2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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
|
