SwiftでYコンビネータを使ってみる #Swift

Y コンビネーターを使うと無名関数での再帰的な関数呼び出しが実現できてしまう。

Y = (\lambda f . (\lambda x . f (x x)) (\lambda x . f (x x)))

型パラメータを使いたいので、広域関数として落とす

func Y<T, U>(f: (T -> U) -> (T -> U)) -> (T -> U) {
    return { (x: T) -> U in
        f(Y(f))(x)
    }
}

階乗計算

Y({ (f: Int -> Int) -> (Int -> Int) in
    { (n: Int) -> Int in n == 0 ? 1 : n * f(n - 1) }
})(5) // 120

フィボナッチ数列

// 型推論が効くので型を明示しなくてもコンパイルは通る
Y({ f in
    { n in n <= 2 ? 1 : f(n - 1) + f(n - 2) }
})(10) // 55

SwiftでYコンビネータを使ってみる