Edited at

SwiftでFreeモナド

More than 1 year has passed since last update.

この記事はSwift Advent Calendar その2の10日目の記事です。

ふと見たら空いてたので、軽めの内容で補填しておきます。

SwiftではFunctorMonadも定義できません。ただし、特定の型においてのみメリットを享受することはできます。

FreeモナドのHaskell実装は以下の通りです。

data Free f r = Free (f (Free f r)) | Pure r

instance Functor f => Monad (Free f) where
return = Pure
Pure a >>= k = k a
Free fm >>= k = Free (fmap (>>=k) fm)

要素rのみとる値コンストラクタPureと、f (Free f r))をとる値コンストラクタFreeからなります。大事なのはinstance文に書かれているように、「FunctorなものがFreeを用いることでMonadになる」ということです。Functorをmapできるもの、MonadをflatMapできるものと簡易的に考えるならば、Swiftにおいてイメージしやすくなるのではないでしょうか。

Swift.Arrayに特化したFreeモナドのようなものとしてFreeArray<T>を以下のように定義します。

indirect enum FreeArray<T> {

case pure(T)
case impure([FreeArray<T>])
}

extension FreeArray {
func map<U>(_ f: (T) -> U) -> FreeArray<U> {
switch self {
case .pure(let t):
return .pure(f(t))

case .impure(let list):
return .impure(list.map{ $0.map(f) })
}
}

func flatMap<U>(_ fn: (T) -> FreeArray<U>) -> FreeArray<U> {
switch self {
case .pure(let t):
return fn(t)

case .impure(let list):
return .impure(list.map{ $0.flatMap(fn) })
}
}
}

impureの方はmapメソッドを実装しているArrayFreeArrayを包んでいます。つまりHaskell実装における値コンストラクタFreeに相当します。

定義できはしましたが、これの何が嬉しいのでしょうか。例えば以下のようなことができます。

extension FreeArray : ExpressibleByArrayLiteral {

init(arrayLiteral elements: FreeArray<T>...) {
self = .impure(elements)
}
}

prefix operator %
prefix func % <T>(element: T) -> FreeArray<T> {
return .pure(element)
}

let a: [Int] = [1]
let b: [Int] = [[[[[[[[1]]]]]]]] // NG

let c: FreeArray<Int> = %1
let d: FreeArray<Int> = [[[[[[[[%1]]]]]]]] // OK

いくら包んでやっても同じ型になります。最初にmapflatMapも定義したので、もちろん使えます。FreeArrayCollectionに準拠させるとこのようなこともできます。

extension FreeArray: Collection {

var startIndex: Int {
return 0
}

var endIndex: Int {
switch self {
case .pure(_):
return 1

case .impure(let list):
return list.reduce(0){ $0 + $1.endIndex }
}
}

subscript (index: Int) -> T {
guard startIndex <= index && index < endIndex else {
fatalError("range over")
}

switch self {
case .impure(let list):
var i = 0
for aList in list {
if index < i + aList.endIndex {
return aList[index - i]
}

i += aList.endIndex
}

fatalError("is end")

case .pure(let t):
guard index == 0 else {
fatalError("")
}

return t
}
}

func index(after i: Int) -> Int {
return i == endIndex ? i : i + 1
}
}

let freeList: FreeArray<Int> = [%1, [%2, %3, [%4]], %5]
freeList.reduce(""){ "\($0) \($1)" } // "1 2 3 4 5"

Enjoy Swift life!


参考

Freeモナドって何なのさっ!?

free monadとはmonadそのものである