Monoid_Haskell ノート 9

一.幺元

数学の世界では、0 は加法単位元、1 は乗法単位元（identity element）です。例えば：

> 0 + 3
3
> 3 + 0
3
> 1 * 3
3
> 3 * 1
3

両者の共通点は演算に参加するが、もう一方の操作数を変更しないことです：

In mathematics, an identity element or neutral element is a special type of element of a set with respect to a binary operation on that set, which leaves other elements unchanged when combined with them.

（Identity element から引用）

単位元は集合内の二項演算で定義され、単位元と結合して演算する時、他の要素は不変です（演算結果仍是該要素）。左単位元（e * a = a）と右単位元（a * e = a）に細分され、同時に満足すれば単位元と呼ばれ、幺元とも呼ばれます（離散数学でこれを学びました）

Haskell にも類似のものがあります（Monoid と呼ばれる）。例えば ++ 演算が [] に遭遇する場合：

> [] ++ "abc"
"abc"
> "abc" ++ []
"abc"

++ は List 上で定義された二項演算で、[] は幺元の性質に合致します

二.Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

（Monoid から引用）

幺半群（monoid）は抽象代数中の概念で、結合可能な二項演算と幺元を持つ代数構造を指します。正規（厳密）な記述は以下の通り：

幺半群は二項演算 *: M × M → M を持つ集合 M で、以下の公理に合致します： 結合律：M 内の任意の a、b、c に対して、(a*b)*c = a*(b*c) 幺元：M 内の要素 e が存在し、M 内の任意の a が a*e = e*a = a に合致する

（幺半群 から引用）

結合律に従う二項関数と、その関数の幺元となる値の 2 つで Monoid を構成します

Monoid typeclass

Data.Monoid モジュールに位置：

class Semigroup a => Monoid a where
    mempty  :: a
    mappend :: a -> a -> a
    mappend = (<>)
    mconcat :: [a] -> a
    mconcat = foldr mappend mempty

（GHC.Base から引用）

P.S. 注意、(<>) は Semigroup クラスで定義され、mappend = (<>) は mappend と <> が完全に等価であることを宣言

Monoid（幺半群）はまず Semigroup（半群、詳細は最後の部分を参照）である必要があります。その中で mempty は幺元、mappend はその二項関数です

mappend は幺半群の定義で要求される結合律に従う二項関数で、名前があまり適切ではありません（append を含んでいますが、append に類似した動作を実装する必要があるわけではありません）。2 つの monoid 値を受け取り、別の monoid 値を返します

mconcat は monoid 値のリストを受け取り、mappend で畳み込み（fold、または reduce 規約）して 1 つの monoid 値にします。デフォルト実装が与えられており、一般に自分で実装する必要はありません。より適切な実装方式（例えば効率の高い方式）がある場合を除きます

Monoid laws

Monoid クラスもいくつかのルールに従う必要があります。以下の通り：

mempty `mappend` x = x
x `mappend` mempty = x
(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

前 2 条は mempty が幺元であることを保証し、第 3 条は二項関数 mappend が結合律を満たすことを説明

三.Monoid instances

List

instance Semigroup [a] where
  (<>) = (++)

instance Monoid [a] where
  mempty  = []
  mconcat xss = [x | xs <- xss, x <- xs]

（GHC.Base から引用）

私たちが思った通り、List および List 上で定義された ++ 演算と空 List 幺元で、幺半群を構成します

Monoid laws で検証してみましょう：

> mempty `mappend` "hoho"
"hoho"
> "hoho" `mappend` mempty
"hoho"
> "a" `mappend` "b" `mappend` "c"
"abc"
> "a" `mappend` ("b" `mappend` "c")
"abc"

mempty は幺元で、mappend も結合律を満たすため、List は合格の Monoid インスタンスです

P.S. mempty が具体的に何かを知りたい場合、このようにします：

> mempty :: [a]
[]
> mempty :: Ordering
EQ
> mempty :: ()
()

注意、mempty に具体的なタイプ（例えば [a] または [Int] :: *、[] :: * -> * ではない）を指定する必要があります

Product と Sum

冒頭の幺元部分で加法単位元と乗法単位元に言及しました。同時にそれらも結合律を満たすため、数値演算には 2 つの幺半群が存在します。それぞれ加法と幺元 0、および乗法と幺元 1 です

言い換えれば、Num には 2 種類の異なる Monoid 実装が存在できます。それぞれ二項関数 + と幺元 0、および二項関数 * と幺元 1 です。またこの種のシーンに直面したため、ZipList を作成したように、Sum と Product クラスを作成しました（Data.Monoid に位置）：

newtype Product a = Product { getProduct :: a }
  deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)
newtype Sum a = Sum { getSum :: a }
    deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)

