Haskellにおけるモノイド, Foldable, Traversable覚書
勤め先で毎週行っている関数型プログラミング勉強会のまとめです。 参考書籍として「プログラミングHaskell第2版」を使っており、今回は14章についてまとめました。 Haskellで実装されてる概念と数学上の概念の対応がわかってくると嬉しくなりますね。
モノイド
集合が「集合の二つの要素を結びつける結合的な演算子」と「その演算子に対する単位元」を持つとき、その代数的構造をモノイドと呼ぶ
-- Haskellにおける型クラス宣言 -- モノイドの概念の抽象化 class Monoid a where -- 単位元 mempty :: a -- 演算子 mappend :: a -> a -> a mconcat :: [a] -> a mconcat :: foldr mappend mempty -- 単位元と演算子が満たさなければならない則（モノイド則） mempty `mappend` x = x x `mappend` mempty = x x `mapppend` (y `mappend` z) = (x `mappend` y) `mappend` z
mempty, mappendといった命名から、空のもの、追加に関する演算子を連想するが、２つのメソッドは、あくまで「モノイド則」を満たしていれば良い。
Foldable
リストに対する畳込関数の考え方を、型変数をもつ型へと拡張したもの
モノイドを使用して、あるデータ構造の中にある全ての値を１つにまとめるという作業がよく行われる
例えば、リストの場合(他にはTreeなどが紹介されていた)
-- リストの中の値を１つにまとめる関数 -- 空リストにfoldを適用すると、モノイドの単位元memptyとなる -- 空でないリストでは、「リストの先頭」と「残りのリストを再帰的に処理した結果」をmappendで連結する -- ※Monoidなのはリストの要素であり、リスト自体ではないため注意 fold :: Monoid a => [a] -> a fold [] = mempty fold (x:xs) = x `mappend` fold xs
「データ構造の中の値をモノイドを使って畳み込む操作」は、リストやTreeだけでなく、型引数をもつ型全般に対して抽象化できる -> この抽象化はFoldableと呼ばれる
class Foldable t where fold :: Monoid a => t a -> a -- リストの中の値を１つに畳み込むイメージ foldMap :: Monoid b => (a -> b) -> t a -> b -- リストの中の値に一つずつ関数を適用し、その結果を畳み込んで１つの値にするイメージ -- リスト用高階関数の一般化、初期値と二つの値を連結する関数を引数として明示的に渡すので、モノイドに関する制約はない foldr :: (a -> b -> b) -> b -> t a -> b foldl :: (a -> b -> a) -> a -> t b -> a
また、Foldableクラスではデータ構造の中の値を処理するためのメソッドがたくさん提供されている（null, length, elem ...etc）
特に、データ構造を平坦化しリストへ変換するメソッドtoListは、リスト向けのメソッドを流用して実装を与えるために便利（Foldableのデフォルト実装にも使われている）
-- toList :: t a -> [a] -- いくつか例 null = null . toList length = length . toList maximum = maximum . toList sum = sum . toList
Foldableに抽象化することの利点は、Foldableクラスのメソッドを使って、Foldableであれば何にでも使える汎用的な関数を定義可能になったこと
-- リスト構造の中の値の平均を求める関数をFoldableに抽象化 average :: Foldable t => t Int -> Int average ns = sum ns `div` length ns -- 上記関数は、（Foldable型クラスのインスタンスである）リストと木の両方に適用できる > average [1..10] 5 > average (Node (Leaf 1) (Leaf 3)) 2
Traversable
あるデータ構造を走査するという考え方を抽象化したもの
class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
Traversableである型tが関手であるという制約は、Traversableが変換の概念を一般化したものであり、fmapが提供されているという事実を反映している（関手はデータ構造の中の各要素に関数を適用していくという考え方の抽象化） また、型tがFoldableであるという制約から、Traversableの値は必要に応じて畳み込めることが保証されている
まとめ
個人的にこの章は結構読みやすく、プログラミングにおいて広く一般的な概念（畳み込み、データの走査）を抽象化してみるという考え方にワクワクしました。まだ練習問題を解いていないので、これからじっくり問題に向き合っていこうと思います。
頑張ろう。
