Практический пример 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 действительно спас меня там. Это, конечно, не первое, что пришло в голову, хотя.