Haskell

HaskellのMonoid探検

More than 1 year has passed since last update.

今日は如法会#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 + 35になるように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の第1引数に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

自己準同型な関数と関数合成です。入力と出力の型が同じな関数です。

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

> 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などがわかった


次にしたいこと

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