Différence entre plier et réduire?

121

Essayer d'apprendre F # mais être confus en essayant de faire la distinction entre plier et réduire . Fold semble faire la même chose mais prend un paramètre supplémentaire. Existe-t-il une raison légitime pour que ces deux fonctions existent ou sont-elles là pour accueillir des personnes d'horizons différents? (Par exemple: chaîne et chaîne en C #)

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

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
la source
1
Vous pouvez écrire réduire et plier l'un par rapport à l'autre, par exemple fold f a lpeut être écrit comme reduce f a::l.
Neil
9
@Neil - La mise folden œuvre en termes de reduceest plus compliquée que cela - le type d'accumulateur de foldn'a pas besoin d'être le même que le type de choses dans la liste!
Tomas Petricek
@TomasPetricek Mon erreur, j'avais initialement l'intention de l'écrire dans l'autre sens.
Neil

Réponses:

171

Foldprend une valeur initiale explicite pour l'accumulateur tandis que reduceutilise le premier élément de la liste d'entrée comme valeur initiale de l'accumulateur.

Cela signifie que l'accumulateur et donc le type de résultat doivent correspondre au type d'élément de liste, alors qu'ils peuvent différer foldcar l'accumulateur est fourni séparément. Cela se reflète dans les types:

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

De plus, reducelance une exception sur une liste d'entrée vide.

Lee
la source
Donc, fondamentalement, au lieu de faire fold, vous pouvez simplement ajouter cette valeur initiale au début de la liste et faire reduce? À quoi ça sert foldalors?
Pacerier
2
@Pacerier - La fonction d'accumulateur pour le pli a un type différent: 'state -> 'a -> 'statepour le pli vs 'a -> 'a -> 'apour réduire, ainsi la réduction contraint le type de résultat à être le même que le type d'élément. Voir la réponse de Tomas Petricek ci-dessous.
Lee
178

En plus de ce que Lee a dit, vous pouvez définir reduceen termes de fold, mais pas (facilement) l'inverse:

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

Le fait que cela foldprenne une valeur initiale explicite pour l'accumulateur signifie également que le résultat de la foldfonction peut avoir un type différent du type de valeurs dans la liste. Par exemple, vous pouvez utiliser un accumulateur de type stringpour concaténer tous les nombres d'une liste en une représentation textuelle:

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

Lors de l'utilisation reduce, le type d'accumulateur est le même que le type de valeurs dans la liste - cela signifie que si vous avez une liste de nombres, le résultat devra être un nombre. Pour implémenter l'exemple précédent, vous devez d'abord convertir les nombres string, puis les accumuler:

[1 .. 10] |> List.map string
          |> List.reduce (fun s1 s2 -> s1 + "," + s2)
Tomas Petricek
la source
2
Pourquoi définir réduire de telle sorte qu'il puisse générer des erreurs lors de l'exécution?
Fresheyeball
+1 pour la note sur la généralité de fold' & its ability to express réduire '. Certaines langues ont un concept de chiralité structurelle (Haskell je vous regarde) que vous pouvez replier à gauche ou à droite visuellement représenté dans ce wiki ( en.wikipedia.org/wiki/Fold_%28higher-order_function ). Avec une construction d'identité, les deux autres opérateurs FP «fondamentaux» (filtre et fmap) sont également implémentables avec une construction de langage de première classe «fold» existante (ce sont toutes des constructions isomorphes). ( cs.nott.ac.uk/~pszgmh/fold.pdf ) Voir: HoTT, Princeton (Cette section de commentaires est trop petite pour contenir ..)
Andrew
Par curiosité ... est-ce que cela rendrait la performance de la réduction plus rapide que celle du repli parce que c'est sous moins d'hypothèses sur les types et les exceptions?
sksallaj
19

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 existe des différences importantes:

  • Bien que cela ne reducefonctionne que sur un seul type d'éléments, les éléments d'accumulateur et de liste dans foldpeuvent être de types différents.
  • Avec reduce, vous appliquez une fonction fà chaque élément de liste en commençant par le premier:

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

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

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

Par conséquent, il en reducerésulte une ArgumentExceptionliste vide. De plus, foldest plus générique que reduce; vous pouvez utiliser foldpour mettre en œuvre reducefacilement.

Dans certains cas, l'utilisation reduceest plus succincte:

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

ou plus pratique s'il n'y a pas d'accumulateur raisonnable:

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

En général, foldest plus puissant avec un accumulateur de type arbitraire:

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

foldest une fonction beaucoup plus précieuse que reduce. Vous pouvez définir de nombreuses fonctions différentes en termes de fold.

reduceest juste un sous-ensemble de fold.

Définition du pli:

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

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
la source
1
Vous définissez votre folddifféremment List.foldcomme le type de List.foldest ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a, mais dans votre cas ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b. Juste pour le rendre explicite. De plus, votre implémentation de append est incorrecte. Cela fonctionnerait si vous y ajoutez une liaison, par exemple List.collect id (fold (fun x y -> x :: y) [] [xs;ys]), ou si vous remplacez cons par l'opérateur append. L'ajout n'est donc pas le meilleur exemple de cette liste.
jpe