Różnica między spasowaniem a redukcją?

Próbuje dowiedzieć się F #, ale irytować, gdy próbuje odróżnić krotnie i zmniejszyć . Fold wydaje się robić to samo, ale ma dodatkowy parametr. Czy istnieje uzasadniony powód, dla którego te dwie funkcje istnieją, czy też mają one służyć osobom z różnych środowisk? (Np .: ciąg i ciąg w C #)

Oto fragment kodu skopiowany z przykładu:

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

Foldprzyjmuje jawną wartość początkową akumulatora, podczas gdy reduceużywa pierwszego elementu listy wejściowej jako początkowej wartości akumulatora.

Oznacza to, że akumulator, a tym samym typ wyniku, musi pasować do typu elementu listy, podczas gdy mogą się różnić, foldponieważ akumulator jest dostarczany oddzielnie. Znajduje to odzwierciedlenie w typach:

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

Dodatkowo reducezgłasza wyjątek na pustej liście wejściowej.

Oprócz tego, co powiedział Lee, możesz zdefiniować reducew kategoriach 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, że foldprzyjmuje jawną wartość początkową akumulatora, oznacza również, że wynik foldfunkcji może mieć inny typ niż typ wartości na liście. Na przykład, możesz użyć akumulatora typu, stringaby połączyć wszystkie liczby na liście w tekstową reprezentację:

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

Podczas używania reducetyp akumulatora jest taki sam, jak typ wartości na liście - oznacza to, że jeśli masz listę liczb, wynikiem będzie liczba. Aby zaimplementować poprzednią próbkę, musisz najpierw przekonwertować liczby na, stringa następnie skumulować:

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

Spójrzmy na ich podpisy:

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

Istnieje kilka ważnych różnic:

• Chociaż reducedziała tylko na jednym typie elementów, elementy akumulatora i listy w programie foldmogą być różnych typów.

• W programie reducestosuje się funkcję fdo każdego elementu listy, zaczynając od pierwszego:

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

  Dzięki fold, zastosowaniu fwychodząc z akumulatorem s:

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

Dlatego reducepowoduje ArgumentExceptionwyświetlenie pustej listy. Ponadto foldjest bardziej ogólny niż reduce; możesz użyć folddo reducełatwego wdrożenia .

W niektórych przypadkach użycie reducejest bardziej zwięzłe:

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

lub wygodniej, jeśli nie ma żadnego rozsądnego akumulatora:

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

Ogólnie rzecz biorąc, foldjest mocniejszy z akumulatorem dowolnego typu:

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

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

reducejest tylko podzbiorem fold.

Definicja fałdy:

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

Przykłady funkcji zdefiniowanych pod kątem krotnie:

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