如何使用Kotlin編寫Y組合函數？

Question

我可以使用Kotlin FP（Lambda，函數）編寫Y組合函數嗎？

Y = λf.(λx.f (x x)) (λx.f (x x)) 

在JS：

function Y(f) { 
    return (function (g) { 
     return g(g); 
    })(function (g) { 
     return f(function (x) { 
      return g(g)(x); 
     }); 
    }); 
} 

var fact = Y(function (rec) { 
    return function (n) { 
     return n == 0 ? 1 : n * rec(n - 1); 
    }; 
}); 

在咖啡：

coffee> Y = (f) -> ((x) -> (x x)) ((x) -> (f ((y) -> ((x x) y)))) 
[Function] 

coffee> fact = Y (f) ->(n) -> if n==0 then 1 else n*f(n-1) 
[Function] 

coffee> fact(10) 
3628800 

我怎樣才能做到這一點？

Answer 1

在科特林，您應該引入額外的接口G，否則，你將得到UNCHECKED_CAST警告，因爲科特林是靜態類型編程語言，而不是一種動態語言，例如：

typealias X = (Int) -> Int 
typealias F = Function1<X, X> 
//  v-------------v--- let G reference G recursively 
interface G : Function1<G, X> 

// v--- create a G from lazy blocking 
fun G(block: (G) -> X) = object : G { 
    //       v--- delegate call `block(g)` like as `g(g)` 
    override fun invoke(g: G) = block(g) 
} 

fun Y(f: F) = (fun(g: G) = g(g))(G { g -> f({ x -> g(g)(x) }) }) 

val fact = Y({ rec -> { n -> if (n == 0) 1 else n * rec(n - 1) } }) 

另一個版本蒙上了Function1<G, X>到G，所以應該抑制UNCHECKED_CAST警告，例如：

typealias X = (Int) -> Int 
typealias F = Function1<X, X> 
typealias G = Function1<Any, X> 

@Suppress("UNCHECKED_CAST") 
//           v--- cast `g` to `G`. 
fun Y(f: F) = (fun(g: Function1<G, X>) = g(g as G))({ g -> f { x -> g(g)(x) } }) 

val fact = Y({ rec -> { n -> if (n == 0) 1 else n * rec(n - 1) } })