P.S. ZipList と newtype の過去については、[newtype_Haskell ノート 8](/articles/newtype-haskell ノート 8/) を参照

Product の Monoid 実装は以下の通り：

instance Num a => Semigroup (Product a) where
  (<>) = coerce ((*) :: a -> a -> a)

instance Num a => Monoid (Product a) where
  mempty = Product 1

幺元は Product 1、二項関数は coerce ((*) :: a -> a -> a) です。その中で coerce はタイプ変換に使用されます（詳細は Data.Coerce を参照）。以下に相当：

Product x `mappend` Product y = Product (x * y)

Num 上で定義されているため、幺元の値は具体的なタイプに関係します：

> getProduct (mempty :: (Product Int))
1
> getProduct (mempty :: (Product Double))
1.0

Sum の実装は Product と類似：

instance Num a => Semigroup (Sum a) where
  (<>) = coerce ((+) :: a -> a -> a)

instance Num a => Monoid (Sum a) where
  mempty = Sum 0

試玩してみましょう：

> getSum $ Sum 3 `mappend` (mconcat $ map Sum [1, 2, 3])
9

Any と All

Num と類似で、Bool 値にも 2 つの幺半群が存在：|| 演算と幺元 False、&& 演算と幺元 True：

-- ||演算と幺元 False
newtype Any = Any { getAny :: Bool }
  deriving (Eq, Ord, Read, Show, Bounded, Generic)

instance Semigroup Any where
  (<>) = coerce (||)

instance Monoid Any where
  mempty = Any False

-- &&演算と幺元 True
newtype All = All { getAll :: Bool }
  deriving (Eq, Ord, Read, Show, Bounded, Generic)

instance Semigroup All where
  (<>) = coerce (&&)

instance Monoid All where
  mempty = All True

Any と All も同様に Data.Monoid に位置

Ordering

Ordering タイプ定義は非常に簡単：

data Ordering = LT | EQ | GT

対応する Monoid 実装は以下の通り：

instance Semigroup Ordering where
  LT <> _ = LT
  EQ <> y = y
  GT <> _ = GT

instance Monoid Ordering where
  mempty             = EQ

P.S. 前面で言及した其它 Monoid instances と異なり、ここの mappend は新規作成で、既存関数を直接使用したわけではありません（以前は既存関数で検証し、幺半群特性があるか確認）

この関数の動作は、演算結果は左側の操作数を取りますが、左側が EQ の場合を除きます（此时は右側を取る）。少し奇妙に見えますが、文字列（辞書順）比較と理解できます。例えば compare "ab" "am" の比較結果は LT、LT <> _ = LT は現在の比較結果が LT の場合、続けて後ろを比較しても結果仍是 LT であることを意味。例えば compare "absolute" "america"。類似で、EQ <> y = y は現在の結果が EQ の場合、残りの部分の比較結果が最終結果であることを示し、GT <> _ = GT は現在の結果が GT の場合、後面が何であれ、最終結果は必ず GT であることを示

Maybe

instance Semigroup a => Semigroup (Maybe a) where
  Nothing <> b       = b
  a       <> Nothing = a
  Just a  <> Just b  = Just (a <> b)

instance Semigroup a => Monoid (Maybe a) where
  mempty = Nothing

P.S. 注意 ここのタイプ制約で、a が Semigroup であることを要求。Just a <> Just b = Just (a <> b) が正常に演算できることを保証するため

したがって、Maybe の幺元は Nothing、演算も新規作成ですが、比較的巧みで、2 つの Just a の演算結果は内容に対して演算し、再び Just に装入。したがって内容もこの種の演算（<>）をサポートする必要があります。例えば：

> Just (Sum 2) `mappend` Just (Sum 3)
Just (Sum {getSum = 5})
> Just [1, 2] `mappend` Just [3, 4]
Just [1,2,3,4]

内容が <> 演算をサポートしない場合、Maybe の演算を行えません：

> Just 2 `mappend` Just (3 :: Int)

<interactive>:195:1: error:
    ? No instance for (Monoid Int) arising from a use of 'mappend'

四.Foldable と Monoid

Monoid インスタンスはすべて mappend 動作をサポートし、「重ね合わせ」と理解できます。2 つの Monoid インスタンスを演算を通じて 1 つの Monoid インスタンスにします。さらに、「畳み込み」（mconcat）もサポート。一組の Monoid インスタンスを頭から尾まで「重ね合わせ」、从而「畳み込み」して 1 つの Monoid インスタンスにできます

一組のものが「畳み込み」できて 1 つのものになれ、このものは「畳み込み可能」、即ち Foldable：

