Różnica między krotnie i zmniejszyć?

Question

Próbujesz nauczyć się F #, ale mylić, próbując rozróżnić między fold i reduce. Fold wydaje się robić same thing, ale przyjmuje dodatkowy parametr. Czy istnieje uzasadniony powód, by te dwie funkcje istniały, czy też są one dostępne dla osób o różnym pochodzeniu? (Np: String i ciąg w C#)

Oto fragment kodu skopiowany z próbką:

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

Answer 1

Fold zajmuje wyraźną wartość początkową na akumulatorze podczas reduce używa pierwszego elementu listy wejściowej jako początkowy wartość akumulatora.

Oznacza to, że akumulator, a więc typ wyniku musi być zgodny z typem elementu listy, podczas gdy mogą się różnić w fold, ponieważ akumulator jest dostarczany osobno. Znajduje to odzwierciedlenie w rodzajach:

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

Ponadto reduce zgłasza wyjątek na liście wejściowej pusty.

Answer 2

Oprócz tego, co powiedział Lee, można zdefiniować reduce pod względem fold, ale nie (łatwo) na odwrót:

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

Fakt fold zajmuje wyraźną wartość początkową na akumulatorze również oznacza, że ​​wynik funkcji fold może mieć inny typ niż typ wartości na liście. Na przykład, można użyć akumulatora typu string aby złączyć wszystkie numery na liście do tekstowej reprezentacji:

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

Podczas korzystania reduce, typ akumulatora jest taki sam jak typ wartości na liście - to oznacza, że ​​jeśli masz listę liczb, wynik musi być liczbą. W celu realizacji poprzedniej próbki, trzeba przekonwertować numery do string a potem gromadzić:

[1 .. 10] |> List.map string 
      |> List.reduce (fun s1 s2 -> s1 + "," + s2) 

Answer 3

Spójrzmy na ich podpisów:

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

Istnieją pewne istotne różnice:

• Podczas gdy reduce działa tylko na jednym typie elementów, elementy akumulatora i listy w fold mogą być w różnych typach.

• Z reduce, zastosować funkcję f do każdego elementu listy, począwszy od pierwszego:

  f (... (f i0 i1) i2 ...) iN.

  Z fold, zastosować f począwszy od akumulatora s:

  f (... (f s i0) i1 ...) iN.

Dlatego reduce skutkuje ArgumentException na pustą listę. Ponadto, fold jest bardziej ogólny niż reduce; możesz użyć fold, aby łatwo wdrożyć reduce.

W niektórych przypadkach, przy użyciu reduce jest bardziej zwięzły:

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

lub bardziej wygodne, jeśli nie ma tam każdy rozsądny akumulatorowe:

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

Ogólnie fold jest mocniejszy z akumulatorem od An dowolny typ:

// Reverse a list using an empty list as the accumulator 
let rev xs = List.fold (fun acc x -> x::acc) [] xs 

Answer 4

fold jest znacznie bardziej wartościową funkcją niż reduce. Możesz zdefiniować wiele różnych funkcji w zakresie fold.

reduce to tylko podzbiór fold.

Definicja owczarni

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

Przykłady funkcji określonych w zakresie owczarni

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