Differenza tra piega e riduzione?

Question

Cercando di imparare F # ma è stato confuso quando si cerca di distinguere tra fold e reduce. Fold sembra fare lo same thing ma prende un parametro extra. C'è una ragione legittima per queste due funzioni di esistere o sono lì per ospitare persone con background diversi? (Ad esempio: String e stringa in C#)

Ecco frammento di codice copiati dal campione:

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 assume un valore iniziale esplicita per dell'accumulatore mentre reduce utilizza il primo elemento della lista di input come l'iniziale valore dell'accumulatore.

Ciò significa che l'accumulatore e il tipo di risultato devono corrispondere al tipo di elemento dell'elenco, mentre possono differire in fold poiché l'accumulatore viene fornito separatamente. Ciò si riflette nel tipo:

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

Inoltre reduce genera un'eccezione su un elenco di inserimento vuoto.

Answer 2

In aggiunta a quanto detto Lee è possibile definire reduce, in termini di fold, ma non (facilmente) il contrario:

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

Il fatto che fold prende un valore iniziale esplicita per l'accumulatore anche significa che il risultato della funzione fold può avere un tipo diverso dal tipo di valori nell'elenco. Ad esempio, è possibile utilizzare l'accumulatore di tipo string per concatenare tutti i numeri in un elenco in una rappresentazione testuale:

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

Quando si utilizza reduce, il tipo di accumulatore è lo stesso che il tipo di valori nella lista - questo significa che se hai una lista di numeri, il risultato sarà un numero. Per implementare l'esempio precedente, che avrebbe dovuto convertire i numeri per string prima e poi si accumulano:

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

Answer 3

Vediamo le loro firme:

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

Ci sono alcune importanti differenze:

• Mentre reduce funziona solo su un tipo di elementi, gli elementi dell'accumulatore e dell'elenco in fold potrebbero essere di tipi diversi.

• Con reduce, si applica una funzione di f per ogni elemento della lista a partire dal primo:

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

  Con fold, si applica a partire dal f dell'accumulatore s:

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

Pertanto, reduce traduca in un ArgumentException sulla lista vuota. Inoltre, fold è più generico di reduce; è possibile utilizzare fold per implementare facilmente reduce.

In alcuni caso, utilizzando reduce è più succinta:

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

o più conveniente se non c'è alcun accumulatore ragionevole:

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

In generale fold è più potente di un accumulatore di un tipo arbitrario:

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

Answer 4

fold è una funzione molto più valida di reduce. È possibile definire molte funzioni diverse in termini di fold.

reduce è solo un sottoinsieme di fold.

Definizione di piega:

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

Esempi di funzioni definite in termini di piega:

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