Implementing the Y-Combinator in Swift

91 Views Asked by At

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?

0

There are 0 best solutions below