I was watching this talk by Jim Weirich: https://www.youtube.com/watch?v=FITJMJjASUs about implementing the Y-Combinator in Ruby, and following along in Swift.
I eventually got to this function, which works as a factorial for numbers up to 5:
let error: (Int) -> Int = { x in return -1 }
let generator = { (generator: (@escaping ((Int) -> Int)) -> (Int) -> Int) in
generator(generator(generator(generator(generator(generator(error))))))
}( { (factorial: @escaping ((Int) -> Int)) -> (Int) -> Int in
{ (x: Int) -> Int in
if x == 0 { return 1 }
return x * factorial(x-1)
}
}
)
What happens next is that he removes error
, and his code still works:
let generator = { (generator: (@escaping ((Int) -> Int)) -> (Int) -> Int) in
generator(generator)
} ...
Which, in Swift, is a compiler failure because generator
is expecting (Int) -> Int
as input, but getting a generator
type.
Instead, we can implement the Y-combinator as follows:
func Y<T, R>(_ generator: @escaping (@escaping (T) -> R) -> (T) -> R) -> (T) -> R {
return { (t: T) -> R in
let recursiveWorker = Y(generator)
let worker = generator(recursiveWorker)
return worker(t)
}
}
let factorial = Y { (factorial: @escaping (Int) -> Int) -> (Int) -> Int in
{ (x: Int) -> Int in
if x == 0 { return 1 }
return x * factorial(x-1)
}
}
But the problem above is that the Y
function refers to itself in the line:
let recursiveWorker = Y(generator)
Which seems to me to defeat the whole purpose of this exercise.
My question is: Is it possible to implement in Swift the same code as in the talk? That is, creating a closure Y-combinator? Or is this impossible because of Swift's static typing?