monoid
id:akihiro4chawon 氏の 比較はモノイド を読んで新しい視点が得られた気がするので忘れないうちに書いておく。
半群とは
Wikipedia から引用
演算が閉じている
- S の各元 a, b に対して、演算結果 a • b は再び S に属する。
結合律
- S の各元 a, b, c に対して、等式 (a • b) • c = a • (b • c) が満たされる。
の2つの条件を満たせば半群 (semigroup) らしいので Groovy で書いてみる。
boolean isSemigroup(Set S, Closure op) { // 2項演算子であること assert op.maximumNumberOfParameters == 2 isClosed(S, op) && isAssociative(S, op) } // 演算が閉じていることを調べる boolean isClosed(Set S, Closure op) { for (a in S) for (b in S) if (!(op(a, b) in S)) return false return true } // 結合律を調べる boolean isAssociative(Set S, Closure op) { for (a in S) for (b in S) for (c in S) if (op(a, op(b, c)) != op(op(a, b), c)) return false return true } // ?: は assert isSemigroup([-1,0,1] as Set, { a, b -> a ?: b })
半群を探す
他にも条件を満たす演算子があるような気がしてきたので Groovy の二項演算子を全部調べてみる。
def operators() { [ '?:':{ a, b -> a ?: b }, '+' :{ a, b -> a + b }, '-' :{ a, b -> a - b }, '*' :{ a, b -> a * b }, '**':{ a, b -> a ** b }, '/' :{ a, b -> a / b }, 'intdiv':{ a, b -> a.intdiv(b) }, '%' :{ a, b -> a % b }, '|' :{ a, b -> a | b }, '&' :{ a, b -> a & b }, '^' :{ a, b -> a ^ b }, '<<':{ a, b -> a << b }, '>>':{ a, b -> a >> b }, '>>>':{ a, b -> a >> b }, '==':{ a, b -> a == b }, '!=':{ a, b -> a != b }, '<=>':{ a, b -> a <=> b }, '>' :{ a, b -> a > b }, '>=':{ a, b -> a >= b }, '<' :{ a, b -> a < b }, '<=':{ a, b -> a <= b }, ] } def semigroupOps(Set S) { operators().findAll { name, op -> try { isSemigroup(S, op) } catch(e) { false } } } assert semigroupOps([-1,0,1] as Set)*.key == ['?:', '*', '|', '&']
4つの演算子が条件を満たしているようだ。
モノイドを探す
Wikipedia から引用。
単位元の存在
- S の元 e が存在して、S の任意の元 a に対して e • a = a • e = a なる等式が成り立つ。
結合律は半群で条件を満たすので単位元の条件を追加すればモノイドということになる。
boolean isMonoid(Set S, Closure op) { isSemigroup(S, op) && hasIdentity(S, op) } boolean hasIdentity(Set S, Closure op) { for (e in S) if (S.every { a -> op(a, e) == a && op(e, a) == a }) return true return false } def monoidOps(Set S) { operators().findAll { name, op -> try { isMonoid(S, op) } catch(e) { false } } } assert monoidOps([-1,0,1] as Set)*.key == ['?:', '*', '|', '&']
先程の4つの演算子と比較結果の集合はモノイドの条件も満たしていた。
def identity(Set S, Closure op) { for (e in S) if (S.every { a -> op(a, e) == a && op(e, a) == a }) return e assert false } assert identity([-1,0,1] as Set, { a, b -> a ?: b }) == 0 assert identity([-1,0,1] as Set, { a, b -> a * b }) == 1 assert identity([-1,0,1] as Set, { a, b -> a | b }) == 0 assert identity([-1,0,1] as Set, { a, b -> a & b }) == -1
比較がモノイドであることを確認する
4つの演算子で比較してみる。
([-1,0,1] as Set).with { S -> def to_s = [(-1):'LT',(0):'EQ',(1):'GT'] monoidOps(S).each { name, op -> println "A $name B" for (a in S) for (b in S) println "${to_s[a]} $name ${to_s[b]} = ${to_s[op(a, b)]}, ${to_s[-op(-a, -b)]}" } }
結果
A ?: B EQ ?: EQ = EQ, EQ EQ ?: GT = GT, GT EQ ?: LT = LT, LT GT ?: EQ = GT, GT GT ?: GT = GT, GT GT ?: LT = GT, GT LT ?: EQ = LT, LT LT ?: GT = LT, LT LT ?: LT = LT, LT A * B EQ * EQ = EQ, EQ EQ * GT = EQ, EQ EQ * LT = EQ, EQ GT * EQ = EQ, EQ GT * GT = GT, LT GT * LT = LT, GT LT * EQ = EQ, EQ LT * GT = LT, GT LT * LT = GT, LT A | B EQ | EQ = EQ, EQ EQ | GT = GT, GT EQ | LT = LT, LT GT | EQ = GT, GT GT | GT = GT, GT GT | LT = LT, GT LT | EQ = LT, LT LT | GT = LT, GT LT | LT = LT, LT A & B EQ & EQ = EQ, EQ EQ & GT = EQ, EQ EQ & LT = EQ, EQ GT & EQ = EQ, EQ GT & GT = GT, GT GT & LT = GT, LT LT & EQ = EQ, EQ LT & GT = GT, LT LT & LT = LT, LT
カンマの右は Comparator#compare の条件を満たしている場合は同じになるように設定した。
Javadoc から引用。
実装では、すべての x と y に対して sgn(compare(x, y)) == -sgn(compare(y, x)) が保証されなければいけません。
残念ながら compare で使える演算子は ?: だけだった。
比較はモノイドであるが、モノイドであれば比較で使えるわけではないということみたいだ。
でもモノイドであることは何か有用な気がしてきたので気になることを確認する。
結合律を確認する
つまり foldLeft と foldRight のどちらで計算しても結果は同じということ。
// すべての要素が集合 S に属するサイズ n のリストを返す def randomList(Set S, int n) { def list = S as List (1..n).collect { list[Math.random() * list.size() as int] } } // 半群であることを利用する ([-1,0,1] as Set).with { S -> def l = randomList(S, 5) def r = l.reverse() semigroupOps(S).each { name, op -> assert l.tail().inject(l.head()) { a, b -> op(a,b) } == r.tail().inject(r.head()) { b, a -> op(a,b) } : "A $name B" } } // モノイドであることを利用する ([-1,0,1] as Set).with { S -> def l = randomList(S, 5) def r = l.reverse() monoidOps(S).each { name, op -> def e = identity(S, op) assert l.inject(e) { a, b -> op(a,b) } == r.inject(e) { b, a -> op(a,b) } : "A $name B" } }
使ってみる
Groovy のリストは Comparable ではないので List のための Comparator を実装する。
結合律があるのでどちら側から計算しても結果は同じ。
// 再帰で比較 def asc1 = { List l1, List l2, int i = 0 -> l1.size() < i && l2.size() < i ? 0 : l1[i] <=> l2[i] ?: trampoline(l1, l2, i+1) }.trampoline() // 左結合で比較 def asc2 = { List l1, List l2 -> [l1, l2].transpose().inject(0) { acc, pair -> acc ?: pair[0] <=> pair[1] } ?: l1.size() <=> l2.size() } // 右結合で比較 def asc3 = { List l1, List l2 -> [l1, l2].transpose().reverse().inject(0) { acc, pair -> pair[0] <=> pair[1] ?: acc } ?: l1.size() <=> l2.size() } def lists = (1..5).collect { randomList(0..9 as Set, 5) } println lists assert lists.clone().sort(asc2) == lists.clone().sort(asc1) assert lists.clone().sort(asc3) == lists.clone().sort(asc1) println lists.clone().sort(asc1)
右結合を使えるということは
foldr といえば無限リスト、Merge が合言葉。
Haskell で遅延評価を使って fold で無限リストを比較してみる。
サイズの比較部分は省略した。
order EQ a = a order LT _ = LT order GT _ = GT compareR :: (Ord a) => [a] -> [a] -> Ordering compareR xs ys = foldr (order . (uncurry compare)) EQ $ zip xs ys compareL :: (Ord a) => [a] -> [a] -> Ordering compareL xs ys = foldl (flip (order . (uncurry compare))) EQ $ zip xs ys
結果
*Main> compareR [1..] [1,1..] GT *Main> compareL [1..] [1,1..] <interactive>: out of memory
Haskell では compare で無限リストも比較できるがその実装は再帰によるパターンマッチだった。
でも比較がモノイドであるので foldr でも実装できることが分かった。
以前、フィボナッチ数列でやった行列計算とかもモノイド？という風にいろいろモノイドに見えてきた。
まとめ
- 比較はモノイドである
- モノイドであっても比較とは限らない
- モノイドであることに気づければ foldr に持ち込める
