Recherche…
Introduction aux plis, avec quelques exemples
Les plis sont des fonctions (d'ordre supérieur) utilisées avec des séquences d'éléments. Ils réduisent seq<'a> en 'b où 'b est n'importe quel type (peut-être encore 'a ). Ceci est un peu abstrait, alors allons dans des exemples pratiques concrets.
Calcul de la somme de tous les nombres
Dans cet exemple, 'a est un int . Nous avons une liste de nombres et nous voulons calculer la somme de tous les nombres. Pour résumer les numéros de la liste [1; 2; 3] nous écrivons
List.fold (fun x y -> x + y) 0 [1; 2; 3] // val it : int = 6
Permettez-moi de vous expliquer, car nous avons affaire à des listes, nous utilisons fold dans le module List , donc List.fold . le premier argument fold est une fonction binaire, le dossier . Le second argument est la valeur initiale . fold commence à plier la liste en appliquant consécutivement la fonction de dossier aux éléments de la liste en commençant par la valeur initiale et le premier élément. Si la liste est vide, la valeur initiale est renvoyée!
La vue d'ensemble schématique d'un exemple d'exécution ressemble à ceci:
let add x y = x + y // this is our folder (a binary function, takes two arguments)
List.fold add 0 [1; 2; 3;]
=> List.fold add (add 0 1) [2; 3]
// the binary function is passed again as the folder in the first argument
// the initial value is updated to add 0 1 = 1 in the second argument
// the tail of the list (all elements except the first one) is passed in the third argument
// it becomes this:
List.fold add 1 [2; 3]
// Repeat untill the list is empty -> then return the "inital" value
List.fold add (add 1 2) [3]
List.fold add 3 [3] // add 1 2 = 3
List.fold add (add 3 3) []
List.fold add 6 [] // the list is empty now -> return 6
6
La fonction List.sum est approximativement List.fold add LanguagePrimitives.GenericZero où le zéro générique le rend compatible avec les entiers, les flottants, les grands entiers, etc.
Comptage des élémets dans une liste ( count implémentation)
Cela se fait presque comme ci-dessus, mais en ignorant la valeur réelle de l'élément dans la liste et en ajoutant 1.
List.fold (fun x y -> x + 1) 0 [1; 2; 3] // val it : int = 3
Cela peut aussi être fait comme ceci:
[1; 2; 3]
|> List.map (fun x -> 1) // turn every elemet into 1, [1; 2; 3] becomes [1; 1; 1]
|> List.sum // sum [1; 1; 1] is 3
Donc, vous pouvez définir count comme suit:
let count xs =
xs
|> List.map (fun x -> 1)
|> List.fold (+) 0 // or List.sum
Trouver le maximum de liste
Cette fois, nous utiliserons List.reduce comme List.fold mais sans valeur initiale, car dans ce cas, nous ne connaissons pas le type des valeurs que nous comparons:
let max x y = if x > y then x else y
// val max : x:'a -> y: 'a -> 'a when 'a : comparison, so only for types that we can compare
List.reduce max [1; 2; 3; 4; 5] // 5
List.reduce max ["a"; "b"; "c"] // "c", because "c" > "b" > "a"
List.reduce max [true; false] // true, because true > false
Trouver le minimum d'une liste
Tout comme pour trouver le max, le dossier est différent
let min x y = if x < y then x else y
List.reduce min [1; 2; 3; 4; 5] // 1
List.reduce min ["a"; "b"; "c"] // "a"
List.reduce min [true; false] // false
Listes concaténantes
Ici, nous prenons la liste des listes La fonction de dossier est l'opérateur @
// [1;2] @ [3; 4] = [1; 2; 3; 4]
let merge xs ys = xs @ ys
List.fold merge [] [[1;2;3]; [4;5;6]; [7;8;9]] // [1;2;3;4;5;6;7;8;9]
Ou vous pouvez utiliser des opérateurs binaires comme fonction de dossier:
List.fold (@) [] [[1;2;3]; [4;5;6]; [7;8;9]] // [1;2;3;4;5;6;7;8;9]
List.fold (+) 0 [1; 2; 3] // 6
List.fold (||) false [true; false] // true, more on this below
List.fold (&&) true [true; false] // false, more on this below
// etc...
Calcul de la factorielle d'un nombre
Même idée qu'en sommant les nombres, mais maintenant on les multiplie. si on veut la factorielle de n on multiplie tous les éléments de la liste [1 .. n] . Le code devient:
// the folder
let times x y = x * y
let factorial n = List.fold times 1 [1 .. n]
// Or maybe for big integers
let factorial n = List.fold times 1I [1I .. n]
La mise en œuvre forall , exists et contains
La fonction forall vérifie si tous les éléments d'une séquence satisfont à une condition. exists vérifie si au moins un élément de la liste satisfait à la condition. Nous devons d'abord savoir comment réduire une liste de valeurs bool . Eh bien, nous utilisons des plis de cours! Les opérateurs booléens seront nos fonctions de dossier.
Pour vérifier si tous les éléments d'une liste sont true nous les && avec la fonction && avec la valeur true comme valeur initiale.
List.fold (&&) true [true; true; true] // true
List.fold (&&) true [] // true, empty list -> return inital value
List.fold (&&) true [false; true] // false
De même, pour vérifier si un élément est true dans une liste booléenne, nous le réduisons avec le || opérateur avec false comme valeur initiale:
List.fold (||) false [true; false] // true
List.fold (||) false [false; false] // false, all are false, no element is true
List.fold (||) false [] // false, empty list -> return inital value
Retour à la forall et exists . Ici, nous prenons une liste de tout type, utilisons la condition pour transformer tous les éléments en valeurs booléennes et ensuite nous la réduisons:
let forall condition elements =
elements
|> List.map condition // condition : 'a -> bool
|> List.fold (&&) true
let exists condition elements =
elements
|> List.map condition
|> List.fold (||) false
Pour vérifier si tous les éléments dans [1; 2; 3; 4] sont plus petits que 5:
forall (fun n -> n < 5) [1 .. 4] // true
définir la méthode contains avec exists :
let contains x xs = exists (fun y -> y = x) xs
Ou même
let contains x xs = exists ((=) x) xs
Vérifiez maintenant si la liste [1 .. 5] contient la valeur 2:
contains 2 [1..5] // true
Mise en œuvre reverse :
let reverse xs = List.fold (fun acc x -> x :: acc) [] xs
reverse [1 .. 5] // [5; 4; 3; 2; 1]
Mise en œuvre de la map et du filter
let map f = List.fold (fun acc x -> List.append acc [f x]) List.empty
// map (fun x -> x * x) [1..5] -> [1; 4; 9; 16; 25]
let filter p = Seq.fold (fun acc x -> seq { yield! acc; if p(x) then yield x }) Seq.empty
// filter (fun x -> x % 2 = 0) [1..10] -> [2; 4; 6; 8; 10]
Y a-t-il quelque chose que le fold ne peut pas faire? Je ne sais pas vraiment
Calcul de la somme de tous les éléments d'une liste
Pour calculer la somme des termes (de type float, int ou big entier) d'une liste de nombres, il est préférable d'utiliser List.sum. Dans d'autres cas, List.fold est la fonction la mieux adaptée pour calculer une telle somme.
- Somme de nombres complexes
Dans cet exemple, nous déclarons une liste de nombres complexes et nous calculons la somme de tous les termes de la liste.
Au début du programme, ajoutez une référence à System.Numerics
ouvrir System.Numerics
Pour calculer la somme, nous initialisons l'accumulateur au nombre complexe 0.
let clist = [new Complex(1.0, 52.0); new Complex(2.0, -2.0); new Complex(0.0, 1.0)]
let sum = List.fold (+) (new Complex(0.0, 0.0)) clist
Résultat:
(3, 51)
- Somme des nombres de type union
Supposons qu'une liste soit composée de nombres de type union (float ou int) et que vous souhaitez calculer la somme de ces nombres.
Déclarez avant le type de numéro suivant:
type number =
| Float of float
| Int of int
Calculez la somme des nombres de type numéro d'une liste:
let list = [Float(1.3); Int(2); Float(10.2)]
let sum = List.fold (
fun acc elem ->
match elem with
| Float(elem) -> acc + elem
| Int(elem) -> acc + float(elem)
) 0.0 list
Résultat:
13.5
Le premier paramètre de la fonction, qui représente l'accumulateur, est de type float et le second paramètre, qui représente un élément de la liste, est de type numéro. Mais avant d'ajouter, nous devons utiliser une correspondance de modèle et la convertir en type float quand elem est de type Int.