0

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?

Eduard Lev
  • 33
  • 5
  • Did you check these related questions? https://stackoverflow.com/q/39643834, https://stackoverflow.com/q/26051683, https://stackoverflow.com/q/25103534, https://stackoverflow.com/q/34563892. – Martin R Mar 23 '20 at 13:53
  • Yes, https://stackoverflow.com/questions/26051683/ycombinator-not-working-in-swift has the closest thing to what I'm looking for, but the answer by @newacct only provides the final code and not the explanation of why Swift is different than Ruby here. – Eduard Lev Mar 23 '20 at 14:00
  • Actually, with the other questions, was able to convert the function to the following: ``` let generator = { (generator: Any) -> (Int) -> Int in (generator as! (Any) -> (Int) -> Int)(generator) }( { (factorial: Any) -> (Int) -> Int in { (x: Int) -> Int in if x == 0 { return 1 } return x * (factorial as! (Any) -> (Int) -> Int)(factorial)(x-1) } } ) ``` which solves the original question. – Eduard Lev Mar 23 '20 at 14:10
  • Btw, you don't need a generator for `Y`. In an eagerly evaluated language evaluation can be stopped by using eta abstractions. Here is an implementation in Javascript `Y = f => (x => f(y=> x (x) (y))) (x => f(y => x (x) (y))); fact = Y(go => n => n === 0 ? 1 : n * go(n - 1));`. Please note that `Y` in this form doesn't even have a type in Haskell, which has a quite expressive type system. –  Mar 23 '20 at 15:26

0 Answers0