Каковы практические примеры функций высшего порядка foldl и foldr?

Question

Типичным академическим примером является подведение списка. Существуют ли реальные примеры использования сгиба, которые проливают свет на его полезность?

Answer 1

fold пожалуй, самая фундаментальная операция над последовательностями. Просить о его полезности все равно что просить о полезности for цикл в императивном языке.

Учитывая список (или массив, или дерево, или..), начальное значение и функцию, fold Оператор сводит список к одному результату. Это также естественный катаморфизм (деструктор) для списков.

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

sum      = fold (+) 0

length   = fold (λx n → 1 + n) 0

reverse  = fold (λx xs → xs ++ [x]) []

map f    = fold (λx ys → f x : ys) []

filter p = fold (λx xs → if p x then x : xs else xs) []

Оператор свертки не является специфичным для списков, но может быть обобщен единообразным способом для "обычных" типов данных.

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

---

Рекомендации:

• Учебник по универсальности и выразительности складки
• Написание фолдл в терминах фолд
• На складках

Answer 2

Много и много примеров foldLeft перечисляет следующие функции:

• сумма
• товар
• подсчитывать
• средний
• прошлой
• предпоследний
• содержит
• получить
• нанизывать
• задний ход
• уникальный
• установить
• двойной
• сортировка вставок
• пивот (часть быстрой сортировки)
• кодировать (считать последовательные элементы)
• декодировать (генерировать последовательные элементы)
• группа (в подсписки четных размеров)

Answer 3

Мой хромой ответ таков:

• Foldr предназначен для того, чтобы свести проблему к примитивному случаю и затем собрать обратно (ведет себя как нерекурсивная рекурсия).
• Foldl предназначен для уменьшения проблемы и сборки решения на каждом шаге, где в примитивном случае у вас есть готовое решение (ведет себя как хвостовая рекурсия / итерация)

Этот вопрос сразу напомнил мне разговор Ральфа Ламмеля Гоинга Банана (поскольку запись оператора rfold выглядит как банан (| и |)). Есть довольно наглядные примеры отображения рекурсии в складки и даже в одну складку в другую.

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