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

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

Если вы не глубоко разбираетесь в теории, вы можете рассмотреть комбинатор 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%, но я думаю, что это общая идея.)

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

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

• Пустельга
• Дрозд
• Кардинал
• Obdurate пустельга
• другие Причудливые птицы

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

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

Надеюсь, ты знаешь 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'

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

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

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

A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.

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

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

(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, но я не буду вдаваться в подробности.

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

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

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

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

Используя 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. Т.е. Вместо того, чтобы вызывать себя, рекурсивная функция вызывает лямбда-выражение, которое передается в качестве одного из аргументов.

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

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

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