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

Question

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

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

(Примечание: что я говорю о these things)

Answer 1

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

Answer 2

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

Монады позволяют вам цепляться за действия, комбинатор 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 3

Реджинальд Брейтуэйт (ака Raganwald) было писать большую серию на комбинаторов в Рубине над в своем новом блоге, homoiconic.

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

• Kestrel
• Thrush
• Cardinal
• в Obdurate Kestrel
• другие Изворотливые Птицы

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

Answer 4

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

Надеется, что вы знаете, 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' 

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

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

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

(Этот пример более или менее копируется из типов и языков программирования по Benjamin C. Pierce)

Answer 5

цитированием Википедии:

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

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

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

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

Здесь o является комбинатор, который принимает в 2-х функций, и fg, и возвращает функцию в качестве результата, состав 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 6

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

Кроме того, сканировать архивы SO:

• What is a y-combinator?
• Y-Combinator Practical Example

Answer 7

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

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

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

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

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

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

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

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

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

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

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

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

Answer 8

Это выглядит хорошим: http://www.catonmat.net/blog/derivation-of-ycombinator/