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