Swiftでのモノイドの実装とその合成

モノイドは以下の項目により構成されます。

- 型A

- A型の二つの値をとり、一つのA型を返す演算op。A型であるx, y, zに対してop(op(x, y), z)==op(x, op(y, z))が成立する。例えば文字列の連結の場合"ab", "cd", "ef"の場合("ab"+"cd")+"ef"と"ab"+("cd"+"ef")は同じになります。

- 演算の単位元であるA型のzero。A型のxに対してop(x, zero)==xならびにop(zero, x)==xが成立する。例えば文字列の連結の場合zeroは空文字列""になります。"ab"+""=="ab"ならびに""+"ab"=="ab"になります。

これをSwiftで実装してさらにモノイドの合成をみてみます。

Swiftでのモノイドの実装

Swiftで実装すると以下のようになります。

struct Monoid<A> {
    let zero: A
    let op: (A, A) -> A
}

例えば整数の加算がモノイドです。

let intAdditionMonoid = Monoid<Int>(zero: 0, op: +)

モノイドの最もシンプルな利用シーンは畳み込みです。

Arrayのreduceメソッドの型を見てみると以下のようになっています。

(Result, (Result, Element) -> Result) -> Result

Int配列ではElementはIntになります。また、ResultとElementが同じ型とすると

(Int, (Int, Int) -> Int) -> Int

となります。これはモノイドの(zero, op) -> Aと合致します。

実際にintAdditionMonoidをreduceで利用してみると以下のようになります。

let intAdditionMonoid = Monoid<Int>(zero: 0, op: +)
let intArray = [1, 2, 3, 4]
let addition = intArray.reduce(intAdditionMonoid.zero, intAdditionMonoid.op)    // 10

モノイドの合成

では次に、モノイドを合成することを考えてみます。

Monoid<A>とMonoid<B>を合成してMonoid<(A, B)>を作成する関数を実装してみます。

func product<A, B>(_ a: Monoid<A>, _ b: Monoid<B>) -> Monoid<(A, B)> {
    return Monoid<(A, B)>(zero: (a.zero, b.zero), op: { tuple1, tuple2 -> (A, B) in
        (a.op(tuple1.0, tuple2.0), b.op(tuple1.1, tuple2.1))
    })
}

利用してみましょう。

Int配列の平均を計算します。平均にはリストの長さと合計を計算して合計/長さを行います。

let intAdditionMonoid = Monoid<Int>(zero: 0, op: +)
let intArray = [1, 2, 3, 4]
let pMonoid = product(intAdditionMonoid, intAdditionMonoid)
let tuple = intArray.map { ($0, 1) }.reduce(pMonoid.zero, pMonoid.op)   // (4, 10)
let average = Double(tuple.0) / Double(tuple.1)     // 2.5

int配列を(値, 1)の(Int, Int)配列に変換してモノイドを利用してreduceすることで合計と長さを得ています。（実際には長さはcountプロパティで取得すればよいのですがモノイドの合成の分かりやすい例として理解してください。）

以上、手短ですがSwiftでのモノイドの実装と合成でした。