SwiftでFreeモナド

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

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

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

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メソッドを実装しているArrayがFreeArrayを包んでいます。つまり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

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

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そのものである