1 {-# LANGUAGE GeneralizedNewtypeDeriving #-}
7 | Node (Tree a) a (Tree a)
11 leaf x = Node Empty x Empty
13 treeSize :: Tree a -> Integer
15 treeSize (Node l _ r) = 1 + treeSize l + treeSize r
17 treeSum :: Tree Integer -> Integer
19 treeSum (Node l x r) = x + treeSum l + treeSum r
21 treeDepth :: Tree a -> Integer
23 treeDepth (Node l _ r) = 1 + max (treeDepth l) (treeDepth r)
25 flatten :: Tree a -> [a]
27 flatten (Node l x r) = flatten l ++ [x] ++ flatten r
30 -- 0. empty case value
31 -- 1. type of the return value.
32 -- 2. how to combine the recursive calls.
34 treeFold :: b -> (b -> a -> b -> b) -> Tree a -> b
35 treeFold e _ Empty = e
36 treeFold e f (Node l x r) = f (treeFold e f l) x (treeFold e f r)
38 treeSize' :: Tree a -> Integer
39 treeSize' = treeFold 0 (\l _ r -> 1 + l + r)
41 treeSum' :: Tree Integer -> Integer
42 treeSum' = treeFold 0 (\l x r -> x + l + r)
44 treeDepth' :: Tree a -> Integer
45 treeDepth' = treeFold 0 (\l _ r -> 1 + max l r)
47 flatten' :: Tree a -> [a]
48 flatten' = treeFold [] (\l x r -> l ++ [x] ++ r)
51 newtype Sum' a = Sum' a
52 deriving (Eq, Num, Ord, Show)
57 instance Num a => Monoid (Sum' a) where
61 newtype Prod' a = Prod' a
62 deriving (Eq, Num, Ord, Show)
64 getProd :: Prod' a -> a
67 instance Num a => Monoid (Prod' a) where
72 lst = [1,5,8,23,423,99]
75 prod = getProd . mconcat . map Prod' $ lst