Différence entre les plier et de les réduire?

Question

Essayez d'apprendre le F# mais suis confus en essayant de distinguer entre les plier et de les réduire. Plier semble faire la même chose , mais prend un paramètre supplémentaire. Est-il une raison légitime pour ces deux fonctions existent pas ou qu'ils sont là pour accueillir des personnes avec différents milieux? (E. g.: Chaîne et chaîne en C#)

Voici un extrait de code copié à partir de l'échantillon:

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

En plus de ce que Lee a dit, vous pouvez définir reduce en termes de fold, mais pas (facilement) dans l'autre sens:

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

Le fait qu' fold prend explicitement la valeur initiale de l'accumulateur-signifie également que le résultat de l' fold fonction peut avoir un autre type que le type de valeurs dans la liste. Par exemple, vous pouvez utiliser l'accumulateur de type string pour concaténer tous les numéros dans une liste dans une représentation textuelle:

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

Lors de l'utilisation d' reduce, le type d'accumulateur est le même que le type de valeurs dans la liste, ce qui signifie que si vous avez une liste de nombres, le résultat devra être un nombre. Pour mettre en œuvre l'exemple précédent, vous devez convertir les nombres d' string d'abord, puis s'accumulent:

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

Answer 2

Fold prend explicitement la valeur initiale de l'accumulateur alors qu' reduce utilise le premier élément de la liste de saisie initiale de l'accumulateur de valeur.

En conséquence, reduce déclenche une exception sur un vide de la liste d'entrée.

Answer 3

Regardons leurs signatures:

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

Il y a quelques différences importantes:

• Alors qu' reduce fonctionne sur un seul type d'éléments seulement, l'accumulateur et les éléments de liste dans fold pourraient être de différents types.

• Avec reduce, vous appliquez une fonction f pour chaque élément de la liste de départ de la première:

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

  Avec fold, vous appliquez f à partir de l'accumulateur s:

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

Par conséquent, reduce résultats en ArgumentException sur liste vide. De plus, en fold est plus générique que l' reduce; vous pouvez utiliser fold à mettre en oeuvre reduce facilement.

Dans certains cas, l'utilisation d' reduce est plus succinct:

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

ou plus pratique si il n'est pas raisonnable de l'accumulateur:

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

En général, fold est plus puissant avec un accumulateur d'un type arbitraire:

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

Answer 4

fold est beaucoup plus utile que d' reduce. Vous pouvez définir plusieurs fonctions différentes en termes de fold.

reduce est juste un sous-ensemble de l' fold.

Définition des objectifs:

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

Exemples de fonctions définies en termes de fois:

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