Объяснение комбинаторов для рабочего человека

Что такое комбинатор ??

Это «функция или определение без свободных переменных» (как определено в SO)?

Или как насчет этого: согласно Джону Хьюзу в его известной статье о стрелах, «комбинатор - это функция, которая строит фрагменты программы из фрагментов программы» , что выгодно, потому что «... программист, использующий комбинаторы, создает большую часть желаемого программировать автоматически, а не писать каждую деталь вручную ». Он продолжает это говорить mapи filterприводит два распространенных примера таких комбинаторов.

Некоторые комбинаторы, соответствующие первому определению:

• S
• K
• Y
• другие из To Mock a Mockingbird (я могу ошибаться - я не читал эту книгу)

Некоторые комбинаторы, соответствующие второму определению:

• карта
• фильтр
• сложить / уменьшить (предположительно)
• любой из >> =, compose, fmap ?????

Меня не интересует первое определение - оно не поможет мне написать настоящую программу (+1, если вы меня убедите, что я ошибаюсь). Пожалуйста, помогите мне понять второе определение . Я считаю, что map, filter и reduce полезны: они позволяют мне программировать на более высоком уровне - меньше ошибок, короче и понятнее код. Вот некоторые из моих конкретных вопросов о комбинаторах:

1. Какие еще примеры комбинаторов, таких как карта, фильтр?
2. Какие комбинаторы часто реализуют языки программирования?
3. Как комбинаторы могут помочь мне разработать лучший API?
4. Как создать эффективные комбинаторы?
5. Какие комбинаторы похожи на комбинаторы в нефункциональном языке (скажем, Java) или что эти языки используют вместо комбинаторов?

Обновить

Благодаря @CA McCann я теперь немного лучше понимаю комбинаторы. Но один вопрос все еще остается камнем преткновения для меня:

В чем разница между функциональной программой, написанной с интенсивным использованием комбинаторов, и программой, написанной без них?

Я подозреваю, что ответ заключается в том, что версия с большим количеством комбинаторов короче, яснее и более общая, но я был бы признателен за более подробное обсуждение, если это возможно.

Я также ищу больше примеров и объяснений сложных комбинаторов (то есть более сложных, чем fold) в обычных языках программирования.

Меня не интересует первое определение - оно не поможет мне написать настоящую программу (+1, если вы меня убедите, что я ошибаюсь). Пожалуйста, помогите мне понять второе определение. Я считаю, что map, filter и reduce полезны: они позволяют мне программировать на более высоком уровне - меньше ошибок, короче и понятнее код.

Эти два определения в основном одно и то же. Первый основан на формальном определении, и приведенные вами примеры являются примитивными комбинаторами - наименьшими возможными строительными блоками. Они могут помочь вам написать настоящую программу, поскольку с их помощью вы сможете создавать более сложные комбинаторы. Думайте о комбинаторах, таких как S и K, как о машинном языке гипотетического «комбинаторного компьютера». Настоящие компьютеры, конечно, так не работают, поэтому на практике вы обычно будете выполнять высокоуровневые операции за кулисами другими способами, но концептуальная основа по-прежнему является полезным инструментом для понимания значения этих высокоуровневых операций. операции.

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

Какие еще примеры комбинаторов, таких как карта, фильтр?

Слишком много, чтобы перечислить! Обе они преобразуют функцию, описывающую поведение одного значения, в функцию, описывающую поведение всей коллекции. У вас также могут быть функции, которые преобразуют только другие функции, например, их составление от начала до конца или разделение и повторное объединение аргументов. У вас могут быть комбинаторы, которые превращают пошаговые операции в рекурсивные операции, которые создают или потребляют коллекции. Или на самом деле все, что угодно.

Какие комбинаторы часто реализуют языки программирования?

Это будет немного отличаться. Полностью универсальных комбинаторов относительно мало - в основном примитивные, упомянутые выше, - поэтому в большинстве случаев комбинаторы будут иметь некоторое представление о любых используемых структурах данных (даже если эти структуры данных в любом случае построены из других комбинаторов), в которых случае обычно есть несколько «полностью универсальных» комбинаторов, а затем любые различные специализированные формы, которые кто-то решил предоставить. Существует смехотворное количество случаев, когда (подходящих обобщенных версий) map, fold и разворачивание достаточно, чтобы делать почти все, что вы можете захотеть.

Как комбинаторы могут помочь мне разработать лучший API?

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

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

Как создать эффективные комбинаторы?

Во-первых, подумайте, какие операции имеют смысл с данными, которые использует ваша программа. Затем подумайте, как эти операции могут быть осмысленно объединены общими способами, а также как операции могут быть разбиты на более мелкие части, которые снова соединены вместе. Главное - работать с преобразованиями и операциями , а не с прямыми действиями . Когда у вас есть функция, которая просто непрозрачно выполняет некоторые сложные функции и выдает только какой-то предварительно обработанный результат, вы мало что можете с этим поделать. Оставьте окончательные результаты коду, который использует комбинаторы - вам нужны вещи, которые доставят вас из точки A в точку B, а не вещи, которые должны стать началом или концом процесса.

Какие комбинаторы похожи на комбинаторы в нефункциональном языке (скажем, Java) или что эти языки используют вместо комбинаторов?

Ахахахаха. Забавно, что вы должны спросить, потому что объекты на самом деле в первую очередь штуки высшего порядка - у них есть некоторые данные, но они также несут кучу операций, и довольно много того, что составляет хороший дизайн ООП, сводится к тому, что «объекты должны обычно действуют как комбинаторы, а не как структуры данных ».

Поэтому, вероятно, лучший ответ здесь заключается в том, что вместо вещей, подобных комбинатору, они используют классы с большим количеством методов получения и установки или общедоступных полей и логику, которая в основном состоит из выполнения некоторых непрозрачных, предопределенных действий.