すごいH本 part81

モノイドで畳み込む

いろいろなデータ構造の上に畳み込みを定義したい時にモノイドは便利。

*Main Lib F> F.foldr (*) 1 [1,2,3]
6
*Main Lib F> F.foldl (+) 2 (Just 9)
11
*Main Lib F> F.foldr (||) False (Just True)
True

もう少し複雑なデータ構造を畳み込んでみてみる

7章で扱った木構造

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

木を Foldable のインスタンスにして畳み込みできるようにする。

foldr を実装しても良いが、もっとかんたんな方法がある。 foldMap 関数を実装すること。 この関数は Foldable 型クラスの一員で、型は次のようになっている。

*Main Lib F> :t foldMap
foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

• 第一引数は、Foldable にしたいコンテナの中身 a の型の値をとって、モノイド値を返す 関数
• 第二引数は、a 型の値を含む Foldable 構造

foldMap はまず、第二引数の構造体に第一引数の関数を map して、構造体の中身をモノイド値に変える 次に、それらのモノイド値を mappend して単一のモノイド値として結合する

foldMap さえあれば、ある型を Foldable にできる。 つまり、foldr, foldl を使うことができるようになる。

Tree を Foldable のインスタンスにする。

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

テスト用の Tree を作る

testTree = Node 5
              (Node 3
                  (Node 1 EmptyTree EmptyTree)
                  (Node 6 EmptyTree EmptyTree)
              )
              (Node 9
                  (Node 8 EmptyTree EmptyTree)
                  (Node 10 EmptyTree EmptyTree)
              )

実行

*Main> F.foldl (+) 0 testTree
42
*Main> F.foldl (*) 1 testTree
64800

foldMap は Foldable インスタンスを定義するためだけにあるのではなく、 Foldable な構造を単一のモノイド値に畳みたいときに便利。

木構造の中に3に等しい数を調べる場合こう書ける

*Main Data.Monoid> getAny $ F.foldMap (\x -> Any $ x == 3) testTree
True

mappend を使って1つのモノイド値に畳んでくれる。

*Main Data.Monoid> getAny $ F.foldMap (\x -> Any $ x > 15) testTree
False

木構造の中のすべてのノード値はラムダ式の中の関数を適用された結果、 Any False に変わる。複数の Any を mappend して True が返るのは、 1つでも True が含まれる場合のみ。

木構造をリストに変換できる技

*Main Data.Monoid> F.foldMap (\x -> [x]) testTree
[1,3,6,5,8,9,10]

これらの例は木構造に限らずあらゆる Foldable なデータ構造に使える

所感

はじめてモノイドが便利に使われている様を観測できて納得感があった。 抽象化とてもおもしろい。

すごいHaskellたのしく学ぼう！