Пытался изучить F #, но запутался, пытаясь различить свертку и свертку . Кажется, что Fold делает то же самое, но принимает дополнительный параметр. Есть ли законная причина для существования этих двух функций или они предназначены для людей с разным опытом? (Например: строка и строка в C #)
Вот фрагмент кода, скопированный из образца:
let sumAList list =
List.reduce (fun acc elem -> acc + elem) list
let sumAFoldingList list =
List.fold (fun acc elem -> acc + elem) 0 list
printfn "Are these two the same? %A "
(sumAList [2; 4; 10] = sumAFoldingList [2; 4; 10])
f#
functional-programming
reduce
fold
Уоллес
источник
источник
fold f a l
можно записать какreduce f a::l
.fold
в терминахreduce
более сложна - тип аккумулятораfold
не обязательно должен совпадать с типом вещей в списке!Ответы:
Fold
принимает явное начальное значение для аккумулятора, в то время какreduce
использует первый элемент входного списка в качестве начального значения аккумулятора.Это означает, что аккумулятор и, следовательно, тип результата должны соответствовать типу элемента списка, тогда как они могут отличаться,
fold
поскольку аккумулятор предоставляется отдельно. Это отражено в типах:Вдобавок
reduce
вызывает исключение для пустого списка ввода.источник
fold
, вы можете просто добавить это начальное значение в начало списка и сделатьreduce
? В чем тогда смыслfold
?'state -> 'a -> 'state
для fold vs'a -> 'a -> 'a
для уменьшения, поэтому сокращение ограничивает тип результата таким же, как тип элемента. См . Ответ Томаса Петричека ниже.В дополнение к тому, что сказал Ли, вы можете определить
reduce
в терминахfold
, но не (легко) наоборот:Тот факт, что
fold
для аккумулятора явно задано начальное значение, также означает, что результатfold
функции может иметь тип, отличный от типа значений в списке. Например, вы можете использовать аккумулятор типаstring
для объединения всех чисел в списке в текстовое представление:При использовании
reduce
тип аккумулятора совпадает с типом значений в списке - это означает, что если у вас есть список чисел, результатом должно быть число. Чтобы реализовать предыдущий пример, вам нужноstring
сначала преобразовать числа в, а затем накапливать:источник
fold' & its ability to express
сокращения ». Некоторые языки имеют концепцию структурной хиральности (Haskell, я смотрю на вас), вы можете складывать влево или вправо, визуально изображенные в этой вики ( en.wikipedia.org/wiki/Fold_%28higher-order_function ). С помощью конструкции идентичности два других «фундаментальных» оператора FP (filter и fmap) также могут быть реализованы с помощью существующей конструкции языка первого класса «fold» (все они изоморфные конструкции). ( cs.nott.ac.uk/~pszgmh/fold.pdf ) См .: HoTT, Princeton (Этот раздел комментариев слишком мал, чтобы содержать ..)Посмотрим на их подписи:
Есть несколько важных отличий:
reduce
работает только с одним типом элементов, элементы аккумулятора и спискаfold
могут быть разных типов.С помощью
reduce
вы применяете функциюf
к каждому элементу списка, начиная с первого:f (... (f i0 i1) i2 ...) iN
,С
fold
, вы применяетеf
начиная с аккумулятораs
:f (... (f s i0) i1 ...) iN
,Таким образом,
reduce
результаты вArgumentException
на пустом списке. Более того,fold
является более общим, чемreduce
; вы можете легкоfold
реализоватьreduce
.В некоторых случаях употребление
reduce
более лаконично:или удобнее, если нет разумного аккумулятора:
В общем,
fold
с аккумулятором произвольного типа мощнее:источник
fold
гораздо более ценная функция, чемreduce
. Вы можете определить множество различных функций в терминахfold
.reduce
это всего лишь частьfold
.Определение складки:
Примеры функций, определенных в терминах свертки:
источник
fold
разному отList.fold
как типаList.fold
IS('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
, но в вашем случае('a -> 'b -> 'b) -> 'b -> 'a list -> 'b
. Просто чтобы сделать это явным. Кроме того, ваша реализация добавления неверна. Это сработает, если вы добавите к нему привязку, напримерList.collect id (fold (fun x y -> x :: y) [] [xs;ys])
, или замените cons на оператор добавления. Таким образом, append - не лучший пример в этом списке.