Help us understand the problem. What is going on with this article?

SwiftでFreeモナド

More than 3 years have 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そのものである

335g
an amateur in programming
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした