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

121

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])
Wallace
źródło
1
Możesz pisać zmniejszać i składać względem siebie, np. fold f a lMożna zapisać jako reduce f a::l.
Neil
9
@Neil - Implementacja foldw kategoriach reducejest bardziej skomplikowana - rodzaj akumulatora foldnie musi być taki sam jak typ rzeczy na liście!
Tomas Petricek
@TomasPetricek Mój błąd, pierwotnie zamierzałem napisać to na odwrót.
Neil

Odpowiedzi:

171

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.

Zawietrzny
źródło
Więc w zasadzie zamiast robić fold, możesz po prostu dodać tę wartość początkową na początku listy i zrobić reduce? Jaki to ma sens fold?
Pacerier,
2
@Pacerier - Funkcja akumulacyjna dla fold ma inny typ: 'state -> 'a -> 'statedla fold vs 'a -> 'a -> 'adla redukcji, więc redukuj ograniczenia, aby typ wyniku był taki sam jak typ elementu. Zobacz odpowiedź Tomasa Petricka poniżej.
Lee,
178

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)
Tomas Petricek
źródło
2
Po co definiować redukcję tak, aby mogła powodować błędy w czasie wykonywania?
Fresheyeball
+1 za uwagę na ogólność fold' & its ability to express redukcji ”. Niektóre języki mają koncepcję chiralności strukturalnej (Haskell patrzę na ciebie), którą możesz złożyć w lewo lub w prawo, przedstawioną wizualnie na tej wiki ( en.wikipedia.org/wiki/Fold_%28higher-order_function ). W przypadku konstrukcji tożsamości pozostałe dwa „podstawowe” operatory FP (filtr i fmap) są również możliwe do zaimplementowania za pomocą istniejącej konstrukcji języka pierwszej klasy, która jest składana (wszystkie są konstrukcjami izomorficznymi). ( cs.nott.ac.uk/~pszgmh/fold.pdf ) Patrz: HoTT, Princeton (Ta sekcja komentarzy jest zbyt mała, aby ją pomieścić ..)
Andrew
Z ciekawości… czy spowodowałoby to szybsze zmniejszenie wydajności niż spasowanie, ponieważ przyjmuje mniej założeń dotyczących typów i wyjątków?
sksallaj
19

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
Podkładka
źródło
18

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
Raz Megrelidze
źródło
1
Zdefiniować swoją foldinaczej niż List.foldjako typ List.foldIs ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a, ale w twoim przypadku ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b. Tylko po to, żeby było to jasne. Ponadto twoja implementacja dołączania jest nieprawidłowa. To zadziała, jeśli dodasz do niego bind, np. List.collect id (fold (fun x y -> x :: y) [] [xs;ys])Lub zastąpisz minusy operatorem dołączania. Dlatego dołączanie nie jest najlepszym przykładem na tej liście.
jpe