学習の素材は、
すごいHaskellたのしく学ぼう!
この表記は、私見・感想です。
Monoid
モノイドのインスタンスである とは、値を二項演算子で結合できるような型を指す。
class Monoid a where
mempty :: a
-- ^ Identity of 'mappend'
mappend :: a -> a -> a
-- ^ An associative operation
mconcat :: [a] -> a
-- ^ Fold a list using the monoid.
-- For most types, the default definition for 'mconcat' will be
-- used, but the function is included in the class definition so
-- that an optimized version can be provided for specific types.
mconcat = foldr mappend mempty
モノイド 則
モノイド型クラスのインスタンスは、次のモノイド則を守らなければならない。
mappend mempty x = x
mappend x mempty = x
mappend x (mappend y z) = mappend (mappend x y) z
mconcat = foldr mappend mempty
Haskell が自動的に満たしてくれるルールではなく、プログラマが注意しなくてはならない。このルールを満たしていなくとも、表面上はモノイドのインスタンスとして宣言できるが、利用するとバグの温床となってしまう。
Monoid インスタンス
Monoid のインスタンスには次のようなものがある。
- リスト
- Sum
- Product
- Any
- All
- Ordering
- Monoid a => Maybe a
- First a
- Last a
Maybe モノイド
例えば、Maybe モノイドは、モノイドな型変数を持つ多相型となっている。
instance Monoid a => Monoid (Maybe a) where
mempty = Nothing
Nothing `mappend` m = m
m `mappend` Nothing = m
Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)
単位元( mempty ) は Nothing であり、mappend の左辺または右辺が Nothing の場合は、もう片方の値を採用する。両辺共に Just値であるなら、それぞれの内部的な値( これもモノイドのインスタンス) 同士を mappend する。
失敗するかもしれない計算の値がモノイドのインスタンスであることがわかっているなら、扱う値が
JustかNothingかを気にすることなくmappendすることができる（パターンマッチして場合分けする必要がなくなる）。
なお、中身がモノイドかどうか不明な場合は、First モノイドや Last モノイドを使うことになる。
Ordering モノイド
次に、Ordering モノイドを見てみる。
instance Monoid Ordering where
mempty = EQ
LT `mappend` _ = LT
EQ `mappend` y = y
GT `mappend` _ = GT
単位元はEQ である。またmappend の実装は、左辺がLT または GT の場合は無条件でそれを返す。左辺がEQ の場合は、無条件で右辺を返す。このルールは、辞書式順序( lexicographic order ) と呼ばれている。
最初の比較結果で大小がわかればそれを採用し、等しければ次の比較結果を採用する。"book" と "body" とを比較すると一文字目は 'b' で
EQだが、二文字の'o'と'd'とを比較した結果、GTが返る、といったルールのこと。
また、次のように、比較条件を mappend することができる。
(\x y -> (length x `compare` length y) `mappend` (x `compare` y))
Ordering モノイドを利用すると、優先度の高い比較条件を一番左に持ってきて、以降優先度に従って右辺方向に比較条件をmappend することで複合的な比較条件を扱うことができるようになる。
上のラムダ式では、まず要素数で比較し、その次に辞書式順序で比較を行う操作を行っている。
モノイドを活用して畳み込む
リストだけではなく、いろんなデータ構造を畳み込むことができる。それは、Fodable 型クラスのインスタンスにすること。一番簡単な方法として、、インタフェースとなるfoldMap を実装すれば良い。
F.foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
class Foldable (t :: * -> *) where
foldMap :: Monoid m => (a -> m) -> t a -> m
あるデータ構造をFoldable にしてみる
自作ツリー構造のデータ型を、Foldable インスタンスにしてみる。
data Tree a = EmptyTree
| Node a (Tree a) (Tree a)
deriving (Show)
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)
-- ちなみにFunctor のインスタンスにするにはこのような形
instance Functor Tree where
fmap f EmptyTree = EmptyTree
fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)
この時点では、ある値をモノイド値に変換する関数を定義する必要がない。
foldMap では、引数に与えられる関数をどのように適用してmappendさせるか、という点を定義する。
これで、データ型Tree に対して foldr が使えるようになった。
なお foldMap も、単体で使用できる関数である。例えば次のように、任意のデータ構造をリスト( モノイド )に変換することができる。
Data.Monoid F> F.foldMap (\x -> [x]) $ Node 3 (Node 1 EmptyTree EmptyTree) (Node 100 EmptyTree EmptyTree)
-- [1,3,100] が返る