読者です 読者をやめる 読者になる 読者になる

はわわーっ

はわわわわっ

二分木を折り畳む

haskell

Haskell で二分木(http://ja.wikipedia.org/wiki/二分木)を作ってみる。

data BTree a = Empty | Node a (BTree a) (BTree a) deriving Show

二分木の例。

tree :: BTree Int
tree = Node 3 (Node 1 (Node 4 Empty Empty)
                      (Node 7 Empty Empty))
              (Node 6 (Node 2 Empty Empty)
                      (Node 5 Empty Empty))

で、これを Foldable(Data.Foldable) にしてみる。Data.Foldable には foldl とか Prelude と同じ名前の関数があるので as 付きで import する。あと、Foldable を使うときは Monoid も必要みたい。

import Data.Foldable as F
import Data.Monoid

instance F.Foldable BTree where
  foldMap f Empty = mempty
  foldMap f (Node x lt rt) = F.foldMap f lt `mappend`
                             f x `mappend`
                             F.foldMap f rt

二分木を折り畳む。

> F.foldr (+) 0 tree
28
> F.foldr (:) [] tree
[4,1,7,3,2,6,5]
> F.foldr (const (+1)) 0 tree
7

こんな感じに使える。