Реализация Y-Combinator в Swift - PullRequest
Новая
       70

Реализация Y-Combinator в Swift

0 голосов
/ 23 марта 2020

Я смотрел этот разговор Джима Вейриха: https://www.youtube.com/watch?v=FITJMJjASUs о внедрении Y-Combinator в Ruby и последующем продвижении в Swift.

В конце концов я получил эту функцию , который работает как факториал для чисел до 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)
  }
}
)

Что происходит дальше, это то, что он удаляет error, и его код все еще работает: 

let generator = { (generator: (@escaping ((Int) -> Int)) -> (Int) -> Int) in
  generator(generator)
} ...

Который, в Swift, это ошибка компилятора, потому что generator ожидает (Int) -> Int в качестве ввода, но получает тип generator.

Вместо этого мы можем реализовать Y-комбинатор следующим образом: 

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)
  }
}

Но проблема выше в том, что функция Y ссылается на себя в строке:

let recursiveWorker = Y(generator)

, что, как мне кажется, противоречит всей цели этого упражнения.

Мой вопрос: возможно ли реализовать в Swift тот же код, что и в докладе? То есть создание замыкания Y-комбинатор? Или это невозможно из-за того, что Свифт печатает c?

...