Monoidのこと

Monoid Haskell

昨日のポストで取り上げた変わった型のApplicativeの２つ目：

instance Monoid a => Applicative ( (,) a) where
	pure x = (mempty, x)
	(u, f) <*> (v, x) = (u `mappend` v, f x)

はMonoidが出てきます。今までかかわったことがなかったのですが、定義を見てみた感じでは、なんとなく何を言ってるかわかりそうなので、ここで取り組んでみようと思います。

Monoidのクラス定義は以下のとおり:

class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a

ただし、mconcatはデフォルトのインプリメンテーションがmemptyとmappendを使った形で提供されているので、Monoidのクラスインスタンスを新しく定義する上で必須となるのはmemptyとmappendだけのようです。ちなみに、mconcatのデフォルト定義は:

mconcat = foldr mappend mempty

だそうです...カテゴリー理論は奥が深そうなので、今のところはパスして、あちこち読んだり、試してみた感じでは、Monoid型aは、a->a->a となる関数mappendが存在して、さらに、
mappend mempty x = x
mappend x mempty = x
となるようなmemptyが存在する型aについて定義されているようです…

何言ってんだか、よくわからないわけなんですが、例を挙げれば、整数における＋なんていうのは、(+):: Int -> Int -> Intということで、mappendの条件を満たしていて、それに対応するmemptyは０ということですね…

整数では掛け算も(*)::Int -> Int -> Intですね...この場合のmemptyは１です。
割り算も、小数点以下を切り捨てる(div)::Int->Int->Intなんですが、これに対するmemptyはあるでしょうか？memptyはmappendの第一と第二パラメタのどちらに渡されてももう一つのパラメタの値を買えずに返さなくてはいけないので、`div`に対するmemptyはなさそうです。ということで、`div`を使ったMonoidのクラスインスタンスは作れなさそうです。

ちなみに、Haskellでは＋に関するMonoidのクラスインスタンスはSumという型、＊はProductという型でインプリメントされているようです。

たちかえって、mconcatをみれば、foldr mappendしているわけなので、リストの中身を全てmappendでまとめて一つの値にしているということですね…ためしにサンプルを書いてみると:

module Main
	where
	
import Data.Monoid

toSum a = Sum a
toProd a = Product a

mfold f xs = mconcat $ map fxs

test = do
	print.getSum $ mfold toSum [1, 2, 3, 4, 5]
	print.getProduct $ mfold toProd [1, 2, 3, 4, 5]
	
=>
	15
	120

みたいな感じです。

ほかにもMonoidのクラスインスタンスには：

Monoid All -- (mappend = &&::Bool, mempty = True)
Monoid Any -- (mappend = ||::Bool, mempty = False)
Monoid Ordering
Monoid b => Monoid (a -> b)
Monoid a => Monoid (Dual a)
Monoid (Endo a)
Monoid (First a)
Monoid (Last a)
Monoid a => Monoid (Maybe a)
Monoid [a] -- (mappend = ++, mempty = [])

(Monoid a, Monoid b) => Monoid (a, b) 
(Monoid a, Monoid b, Monoid c) => Monoid (a, b, c)
(Monoid a, Monoid b, Monoid c, Monoid d) 
　　　=> Monoid (a, b, c, d)
(Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) 
　　　=> Monoid (a, b, c, d, e)

ということで、気づくのは、Monoidのクラスインスタンス型を含むタプル（要素数２−５）は、自動的にMonoidのクラスインスタンスになるようです。

あとは、sortWithで使うcompareの返り値でもあるOrderingもMonoidで、

mempty = eq
mappend eq a = a
mappend GT _ = GT
mappend LT _ = LT

と、[x1, x2, x3, x4]であらわせるベクター値のリストをソートしようと思ったら、

module Main
	where

import Data.List
import Data.Monoid

sortVector :: (Ord a) => [ [a] ] -> [ [a] ]
sortVector xs = sortBy (\x y -> 
      mconcat $ zipWith (compare) x y) xs

vector = [ [1, 2, 3, 4], [1, 5, 9, 7], [7, -1, 4, 0], [0, 9, 10, 5] ]
main = print $ sortVector vector

みたいなことができたりします。ちなみに、sortVectorは覚えたてほやほやのApplicativeを使えば：

sortVector :: (Ord a) => [ [a] ] -> [ [a] ]
sortVector xs = sortBy (\x y -> 
      mconcat $ (compare) <$> x <*> y) xs

と書き換えられます。x <$> y は pure x <*> yのショートハンドです。
そのほかを見てみれば、Monoid a => Monoid (Maybe a)というのがあって、

mempty = Nothing
mappend Nothing a = a
mappend a Nothing = a
mappend Just a Just b = Just (mappend a b)

ということで、Nothingの混じったリストの中からJustな値だけをまとめることがmconcat一発でできそうです。

ということで、覚えておくと便利そうですね...

ではでは...