class Foldable t where
  {-# MINIMAL foldMap | foldr #-}
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b

（Data.Foldable から引用）

P.S. Foldable は Data.Foldable モジュールに位置。関数名は Prelude 中の List 関数名と衝突するため、一般に別名を通じて導入。例えば：

import qualified Data.Foldable as Foldable

class 定義によると、foldMap または foldr を実装するだけで Foldable インスタンスになれます。タイプ宣言から見ると、foldMap は明らかに Monoid 面向で、foldr はより一般的な fold インターフェース

具体的に見ると、foldMap が行うことは関数 a -> m で Foldable 構造（t a）をマッピングし、内容が一組の Monoid で組成された Foldable 構造を得て、再び mconcat（または mappend）を通じてこの一組の Monoid を畳み込んで 1 つの Monoid にして返

実際応用

Foldable を実装する実際的な意義は何でしょうか？例を見：

module BTree
( Tree(..)
, singleton
, add
, fromList
) where

import Data.Monoid
import Data.Foldable

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

singleton x = Node x EmptyTree EmptyTree

add x EmptyTree = singleton x
add x (Node a left right)
  | x == a = Node a left right
  | x > a = Node a left (add x right)
  | x < a = Node a (add x left) right

fromList xs = foldr add EmptyTree xs

これはカスタマイズした二叉樹タイプ（実際には二叉検索樹で、最も単純粗暴なもの。とりあえず二叉樹として使用）。基本的な二叉樹構築機能（singleton、add と fromList）を持ち、それに Monoid インターフェースを実装：

instance Monoid a =>  Monoid (Tree a) where
  mempty = EmptyTree
  a `mappend` EmptyTree = a
  EmptyTree `mappend` b = b
  (Node x xl xr) `mappend` (Node y yl yr) = Node (x `mappend` y) (xl `mappend` yl) (xr `mappend` yr)

注意、Tree a の a も Monoid インスタンスであることを要求。Node の内容に対して mappend を行う必要があるため。前面で言及した Maybe の Monoid 実装と類似

Monoid laws を試：

> let nodeA = Node (Sum 1) (singleton (Sum 2)) EmptyTree
> let nodeB = Node 5 (Node 3 (singleton 1) (singleton 6)) (Node 9 (singleton 8) (singleton 10))
> let nodeC = singleton (Sum 6)
> nodeA `mappend` nodeB `mappend` nodeC
Node (Sum {getSum = 12}) (Node (Sum {getSum = 5}) (Node (Sum {getSum = 1}) EmptyTree EmptyTree) (Node (Sum {getSum = 6}) EmptyTree EmptyTree)) (Node (Sum {getSum = 9}) (Node (Sum {getSum = 8}) EmptyTree EmptyTree) (Node (Sum {getSum = 10}) EmptyTree EmptyTree))
> nodeA `mappend` (nodeB `mappend` nodeC)
Node (Sum {getSum = 12}) (Node (Sum {getSum = 5}) (Node (Sum {getSum = 1}) EmptyTree EmptyTree) (Node (Sum {getSum = 6}) EmptyTree EmptyTree)) (Node (Sum {getSum = 9}) (Node (Sum {getSum = 8}) EmptyTree EmptyTree) (Node (Sum {getSum = 10}) EmptyTree EmptyTree))

3 本の木の構造は以下の通り：

-- nodeA
1
  2
  空
-- nodeB
5
  3
    1
    6
  9
    8
    10
-- nodeC
6

mappend 結果：

12
  5
    1
    6
  9
    8
    10

実際には対応位置で求和。空ノードが 0 の役割を果た。思い出、私たちがどのように「求和」という意図を表現したか？

「求和」は Sum という Monoid インスタンスを通じて表現。Tree は単なる構造。数値が先に Sum で 1 層包まれ、求和のセマンティクスを添え、再び Tree に填入。樹の構造意味を持つ。好像、有那么点意思了

続き、Foldable インターフェースを実装。Foldable と Monoid の関係が親密なことを覚えていれば、一類の Monoid インスタンスを foldable にするのは容易：

instance Foldable.Foldable Tree where
  foldMap f EmptyTree = mempty
  foldMap f (Node x l r) = Foldable.foldMap f l `mappend`
                              f x `mappend`
                              Foldable.foldMap f r

大招蓄力完了。先に起手式：

let tree = fromList [7, 3, 1, 2, 6, 9, 8, 5]
> getAny $ Foldable.foldMap (\x -> Any $ x == 3) tree
True

このような木を作成：

-- tree
5
  2
    1
    3
  8
    6
      空
      7
    9

一言で包含性判断を完成：getAny $ Foldable.foldMap (\x -> Any $ x == 3) tree。出招が速すぎて看清えない？スローモーションで分解：

0. マッピング関数 (\x -> Any $ x == 3) が入力値と 3 の相等性を比較し、比較結果を Any に装入

1. 底から上に tree をトラバース。マッピング関数で各ノード上の数値を変換。空ノードに遭遇すれば mempty に包み、Monoid 木（Any 木）を形成

2. Any 木を畳み込み。具体的には底から上に「左 mappend 中 mappend 右」演算を行う。Any の mappend は値に対して或演算（||）。mempty に遭遇すれば Any False に対応。樹根に走到時、演算結果は Any True

3. getAny で畳み込み結果 True を取出

P.S. 注意、Any 木を生成とトラバース畳み込みは 1 回のトラバース中で同時に行われ、2 回トラバースするわけではありません（1 回目はマッピング、2 回目は畳み込み）。上で拆开て見るのは理解しやすいため

起手式の後、大招が来た：

> Foldable.foldMap (\x -> [x]) tree
[1,2,3,5,6,7,8,9]

待、何が発生？

一言で木を配列に変換。しかも、こっそり排序もした。好吧、少し誇張。排序は二叉検索樹が行った（fromList の時 add で建樹）。したがって木を配列に変換しただけ。具体的：

0. マッピング関数 (\x -> [x]) が入力の値を List に装入（収集）

1. 底から上に tree をトラバース。マッピング関数で各ノード上の数値を変換。空ノードに遭遇すれば mempty に包み、List 木を形成

2. List 木を畳み込み。具体的には底から上に「左 mappend 中 mappend 右」演算を行う。List の mappend は接続（++）。mempty に遭遇すれば [] に対応。樹根に走到時、演算結果は [樹上すべての要素]

3. 直接畳み込み結果を出力。[樹上すべての要素]

一言で包含性判断を完成。一言で樹上要素収集を完成。非常に驚艶な操作

P.S. 樹に対して求和、求積、要素フィルタリングは？非常に容易：

> getSum $ Foldable.foldMap Sum tree
41
> getProduct $ Foldable.foldMap Product tree
90720
> Foldable.foldMap (\x -> if x > 5 then [x] else []) tree
[6,7,8,9]

五.群、半群と幺半群

数学的意味から見ると、すべて集合と二項演算で形成された代数構造：

• 半群：集合 S およびその上の二項演算 ·:S×S→S。· が結合律を満たす場合、即ち：?x,y,z∈S、(x·y)·z=x·(y·z) があれば、有序対 (S,·) を半群と呼

• 幺半群：集合 M およびその上の二項演算 *: M × M → M。該演算は結合律を満たし、幺元も集合里にある

• 群：群は集合 G で、演算 · と共に。任意の 2 つの要素 a と b を結合して別の要素を形成。a·b と記。該演算は結合律と封閉性を満たす必要。集合里に幺元があり、各要素に逆元がある

P.S. 逆元とは、各 G 中の a に対して、G 中の要素 b が存在し、a·b = b·a = e に合致。ここの e は単位元

簡単に言うと：

• 半群：特定集合および該集合上で定義された二項演算。該演算は封閉性（二項演算結果仍在集合里）と結合率（左結合結果は右結合結果に等しい）を満た

• 幺半群：幺元を含む半群

• 群：各要素に対応する逆元を持つ幺半群

一般から特殊へ。幺半群は半群と群の間に位置。群が最も特殊（少し直感に合致しない）。逆に見ると、半群は幺半群の汎化（半群は幺元を要求しない）。また群の汎化（半群は各要素に逆元があることを要求しない）：

A semigroup generalizes a monoid in that there might not exist an identity element. It also (originally) generalized a group (a monoid with all inverses) to a type where every element did not have to have an inverse, thus the name semigroup.

構文角度から見ると、三者関係は以下の通り：

class Semigroup a where
  -- 結合律を満たす演算（同時に封閉性も満た）
  (<>) :: a -> a -> a

class Semigroup a => Monoid a where
  -- 幺元
  mempty  :: a
  -- 結合律を満たす演算（同時に封閉性も満た）
  mappend :: a -> a -> a
  mappend = (<>)

class Monoid m => Group m where
  -- 逆元を求める演算
  invert :: m -> m

Semigroup（半群）はインターフェース（typeclass）。特定集合および該集合上で定義された一種の演算を記。該演算は結合律を満た。すべての Semigroup インスタンスはこの種の行動特徴を持つ

Monoid（幺半群）もインターフェース。特定集合および該集合上で定義された結合律を満たす一種の演算を記。幺元も集合里にある

Group（群）も同様にインターフェース。特定結合を記。該集合上で定義された結合律を満たす一種の演算。幺元があるだけでなく、各要素に逆元もある

P.S. 另外、幺半群と範疇論には一定の関連がある。和範疇論の関係 を参照

参考資料

• semigroups: Anything that associates