HaskellのMonoid探検

今日は如法会#4です。ということで、モノイドを探検することにしました。

なぜモノイドを探検をするかというとfoldMapを使いこなしたいからです。

環境

• ghc 7.10.3

モノイドの一覧

まず、Haskellで使えるMonoidを確認してみます。

> import Data.Monoid
> :i Monoid
class Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a
  	-- Defined in ‘GHC.Base’
instance Num a => Monoid (Sum a) -- Defined in ‘Data.Monoid’
instance Num a => Monoid (Product a) -- Defined in ‘Data.Monoid’
instance Monoid (Last a) -- Defined in ‘Data.Monoid’
instance Monoid (First a) -- Defined in ‘Data.Monoid’
instance Monoid (Endo a) -- Defined in ‘Data.Monoid’
instance Monoid a => Monoid (Dual a) -- Defined in ‘Data.Monoid’
instance Monoid Any -- Defined in ‘Data.Monoid’
instance GHC.Base.Alternative f => Monoid (Alt f a)
  -- Defined in ‘Data.Monoid’
instance Monoid All -- Defined in ‘Data.Monoid’
instance Monoid [a] -- Defined in ‘GHC.Base’
instance Monoid Ordering -- Defined in ‘GHC.Base’
instance Monoid a => Monoid (Maybe a) -- Defined in ‘GHC.Base’
instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) =>
         Monoid (a, b, c, d, e)
  -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b, Monoid c, Monoid d) =>
         Monoid (a, b, c, d)
  -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b, Monoid c) => Monoid (a, b, c)
  -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b) => Monoid (a, b)
  -- Defined in ‘GHC.Base’
instance Monoid () -- Defined in ‘GHC.Base’

