Хорошее объяснение "Комбинаторов" (для не математиков)

Question

Кто-нибудь получил хорошее объяснение «комбинаторов» (Y-комбинаторы и т. Д. И НЕ компании )?

Я ищу одного для практического программиста, который понимает функции рекурсии и высшего порядка, но не имеет сильной теории или математического фона.

(Примечание: я говорю о этих вещах )

Answer 1

Если вы не глубоко в теории, вы можете рассматривать Y комбинатор как аккуратный трюк с функциями, такими как монады.

Монады позволяют вам цеплять действия, Y комбинатор позволяет вам определить саморекурсивные функции.

Python имеет встроенную поддержку саморекурсивных функций, так что вы можно определить их без Y:

> def fun():
>  print "bla"
>  fun()

> fun()
bla
bla
bla
...

fun доступен внутри fun, так что мы можем легко назвать его.

Но что, если Python был другим, а fun не был доступен внутри fun?

> def fun():
>   print "bla"
>   # what to do here? (cannot call fun!)

Решение - передать fun в качестве аргумента fun:

> def fun(arg): # fun receives itself as argument
>   print "bla"
>   arg(arg) # to recur, fun calls itself, and passes itself along

И Y делает это возможным:

> def Y(f):
>   f(f)

> Y(fun)
bla
bla
bla
...

Все, что он делает, это вызывает функцию с самим собой в качестве аргумента.

(Я не знаю, правильно ли это определение Y на 100%, но я думаю, что это общая идея.)

Answer 2

Реджинальд Брэйтвейт (он же Раганвальд) в своем новом блоге пишет «1001 * homoiconic » о серии комбинаторов в Ruby

Хотя он (насколько мне известно) не смотрит на сам Y-комбинатор, он смотрит и на другие комбинаторы, например:

• Пустельга
• Молочница
• Кардинал
• Упрямый пустельга
• другие необычные птицы

и несколько сообщений о том, как вы можете использовать их.

Answer 3

Цитата Википедии:

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

Теперь, что это значит? Это означает, что комбинатор - это функция (вывод определяется исключительно ее вводом), чей ввод включает функцию в качестве аргумента.

Как выглядят такие функции и для чего они используются? Вот несколько примеров:

(f o g)(x) = f(g(x))

Здесь o - комбинатор, который принимает 2 функции, f и g, и возвращает в качестве результата функцию, составленную из f с g, а именно f o g.

Комбинаторы могут использоваться для сокрытия логики. Скажем, у нас есть тип данных NumberUndefined, где NumberUndefined может принимать числовое значение Num x или значение Undefined, где x a - Number. Теперь мы хотим построить сложение, вычитание, умножение и деление для этого нового числового типа. Семантика та же, что и для Number, за исключением того, что Undefined является входом, выход также должен быть Undefined, а при делении на число 0 выход также Undefined.

Можно написать утомительный код, как показано ниже:

Undefined +' num = Undefined
num +' Undefined = Undefined
(Num x) +' (Num y) = Num (x + y)

Undefined -' num = Undefined
num -' Undefined = Undefined
(Num x) -' (Num y) = Num (x - y)

Undefined *' num = Undefined
num *' Undefined = Undefined
(Num x) *' (Num y) = Num (x * y)

Undefined /' num = Undefined
num /' Undefined = Undefined
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x / y)

Обратите внимание, что все они имеют одинаковую логику относительно Undefined входных значений. Только деление делает немного больше. Решение состоит в том, чтобы извлечь логику, сделав ее комбинатором.

comb (~) Undefined num = Undefined
comb (~) num Undefined = Undefined
comb (~) (Num x) (Num y) = Num (x ~ y)

x +' y = comb (+) x y
x -' y = comb (-) x y
x *' y = comb (*) x y
x /' y = if y == Num 0 then Undefined else comb (/) x y

Это можно обобщить в так называемую монаду Maybe, которую программисты используют в функциональных языках, таких как Haskell, но я не буду туда идти.

Answer 4

Комбинатор - это функция с без свободных переменных . Это означает, среди прочего, что комбинатор не имеет зависимостей от вещей вне функции, только от параметров функции.

Используя F # это мое понимание комбинаторов:

let sum a  b = a + b;; //sum function (lambda)

В приведенном выше случае сумма является комбинатором, поскольку и a, и b связаны с параметрами функции.

let sum3 a b c = sum((sum a b) c);;

Вышеприведенная функция не является комбинатором, так как использует sum, который не является связанной переменной (т. Е. Она не определяется ни одним из параметров).

Мы можем сделать sum3 комбинатором, просто передав функцию sum в качестве одного из параметров:

let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);;

Таким образом, sumFunc является ограниченным и, следовательно, вся функция является комбинатором.

Итак, это мое понимание комбинаторов. Их значение, с другой стороны, все еще ускользает от меня. Как отмечали другие, комбинаторы с фиксированной точкой позволяют выражать рекурсивную функцию без explicit рекурсии. То есть вместо того, чтобы вызывать себя, рекурсивная функция вызывает лямбду, которая передается в качестве одного из аргументов.

Вот одно из самых понятных производных от комбинатора, которое я нашел:

http://mvanier.livejournal.com/2897.html

Answer 5

Это выглядит неплохо: http://www.catonmat.net/blog/derivation-of-ycombinator/

Answer 6

У меня довольно мало теории, но я могу привести вам пример, который подстегнет мое воображение, что может быть полезно для вас. Самый простой интересный комбинатор - это, вероятно, «тест».

Надеюсь, вы знаете Python

tru = lambda x,y: x
fls = lambda x,y: y 

test = lambda l,m,n: l(m,n)

Использование:

>>> test(tru,"goto loop","break")
'goto loop'
>>> test(fls,"goto loop","break")
'break'

test оценивает второй аргумент, если первый аргумент равен true, в противном случае третий.

>>> x = tru
>>> test(x,"goto loop","break")
'goto loop'

Целые системы могут быть построены из нескольких базовых комбинаторов.

(Этот пример более или менее скопирован Бенджамином С. Пирсом из Типов и Языков программирования)

Answer 7

Это хорошая статья . Примеры кода в схеме, но им не должно быть сложно следовать.

Answer 8

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

Также просканируйте SO архивы:

• Что такое y-комбинатор?
• Практический пример Y-Combinator