Разница между сгибом и уменьшением? - PullRequest
Новая
       59

Разница между сгибом и уменьшением?

113 голосов
/ 29 января 2012

Пытается выучить 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])

Ответы [ 4 ]

178 голосов
/ 29 января 2012

В дополнение к тому, что сказал Ли, вы можете определить 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)
160 голосов
/ 29 января 2012

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

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

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

Кроме того, reduce создает исключение в пустом списке ввода.

19 голосов
/ 29 января 2012

Давайте посмотрим на их подписи: 

> 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
16 голосов
/ 15 марта 2014

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
...