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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

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

Примечание. Другие функциональные методы, относящиеся к Y combinator, полезны, поэтому держитесь за них. Понимание Y combinator поможет вам понять продолжение, ленивую оценку и т.д.

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