Практический пример Y-Combinator

Question

В последнее время я немного читал о функциональном программировании и пытаюсь использовать Y-Combinator. Я понимаю, что вы можете использовать Y-Combinator для эффективной реализации рекурсии на языке, который не поддерживает рекурсию напрямую. Однако каждый язык, который я, вероятно, буду использовать, уже поддерживает рекурсию, поэтому я не уверен, насколько полезно было бы использовать для этого Y-Combinator.

Есть ли лучший практический пример использования Y-Combinator, который мне не хватает? Кто-нибудь на самом деле использовал его в реальном производственном коде? Или использование Y-Combinator действительно просто умопомрачительное академическое упражнение (хотя и довольно крутое).

Answer 1

Я собираюсь не согласиться с другими ответами: Комбинатор с фиксированной точкой (Y) имеет практическое применение , но для их поиска требуется очень изобретательный ум. Как Брюс МакАдам. Вот реферат из его статьи Это о том, что оборачивает :

Y комбинатор для вычисления фиксированных точек может быть выражен в стандарте ML. Он часто используется в качестве примера мощности функций высшего порядка, но обычно не рассматривается как полезная конструкция программирования. Здесь мы рассмотрим, как методика программирования, основанная на Y-комбинаторе и оболочках, может дать программистам уровень контроля над внутренней работой функций, невозможной в противном случае без переписывания и перекомпиляции кода. В качестве эксперимента алгоритм W определения типа реализован с использованием этой методики, так что сообщения об ошибках создаются с минимальными помехами для алгоритма. Код для этого примера программы иллюстрирует подлинную полезность концепций и простоту их применения. Также обсуждается ряд других методов реализации и возможных приложений, в том числе использование функций более высокого порядка для имитации использования исключений и продолжений.

Это отличная газета; всем, кто интересуется функциональным программированием, вероятно, понравится читать его.

Answer 2

Вы можете проверить этот изящный пост о реализации Y Combinator в C #: Рекурсивные лямбда-выражения , это может помочь вам лучше понять идею.

Возможно, вы захотите посмотреть несколько хороших статей в Википедии: Комбинатор с фиксированной точкой и Теоремы о фиксированной точке

Как говорит Натан, многие функциональные приемы связаны с Y-комбинатором и полезны, так что продолжайте в том же духе! Y действительно полезен, потому что позволяет лучше понять ваш код, но я не думаю, что это особенно полезно для описания того, как он помогает.

Answer 3

Вы можете думать о комбинаторе как о виртуальной машине, которая выполняет вашу функцию, которую вы описываете нерекурсивным функционалом (= функция более высокого порядка).

Иногда было бы неплохо иметь этот комбинатор под управлением программы, чтобы делать подобные вещи, как аспектно-ориентированное программирование (запоминание, трассировка, ...), но ни один из известных мне языков программирования не позволяет этого. Возможно, в большинстве случаев это будет слишком громоздко и / или слишком сложно для изучения.

Answer 4

Другие могут поправить меня, если я ошибаюсь, но я почти уверен, что Y-комбинатор строго академичен. Подумайте об этом: для его реализации ваш язык должен поддерживать функции высшего порядка, а не рекурсию. Я знаю только один такой язык: лямбда-исчисление.

Таким образом, пока наши машины не перейдут с машин Тьюринга на работу с лямбда-исчислением, комбинатор Y будет строго академическим.

Примечание: другие функциональные приемы, связанные с Y-комбинатором , полезны, так что следуйте им. Понимание Y-комбинатора поможет вам понять продолжения, ленивые вычисления и т. Д.

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

Вот пример из компилятора для маленькой библиотеки игр, которую я делаю на F #. Более конкретно, в приведенном выше примере мне нужно, чтобы sprites_up вызывал сам себя рекурсивно, иначе анализатор отступов не будет работать правильно.

Без Y Combinator я не смог бы правильно выполнить синтаксический анализатор и должен был бы написать что-то вроде этого:

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

Не было бы отличного решения, Y Combinator действительно спас меня там. Хотя, конечно, это было не первое, что пришло в голову.