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

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


functional-programming fold catamorphism
person canadadry    schedule 04.05.2012    source источник
comment
Вы хотите сказать, что вам никогда не приходилось вычислять сумму списка в реальном мире?   -  person sepp2k    schedule 04.05.2012
comment
Я использую Python, поэтому, чтобы суммировать список, я просто делаю sum(alist). Таким образом, мне обычно не нужно запускать fold (или reduce в python) для достижения того же эффекта.   -  person canadadry    schedule 04.05.2012
comment
Хорошо, тогда возьмите следующую лучшую вещь: найдите произведение списка. Python не имеет этого встроенного. Конечно, это еще один очень упрощенный пример. Каждый раз, когда у вас есть цикл for, тело которого состоит из переназначения переменной, вы можете заменить его сверткой.   -  person sepp2k    schedule 04.05.2012
comment
Другие примеры: нахождение минимума, максимума, построение дерева или хэш-карты (из списка пар ключ-значение).   -  person Ingo    schedule 04.05.2012
comment
Почти любое вычисление, в котором вы обрабатываете элементы коллекции для получения некоторого результата, зависящего от всех элементов, может быть выражено как своего рода свертка. Полезность функций свертки не в том, что они естественным образом выражают какие-то конкретные конкретные примеры; самые естественные бетонные складки можно тривиально переписать другими методами. Полезность заключается в том, что вам не нужно писать каждый отдельный тривиальный пример, потому что свертывание покрывает все их.   -  person Ben    schedule 04.05.2012

Ответы (3)


arrow_upward
8
arrow_downward

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) []

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

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

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

person Don Stewart    schedule 04.05.2012

arrow_upward
1
arrow_downward

множество примеров foldleft следующие функции:

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

arrow_upward
0
arrow_downward

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

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

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

Классическая статья (поначалу довольно сложная) — Функциональное программирование с Бананы, Линзы,. Конверты и колючая проволока названы в честь других операторов.

person jJ'    schedule 05.05.2012