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])
f#
functional-programming
reduce
fold
Wallace
źródło
źródło
fold f a l
Można zapisać jakoreduce f a::l
.fold
w kategoriachreduce
jest bardziej skomplikowana - rodzaj akumulatorafold
nie musi być taki sam jak typ rzeczy na liście!Odpowiedzi:
Fold
przyjmuje jawną wartość początkową akumulatora, podczas gdyreduce
uż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ć,
fold
ponieważ akumulator jest dostarczany oddzielnie. Znajduje to odzwierciedlenie w typach:Dodatkowo
reduce
zgłasza wyjątek na pustej liście wejściowej.źródło
fold
, możesz po prostu dodać tę wartość początkową na początku listy i zrobićreduce
? Jaki to ma sensfold
?'state -> 'a -> 'state
dla fold vs'a -> 'a -> 'a
dla redukcji, więc redukuj ograniczenia, aby typ wyniku był taki sam jak typ elementu. Zobacz odpowiedź Tomasa Petricka poniżej.Oprócz tego, co powiedział Lee, możesz zdefiniować
reduce
w kategoriachfold
, ale nie (łatwo) na odwrót:Fakt, że
fold
przyjmuje jawną wartość początkową akumulatora, oznacza również, że wynikfold
funkcji może mieć inny typ niż typ wartości na liście. Na przykład, możesz użyć akumulatora typu,string
aby połączyć wszystkie liczby na liście w tekstową reprezentację:Podczas używania
reduce
typ 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,string
a następnie skumulować:źródło
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ć ..)Spójrzmy na ich podpisy:
Istnieje kilka ważnych różnic:
reduce
działa tylko na jednym typie elementów, elementy akumulatora i listy w programiefold
mogą być różnych typów.W programie
reduce
stosuje się funkcjęf
do każdego elementu listy, zaczynając od pierwszego:f (... (f i0 i1) i2 ...) iN
.Dzięki
fold
, zastosowaniuf
wychodząc z akumulatorems
:f (... (f s i0) i1 ...) iN
.Dlatego
reduce
powodujeArgumentException
wyświetlenie pustej listy. Ponadtofold
jest bardziej ogólny niżreduce
; możesz użyćfold
doreduce
łatwego wdrożenia .W niektórych przypadkach użycie
reduce
jest bardziej zwięzłe:lub wygodniej, jeśli nie ma żadnego rozsądnego akumulatora:
Ogólnie rzecz biorąc,
fold
jest mocniejszy z akumulatorem dowolnego typu:źródło
fold
jest znacznie bardziej wartościową funkcją niżreduce
. Możesz zdefiniować wiele różnych funkcji w zakresiefold
.reduce
jest tylko podzbioremfold
.Definicja fałdy:
Przykłady funkcji zdefiniowanych pod kątem krotnie:
źródło
fold
inaczej niżList.fold
jako typList.fold
Is('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.