instanceで始まる部分のMonoidと書かれてるところの右側に注目します。
(ただし、=>がはいっている行は=>の右側に着目します

• Sum a
• Product a
• Last a
• First a
• Endo a
• Dual a
• Any
• Alt f a
• All
• [a]
• Ordering
• Maybe a
• a -> b
• (a, b, c, d, e)
• (a, b, c, d)
• (a, b, c)
• (a, b)
• ()

いろんなモノイドがいますね。

Sum

Sumは数と+のことらしいです。

Sumの元をつくってみます。

> Sum 1
Sum {getSum = 1}

> Sum 2
Sum {getSum = 2}

モノイドには単位元があります。Sum Intの単位元はSum { getSum = 0}になります。memptyで取得できます。

以下の方法でもつくれました

> 1 :: Sum Int
Sum {getSum = 1}

> mempty :: Sum Int
Sum {getSum = 0}

モノイドは元と元を演算できるらしいです。演算するにはmappendを使います。

> Sum 2 `mappend` Sum 3
Sum {getSum = 5}

2 + 3が5になるようにSum 5になりました。

モノイドが便利なのはmconcatです。単位元とmappendがあることと結合律があるからつかうことができます。

> mconcat [Sum 1, Sum 2, Sum 3, Sum 4]
Sum {getSum = 10}

sum [1, 2, 3, 4]が10になるようにSum 10になりました。

以下のようにもかけます。

> mconcat [1, 2, 3, 4] :: Sum Int
Sum {getSum = 10}

しかし、mconcatのはリストにしかつかえないです。

> :t mconcat
mconcat :: Monoid a => [a] -> a

mconcatをリスト以外でも使えるようにしたData.Foldbale.foldがあります。

> Data.Foldable.fold [Sum 1, Sum 2, Sum 3, Sum 4]
Sum {getSum = 10}

> import Data.Tree
> let tree = Node 1 [Node 2 [], Node 3 [Node 4 []]]
Node {rootLabel = 1, subForest = [Node {rootLabel = 2, subForest = []},Node {rootLabel = 3, subForest = [Node {rootLabel = 4, subForest = []}]}]}
> Data.Foldable.fold tree :: Sum Int
Sum {getSum = 10}

Foldableな構造をしていればすべての要素の和がとれます。
FoldableにはtoListがあるので以下のようにかいても同じようにうごきます。

> mconcat $ Data.Foldable.toList tree :: Sum Int
Sum {getSum = 10}

:: Sum Intと書くのも少し面倒ですね。foldMapを使うとfoldする前に値を調整できるので、SumをつかってSum Intに変換することもできます。

> foldMap Sum tree
Sum {getSum = 10}

foldはfoldMapの第１引数にidを指定しているとも考えられそうです。

> foldMap id tree :: Sum Int
Sum {getSum = 10}

foldMapはfoldすることができる型に変換してfoldしてくれるのでfoldMapを使いこなすにはどんなモノイドがあるのか知っておくのが重要そうです。

Product

掛け算です。

> mconcat [1, 2, 3, 4] :: Product Int
Product {getProduct = 24}

Last

Nothingが混ざる場合の最後の値が取り出せます。

> mconcat [Last $ Just 1, Last $ Just 2]
Last {getLast = Just 2}

> mconcat [Last $ Just 1, Last $ Just 2, Last Nothing]
Last {getLast = Just 2}

Lastかくのつらい。

> foldMap Last [Just 1, Just 2, Nothing]
Last {getLast = Just 2}

単位元はNothingです。

mempty ::  Last Int
Last {getLast = Nothing}

First

Lastの逆です。

> foldMap First [Just 1, Just 2, Nothing]
First {getLast = Just 1}
``'

foldMap First [Nothing, Just 1, Just 2]
First {getLast = Just 1}

# Endo

[自己準同型](https://ja.wikipedia.org/wiki/%E8%87%AA%E5%B7%B1%E6%BA%96%E5%90%8C%E5%9E%8B)な関数と関数合成です。入力と出力の型が同じな関数です。

関数をくっつけてあとで使えます。

let a = foldMap Endo [(+3), (*2)]
appEndo a $ 1 -- 1 * 2 + 3
5
appEndo a $ 2 -- 2 * 2 + 3
7

# Dual

入れ替えができます。

let a = foldMap (Dual . Endo) [(+3), (*2)]
appEndo (getDual a) 1 - (1 + 3) * 2
8
appEndo (getDual a) 2 -- (2 + 3) * 2
10

# Any

真偽値と`||`です。

foldMap Any [False, True]
Any {getAny = True}

foldMap Any [True, True]
Any {getAny = True}

foldMap Any [False, False]
Any {getAny = False}

mempty :: Any
Any {getAny = False}

# Alt

まだしらべてない

# All


真偽値と`&&`です。

foldMap All [False, True]
All {getAll = False}

foldMap All [True, True]
All {getAll = True}

foldMap All [False, False]
All {getAny = False}

mempty :: All
All {getAny = True}

# [A]

リストと`++`です。

mconcat [[1], [2,3]]
[1, 2, 3]

mempty :: [a]
[]

# Ordering

比較の結果で演算はなんというものなのかよくわからない。
EQ以外の左側の結果が優先されます。全部EQならEQになります。
辞書順比較と考えるとよい。

mconcat [EQ, GT, LT]
GT

mconcat [EQ, EQ, EQ]
EQ

mconcat [EQ, LT, GT]
LT

mempty
EQ

# Maybe a

aはモノイドである必要があります。
Nothingが無視できる感じ

mconcat [Just $ Sum 2, Nothing, Just $ Sum 3]
Just (Sum {getSum = 5})

mconcat [Just $ Product 2, Nothing, Just $ Product 3]
Just (Product {getProduct = 6})

mempty :: Mabye Sum Int
mempty :: Maybe (Sum Int)
Nothing

# a -> b

まだかいてない。

# (a, b, c, d, e), (a, b, c, d), (a, b, c), (a, b)

同時に複数のモノイドをまとめて処理できます。

mconcat [(Sum 2,Product 2,[], EQ),(Sum 3,Product 3, [3], GT)]
(Sum {getSum = 5},Product {getProduct = 6},[3],GT)

(Sum {getSum = 0},Product {getProduct = 1},[],EQ)

# ()

単位元しかない。

mconcat [(), (), ()]
()

# 感想

## やったこと

またひとつプログラミングの視野が広がったとおもいます。
モノイドの結合律って並行に処理できるってところとかは表現できてないですが、そういったところも見えたりしました。

* モノイドについて考えた
* 実際にHaskellでつかえるモノイドをさわってみた

## わかったこと

* foldMap, Foldable, fold, mconcatなどがわかった

## 次にしたいこと

その他の代数関連のものをさわってみる