Практический пример Y-комбинатора

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.Хотя, конечно, это было не первое, что пришло на ум.