В чем разница между свертыванием и уменьшением?

121

Пытался изучить 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])
Уоллес
источник
1
Вы можете написать сокращение и свернуть относительно друг друга, например, fold f a lможно записать как reduce f a::l.
Нил
9
@Neil - Реализация foldв терминах reduceболее сложна - тип аккумулятора foldне обязательно должен совпадать с типом вещей в списке!
Tomas Petricek
@TomasPetricek Моя ошибка, я изначально хотел написать наоборот.
Нил

Ответы:

171

Foldпринимает явное начальное значение для аккумулятора, в то время как reduceиспользует первый элемент входного списка в качестве начального значения аккумулятора.

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

List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
List.reduce : ('T -> 'T -> 'T) -> 'T list -> 'T

Вдобавок reduceвызывает исключение для пустого списка ввода.

подветренный
источник
В основном, вместо того, чтобы делать fold, вы можете просто добавить это начальное значение в начало списка и сделать reduce? В чем тогда смысл fold?
Pacerier
2
@Pacerier - функция аккумулятора для fold имеет другой тип: 'state -> 'a -> 'stateдля fold vs 'a -> 'a -> 'aдля уменьшения, поэтому сокращение ограничивает тип результата таким же, как тип элемента. См . Ответ Томаса Петричека ниже.
Ли
178

В дополнение к тому, что сказал Ли, вы можете определить reduceв терминах fold, но не (легко) наоборот:

let reduce f list = 
  match list with
  | head::tail -> List.fold f head tail
  | [] -> failwith "The list was empty!"

Тот факт, что foldдля аккумулятора явно задано начальное значение, также означает, что результат foldфункции может иметь тип, отличный от типа значений в списке. Например, вы можете использовать аккумулятор типа stringдля объединения всех чисел в списке в текстовое представление:

[1 .. 10] |> List.fold (fun str n -> str + "," + (string n)) ""

При использовании reduceтип аккумулятора совпадает с типом значений в списке - это означает, что если у вас есть список чисел, результатом должно быть число. Чтобы реализовать предыдущий пример, вам нужно stringсначала преобразовать числа в, а затем накапливать:

[1 .. 10] |> List.map string
          |> List.reduce (fun s1 s2 -> s1 + "," + s2)
Томаш Петричек
источник
2
Зачем определять сокращение так, чтобы оно могло вызывать ошибку во время выполнения?
Fresheyeball
+1 за замечание об общности 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, потому что при этом меньше предположений о типах и исключениях?
sksallaj
19

Посмотрим на их подписи:

> List.reduce;;
val it : (('a -> 'a -> 'a) -> 'a list -> 'a) = <fun:clo@1>
> List.fold;;
val it : (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) = <fun:clo@2-1>

Есть несколько важных отличий:

  • Хотя 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более лаконично:

// Return the last element in the list
let last xs = List.reduce (fun _ x -> x) xs

или удобнее, если нет разумного аккумулятора:

// Intersect a list of sets altogether
let intersectMany xss = List.reduce (fun acc xs -> Set.intersect acc xs) xss

В общем, foldс аккумулятором произвольного типа мощнее:

// Reverse a list using an empty list as the accumulator
let rev xs = List.fold (fun acc x -> x::acc) [] xs
подушечка
источник
18

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

reduceэто всего лишь часть fold.

Определение складки:

let rec fold f v xs =
    match xs with 
    | [] -> v
    | (x::xs) -> f (x) (fold f v xs )

Примеры функций, определенных в терминах свертки:

let sum xs = fold (fun x y -> x + y) 0 xs

let product xs = fold (fun x y -> x * y) 1 xs

let length xs = fold (fun _ y -> 1 + y) 0 xs

let all p xs = fold (fun x y -> (p x) && y) true xs

let reverse xs = fold (fun x y -> y @ [x]) [] xs

let map f xs = fold (fun x y -> f x :: y) [] xs

let append xs ys = fold (fun x y -> x :: y) [] [xs;ys]

let any p xs = fold (fun x y -> (p x) || y) false xs 

let filter p xs = 
    let func x y =
        match (p x) with
        | true -> x::y
        | _ -> y
    fold func [] xs
Раз Мегрелидзе
источник
1
Вы определяете свой по- foldразному от List.foldкак типа List.foldIS ('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 - не лучший пример в этом списке.
jpe