Практическое использование сложения / уменьшения в функциональных языках

Question

Fold (он же reduce) считается очень важной функцией высшего порядка.Map можно выразить в виде fold ( см. Здесь ).Но для меня это звучит скорее академично, чем практично.Типичным использованием может быть получение суммы, или продукта, или максимума чисел, но эти функции обычно принимают любое количество аргументов.Так зачем писать (fold + 0 '(2 3 5)), когда (+ 2 3 5) работает нормально.У меня вопрос, в какой ситуации проще или естественнее использовать fold?

Answer 1

Смысл fold в том, что он более абстрактный. Дело не в том, что вы можете делать то, что раньше не могли, а в том, что вы можете делать это легче.

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

Поскольку fold (и в этом отношении map, filter и друзья) имеют четко определенное поведение, зачастую понять код с помощью этих функций гораздо проще, чем явной рекурсии.

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

Answer 2

Вот несколько простых примеров, когда reduce работает очень хорошо.

Найти сумму максимальных значений каждого подсписка

Clojure:

user=> (def x '((1 2 3) (4 5) (0 9 1)))
#'user/x
user=> (reduce #(+ %1 (apply max %2)) 0 x)
17

Ракетка:

> (define x '((1 2 3) (4 5) (0 9 1)))
> (foldl (lambda (a b) (+ b (apply max a))) 0 x)
17

Построить карту из списка

Clojure:

user=> (def y '(("dog" "bark") ("cat" "meow") ("pig" "oink")))
#'user/y
user=> (def z (reduce #(assoc %1 (first %2) (second %2)) {} y))
#'user/z
user=> (z "pig")
"oink"

Для более сложного примера clojure с reduce проверьте мое решение для задач Project Euler 18 & 67 .

См. Также: уменьшить или применить

Answer 3

В функциях Common Lisp не принимают любое количество аргументов.

В каждой реализации Common Lisp определена константа CALL-ARGUMENTS-LIMIT , которая должна быть 50 или больше.

Это означает, что любая такая переносимая функция должна принимать не менее 50 аргументов.Но это может быть всего 50.

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

Таким образомчтобы действительно обрабатывать большие (более 50 элементов) списки или векторы в переносимом коде Common Lisp, необходимо использовать итерационные конструкции, Reduction, Map и тому подобное.Таким образом, также необходимо не использовать (apply '+ large-list), а использовать (reduce '+ large-list).

Answer 4

Код с использованием Fold обычно неудобно читать. Вот почему люди предпочитают карту, фильтр, существует, сумма и т. Д., Если они доступны. В эти дни я пишу в основном компиляторы и интерпретаторы; Вот несколько способов, которыми я использую Fold:

• Вычислить набор свободных переменных для функции, выражения или типа
• Добавить параметры функции в таблицу символов, например, для проверки типа
• Накапливать сбор всех разумных сообщений об ошибках, сгенерированных из последовательности определений
• Добавить все предопределенные классы в интерпретатор Smalltalk во время загрузки

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

Answer 5

1. Ваш пример (+ 2 3 4) работает только потому, что вы заранее знаете количество аргументов. Складки работают со списками, размер которых может варьироваться.

2. fold / reduce - это общая версия шаблона «составление списка». Каждый алгоритм предназначен для обработки каждого элемента последовательности по порядку и вычисления некоторого возвращаемого значения, которое можно выразить с его помощью. Это в основном функциональная версия цикла foreach.

Answer 6

Вот пример, который еще никто не упомянул.

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

Ваш пример тривиален: + уже принимает любое количество аргументов, работает быстро в малой памяти и уже былнаписано и отлажено тем, кто написал ваш компилятор.Эти свойства не всегда верны для алгоритмов, которые мне нужно запустить.