Swiftでちょっとだけモナド
Monads for functional programming - Philip Wadler セクション２のメモ。セクション２では、シンプルな評価器を構成することにより、モナドを導入し、修正に強い評価器を構成するのにモナドが使用できることが説明されている。
環境
- Xcode 8.0
- Swift 3.0
準備
- forget inpure world
バリエーション０：基本的な評価器
項を定数 con(Int) か 項の商 div(Term, Term) で定義する。
enum Term { case con(Int) indirect case div(Term, Term) }
ログのために CustomStringConvertible を準拠させる。
extension Term: CustomStringConvertible { var description: String { switch self { case let .con(a): return "con(\(a))" case let .div(t, u): return "div(\(t), \(u))" } } }
評価器(eval関数)は項(Term)に作用する。
基本的な評価機（eval関数）は至って簡単。
(話を分かりやすくするために、簡単にしてある。)
func eval(_ term: Term) -> Int { switch term { case let .con(a): return a case let .div(t, u): return eval(t) / eval(u) } }
以下の項 answer と error は他の例でも用いる。
// (1972 / 2) / 23 let answer: Term = .div(.div(.con(1972), .con(2)), .con(23)) // 1 / 0 let error: Term = .div(.con(1), .con(0))
eval(answer) の評価は 42 になる。この評価器には例外処理は組み込まれていないので、eval(error)の評価はexecution errorになる。
eval(answer) // 出力：42 eval(error) // error
バリエーション1：例外
上記の例 eval(error) でエラーメッセージを返すようにエラー判定を加える。 例外処理は例外を投げる可能性がある計算を表す型を導入する。
enum M<A> { typealias `exception` = String case raise(`exception`) case ret(A) // Haskellのreturn }
型M<A> は、 .raise(e) の形式(eはexception)か、.ret(a) の形式(aは型Aの値)をした値をとる。
評価器をこの型に適合させるのは簡単だが、退屈である。
func eval(_ term: Term) -> M<Int> { switch term { case let .con(a): return .ret(a) case let .div(t, u): switch eval(t) { case let .raise(e): return .raise(e) case let .ret(a): switch eval(u) { case let .raise(e): return .raise(e) case let .ret(b): if b == 0 { return .raise("divided by zero") } else { return .ret(a / b) } } } } }
各評価器の呼び出し時に、結果の形式を確認する必要がある。
例外が投げられた場合は、再度例外が投げられ、値の場合は、処理される。
eval(answer) // 出力：ret(42) eval(error) // 出力：raise("divided by zero")
バリエーション２：状態(State)
評価中の除法(割り算)の回数をカウントすることを考える。
状態は状態に作用する計算を表す型を導入する。
typealias State = Int typealias M<A> = (State) -> (A, State)
型M<A> の値は初期状態を取り、最終状態とペアになった計算の値を戻り値にする関数である。
再び、評価器をこの型に適合させるのは簡単だが、退屈である。
func eval(_ term: Term) -> M<Int> { switch term { case let .con(a): return { x in (a, x) } case let .div(t, u): return { x in let (a, y) = eval(t)(x) let (b, z) = eval(u)(y) return (a / b, z + 1) } } }
eval(answer)(0) の評価は (42, 2) になる。よって、初期状態 0 の時、答えは 42 で、最終状態は、除法が2回行われたことを示す 2 である。
eval(answer)(0) // 出力：42 2
バリエーション３：出力
実行のトレースを出力することを考える。
出力は出力を生成する計算を表現する型を導入する。
typealias Output = String typealias M<A> = (Output, A)
型M<A> の値は出力を生成したペアと計算結果の値で構成される。
又々、評価器をこの型に適合させるのは簡単だが、退屈である。
func eval(_ term: Term) -> M<Int> { switch term { case let .con(a): return (line(term)(a), a) case let .div(t, u): let (x, a) = eval(t) let (y, b) = eval(u) return (x + y + line(term)(a / b), a / b) } } func line(_ term: Term) -> (Int) -> Output { return { "eval \(term) <= \($0)\n" } }
eval(answer) のoutputは計算のトレースを表し、出力は以下のようになる。
eval con(1972) <= 1972 eval con(2) <= 2 eval div(con(1972), con(2)) <= 986 eval con(23) <= 23 eval div(div(con(1972), con(2)), con(23)) <= 42
Monadic評価器
各バリエーションで、計算の種類を見た。それぞれMは、例外を発生させ、状態に作用し、出力を生成する計算を表した。最初の評価器はTerm -> Intの型を持っていたが、各バリエーションでは、Term -> M<Int>の型になった。一般に、A -> Bの関数の型からA -> M<B>の関数の型に替わった。これは、型Aを引数に取り、型Bの結果とMによって得られた付加効果を返す関数と解釈できる。
それぞれの例から分かるように、型Mに必要なオペレーションは以下の２つ:
func unit(_ a: A) -> M<A> func *<A, B>(x: M<A>, f:(A) -> M<B>) -> M<B>
型構成子Mと２つのオペレーションで構成する３つの組み(M, unit, *)をモナドと言う。これらのオペレーションはセクション３で説明されている３つの法則を満たさなければならない。
これらの抽象化の観点から、評価器は以下のように書き換えられる:
func eval(_ term: Term) -> M<Int> { switch term { case let .con(a): return unit(a) case let .div(t, u): return eval(t) * { a in eval(u) * { b in unit(a / b) } } } }
この評価器は最初のものよりは複雑だが、柔軟である。各バリエーションで見た変更は、M, unit, * の定義と局所的な変更をするだけで良い。評価器全体を書き換える必要がない。
バリエーション０再考：基本的な評価器
最も単純なモナドでは、計算は値と何ら変わりはない。
typealias M<A> = A func unit<A>(_ a: A) -> M<A> { return a } func *<A, B>(a: A, f: ((A) -> M<B>)) -> M<B> { return f(a) }
バリエーション1再考：例外
例外モナドでは、計算は例外を発生させるか、値を返す。
enum M<A> { typealias `exception` = String case raise(`exception`) case ret(A) } func unit<A>(_ a: A) -> M<A> { return .ret(a) } func *<A, B>(a: M<A>, k:(A) -> M<B>) -> M<B> { switch a { case let .ret(a): return k(a) case let .raise(e): return .raise(e) } } func raise<A>(_ e: M<A>.exception) -> M<A> { return .raise(e) }
unit(a) は単純に値aを返す。
m * k はmが例外の場合、再度例外を発生させ、その他の場合、関数kを戻された値に適応する。
最後に関数raiseは例外を発生させる。
例外処理をmonadic評価器に加えるには、上記のモナドと、 unit(a/b) を以下のように変更すれば良い。
if b == 0 { return raise("divide by zero") } else { return unit(a / b) }
評価器は以下のようになる：
func eval(_ term: Term) -> M<Int> { switch term { case let .con(a): return unit(a) case let .div(t, u): return eval(t) * { a in eval(u) * { b in if b == 0 { return raise("divided by zero")} else { return unit(a / b) } } } } }
バリエーション2再考：状態
状態モナドでは、計算は初期状態を取り、値とペアになる最終状態を返す。
typealias State = Int typealias M<A> = (State) -> (A, State) func unit<A>(_ a: A) -> M<A> { return { x in (a, x) } } func *<A, B>(m: @escaping M<A>, k: @escaping ((A) -> M<B>)) -> M<B> { return { x in let (a, y) = m(x) let (b, z) = k(a)(y) return (b, z) } } let tick: M<()> = { x in ((), x + 1) }
unit(a) は初期状態xと値aと最終状態xをとる計算を返す。つまり、unit(a)はaをとり状態を変更させない。
m * k は初期状態xの計算mを実行し、値aと中間状態yを引き起こし、状態yの計算k(a)を実行し、値bと最終状態zを返す。
tick は状態を増加させ、空の値()を返す。
monadic評価器に実行回数をカウントする機能を追加するには、上記のモナドとunit(a/b) を以下に変更すれば良い。
tick * { unit(a / b) }
評価器は以下のようになる：
func eval(_ term: Term) -> M<Int> { switch term { case let .con(a): return unit(a) case let .div(t, u): return eval(t) * { a in eval(u) * { b in tick * { unit(a / b) } } } } }
バリエーション3再考：出力
出力モナドでは、計算は生成された出力とペアになる値を返す。
typealias Output = String typealias M<A> = (Output, A) func unit<A>(_ a: A) -> M<A> { return ("", a) } func *<A, B>(m: M<A>, k:(A) -> M<B>) -> M<B> { let (x, a) = m let (y, b) = k(a) return (x + y, b) } func out(_ x: Output) -> M<()> { return (x, ()) }
unit(a) は出力なしとペアになるaを返す。 m * k は出力xと計算mの値aを抽出し、出力yと計算k(a)の値bを抽出し、xとyの結合からなる出力とペアになる値bを返す。 out(x) は出力xと空の値()の計算を返す。
実行のトレースをmonadic評価器に適応すると以下のようになる。
func eval(_ term: Term) -> M<Int> { switch term { case let .con(a): let output = out(line(term)(a)) return output * { unit(a) } case let .div(t, u): return eval(t) * { a in eval(u) * { b in let output = out(line(.div(t, u))(a / b)) return output * { unit(a / b) } } } } }
