Кто-нибудь получил хорошее объяснение "комбинаторов" (Y-комбинаторы и т.д., а не компания)
Я ищу один для практического программиста, который понимает рекурсию и функции более высокого порядка, но не имеет сильной теории или математического фона.
(Обратите внимание, что я говорю об этих вещах: http://en.wikipedia.org/wiki/Y_combinator)
Если вы глубоко вникаете в теорию, вы можете оценить Y combinator как опрятный трюк с функциями, как монады.
Монады позволяют вам цепочки действий, Y combinator позволяет вам определить саморекурсивные функции.
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%, но я думаю, что это общая идея.)
Реджинальд Брейтуэйт (он же Раганвальд) пишет в своем новом блоге великолепную серию о комбинаторах в Ruby, homoiconic.
Пока он (насколько мне известно) не смотрит на сам Y-combinator, он смотрит на другие комбинаторы, например:
и несколько сообщений о том, как вы можете использовать их.
Цитата Википедия:
Комбинатор представляет собой функцию более высокого порядка, которая использует только приложение-приложение и ранее определенные комбинаторы для определения результата из своих аргументов.
Что это значит? Это означает, что комбинатор является функцией (выход определяется исключительно его входом), вход которого включает функцию в качестве аргумента.
Как выглядят такие функции и для чего они используются? Вот несколько примеров:
(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, но я туда не поеду.
Комбинатор работает с без свободных переменных. Это означает, среди прочего, что комбинатор не имеет зависимостей от вещей вне функции, только от параметров функции.
Используя 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 вызывает lambda, которая передается как один из аргументов.
Вот один из наиболее понятных разборчиков комбинаторов, который я нашел:
Это выглядит неплохо: http://www.catonmat.net/blog/derivation-of-ycombinator/
Это хорошая статья:
http://www.dreamsongs.com/NewFiles/WhyOfY.pdf
Примеры кода приведены в схеме, но с ними не должно быть трудно следовать.
Я довольно коротко отношусь к теории, но я могу привести пример, который заставляет мое воображение вздыматься, что может быть полезно для вас. Самый простой интересный комбинатор, вероятно, "тест".
Надеюсь, вы знаете 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 оценивает второй аргумент, если первый аргумент истинен, в противном случае третий.
>>> x = tru
>>> test(x,"goto loop","break")
'goto loop'
Целые системы могут быть созданы из нескольких основных комбинаторов.
(Этот пример более или менее скопирован из типов и языков программирования Бенджамином С. Пирсом)
Вскоре Y combinator является функцией более высокого порядка, которая используется для реализации рекурсии на лямбда-выражениях (анонимные функции). Проверьте статью Как добиться успеха в рекурсии без реальной рекурсии Майком Ванье - это одно из лучших практических объяснений этого вопроса, которое я видел.
Также сканируйте архивы SO: