# 加總樹的節點值

``````data Tree a = EmptyTree | Node a (Tree a) (Tree a)

singleNode :: a -> Tree a
singleNode x = Node x EmptyTree EmptyTree

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = singleNode x
insert x (Node a l r)
| x == a = Node x l r
| x < a  = Node a (insert x l) r
| x > a  = Node a l (insert x r)

fromList :: Ord a => [a] -> Tree a
fromList [] = EmptyTree
fromList (x:xs) = insert x \$ fromList xs

node :: (Ord a) => a -> Tree a -> Bool
node x EmptyTree = False
node x (Node a l r)
| x == a = True
| x < a  = node x l
| x > a  = node x r

toList :: Tree a -> [a]
toList EmptyTree = []
toList tree = con [] tree
where
con lt EmptyTree = lt
con lt (Node a l r) = con r (a : (con l lt))

instance Show a => Show (Tree a) where
show tree = "fromList " ++ (show . toList) tree
``````

``````sumTree :: Tree Integer -> Integer
sumTree tree = sumIt 0 tree
where
sumIt init EmptyTree = init
sumIt init (Node a l r) = sumIt (a + (sumIt init l)) r
``````

``````foldTree :: (a -> b -> a) -> a -> Tree b -> a
foldTree _ z EmptyTree = z
foldTree f z (Node a l r) = foldTree f (f preZ a) r
where preZ = foldTree f z l
``````

``````toList :: Tree a -> [a]
toList tree = foldTree (\z a -> a : z) [] tree

sumTree :: Tree Integer -> Integer
sumTree tree = foldTree (+) 0 tree
``````

# Foldable Typeclass

`foldTree` 看起來很像可以處理 List 的 `foldl`（也就是定義在 `Data.List` 中的 `foldl`），實際上，如果折疊樹時是從右子樹開始，實作出來的就像是可處理 List 的 `foldr` 了，看來可以折疊的並不只有 List，對於可折疊的行為，Haskell 在 `Data.Foldable` 模組中定義了 `Foldable` 這個 Typeclass。

`Data.Foldable` 模組中也有定義 `foldl` 等函式，先來看看看它們的型態與使用方式：

``````import Prelude hiding (foldr)
import Data.Foldable hiding (toList)

...

instance Foldable Tree where
foldr _ z EmptyTree = z
foldr f z (Node a l r) = foldr f (f a preZ) l
where preZ = foldr f z r
``````

# Monoid Typeclass

``````instance Monoid [a] where
mempty  = []
mappend = (++)
``````

``````instance Foldable Tree where
foldMap f EmptyTree = mempty
foldMap f (Node x l r) =
(foldMap f l) `mappend` (f x) `mappend` (foldMap f r)
``````