Foldable を使ってみる。

Data.Foldable
これはData.Foldableにある例ですが、Tree型のFoldableインスタンスを定義することによってFoldableに定義されている関数を使用できるようになります。
Foldableインスタンスを定義するには、foldMap またはfoldrを定義すれば良いらしい。

import Data.Foldable
import Data.Monoid

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) deriving Show

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

--instance Foldable Tree where
--  foldr f z Empty = z
--  foldr f z (Leaf x) = f x z
--  foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l


tree =  (Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5)))

{-
-- mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
> Data.Foldable.mapM_ (\x-> print x) tree
1
2
3
4
5
-}
-- foldrM で使用するための関数です。
-- foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
-- の(a -> b -> m b)の部分に該当する関数。
-- Treeのノードにある数値を表示して、和を求めます。

showAndADD x acc = putStrLn (" x="++ show x) >> return (x + acc)

{-
> foldrM  showAndADD 0 tree
 x=5
 x=4
 x=3
 x=2
 x=1
15

> Data.Foldable.toList tree  -- > [1,2,3,4,5]
> Data.Foldable.minimum tree -- > 1
> Data.Foldable.find (>10) tree -- >Nothing
> Data.Foldable.find (>1) tree -- > Just 2
> Data.Foldable.find (3==) tree -- > Just 3
> Data.Foldable.find (9==) tree -- > Nothing
-}