Fonctions génériques

Accès à un élément

↓ Accès \ Renvoie →	'T ou 💥	'T option
Par index	list.[index]
	item index	tryItem index
Premier élément	head	tryHead
Dernier élément	last	tryLast

→ Fonctions à préfixer par le module associé : Array, List ou Seq → Dernier paramètre, la "collection", omis par concision → 💥 : ArgumentException ou IndexOutOfRangeException

[1; 2] |> List.tryHead    // Some 1
[1; 2] |> List.tryItem 2  // None

Coût ⚠️

Fonction \ Module	Array	List	Seq
head	O(1)	O(1)	O(1)
item	O(1)	O(n) ❗	O(n) ❗
last	O(1)	O(n) ❗	O(n) ❗
length	O(1)	O(n) ❗	O(n) ❗

Combiner des collections

Fonction	Paramètre(s)	Taille finale
append / @	2 collections de tailles N1 et N2	N1 + N2
concat	P collections de tailles N1..Np	N1 + N2 + ... + Np
zip	2 collections de même taille N ❗	N tuples
allPairs	2 collections de taille N1 et N2	N1 * N2 tuples

💡 @ = opérateur infixe alias de List.append uniquement (Array, Seq)

List.append [1;2;3] [4;5;6]    // [1; 2; 3; 4; 5; 6]
[1;2;3] @ [4;5;6]              // idem

List.concat [ [1]; [2; 3] ]    // [1; 2; 3]

List.zip [1; 2] ['a'; 'b']     // [(1, 'a'); (2, 'b')]

List.allPairs [1; 2] ['a'; 'b'] // [(1, 'a'); (1, 'b'); (2, 'a'); (2, 'b')]

Cons :: vs Append @

Cons 1 :: [2; 3]

• Élément ajouté en tête de liste

• Liste paraît en ordre inverse 😕

• Mais opération en O(1) 👍 -- (Tail conservée)

Append [1] @ [2; 3]

• Liste en ordre normal

• Mais opération en O(n) ❗ -- (Nouvelle Tail à chaque niveau)

Recherche d'un élément

Via un prédicat f : 'T -> bool :

Quel élément \ Renvoie	'T ou 💥	'T option
Premier trouvé	find	tryFind
Dernier trouvé	findBack	tryFindBack
Index du 1er trouvé	findIndex	tryFindIndex
Index du der trouvé	findIndexBack	tryFindIndexBack

[1; 2] |> List.find (fun x -> x < 2)      // 1
[1; 2] |> List.tryFind (fun x -> x >= 2)  // Some 2
[1; 2] |> List.tryFind (fun x -> x > 2)   // None

Recherche de N éléments

Recherche	Combien d'éléments	Méthode
Par valeur	Au moins un	contains value
Par prédicat f	Au moins un	exists f
"	Tous	forall f

[1; 2] |> List.contains 0      // false
[1; 2] |> List.contains 1      // true
[1; 2] |> List.exists (fun x -> x >= 2)  // true
[1; 2] |> List.forall (fun x -> x >= 2)  // false

Sélection d'éléments

Quels éléments	Par nombre	Par prédicat f
Tous ceux trouvés		filter f
Premiers ignorés	skip n	skipWhile f
Premiers trouvés	take n	takeWhile f
	truncate n

☝ Notes :

• Avec skip et take, 💥 exception si n > list.Length ; pas avec truncate

• Alternative pour Array : sélection par Range arr.[2..5]

Mapping d'éléments

Fonction prenant en entrée :

• Une fonction de mapping f

• Une collection d'éléments de type 'T

Fonction	Mapping f	Retour	Quel(s) élément(s)
map	'T -> 'U	'U list	Autant d'éléments
mapi	int -> 'T -> 'U	'U list	idem
collect	'T -> 'U list	'U list	flatMap
choose	'T -> 'U option	'U list	Moins d'éléments
pick	'T -> 'U option	'U	1er élément ou 💥
tryPick	'T -> 'U option	'U option	1er élément

map vs mapi

mapi ≡ map with index

map : mapping 'T -> 'U → Opère sur valeur de chaque élément

mapi : mapping int -> 'T -> 'U → Opère sur index et valeur de chaque élément

["A"; "B"]
|> List.mapi (fun i x -> $"{i+1}. {x}")
// ["1. A"; "2. B"]

Alternative à mapi

Hormis map et iter, aucune fonction xxx n'a de variante en xxxi.

💡 Utiliser indexed pour obtenir les éléments avec leur index

let isOk (i, x) = i >= 1 && x <= "C"

["A"; "B"; "C"; "D"]
|> List.indexed       // [ (0, "A"); (1, "B"); (2, "C"); (3, "D") ]
|> List.filter isOk   //           [ (1, "B"); (2, "C") ]
|> List.map snd       //               [ "B" ; "C" ]

map vs iter

Fonction	Lambda en paramètre	Type de retour
map	'T -> 'U	'U list
iter	'T -> unit (= Action en C#)	unit list unit

On pourrait considérer iter comme inutile, map pouvant prendre une lambda 'T -> unit en paramètre, mais c'est se tromper.

• Le type de retour n'est pas le même : iter renvoie unit, alors que map renverrait alors unit list. Par contre, le compilateur n'oblige pas à ignorer cette valeur (cf. Fonction ignore), ce qui aiderait à détecter l'usage erroné de map au lieu de iter !?
• Avec une Seq, map ne consomme pas la séquence et donc ne déclenche pas immédiatement les actions pour chaque élément de la séquence !

👉 Conclusion : iter correspond à un cas d'utilisation différent de map. (Idem respectivement pour iteri et mapi)

// ❌ À éviter
["A"; "B"; "C"] |> List.mapi (fun i x -> printfn $"Item #{i}: {x}")
(*
    Item #0: A
    Item #1: B
    Item #2: C
    val it: unit list = [(); (); ()]
*)

// ✅ Recommandé
["A"; "B"; "C"] |> List.iteri (fun i x -> printfn $"Item #{i}: {x}")
(*
    Item #0: A
    Item #1: B
    Item #2: C
    val it: unit = ()
*)

choose, pick, tryPick

Mapping f: 'T -> 'U option → Opération partielle : peut échouer à produire une valeur → D'où le type Option en sortie → Exemple : tryParseInt: string -> int option (cf. exemple ci-dessous)

Les fonctions choose, pick, tryPick gèrent les Options produites par le mapping des éléments de la collection, de manière à obtenir en sortie :

• choose : 'U collection → toutes les valeurs que le mapping a réussi à produire

• pick : 'U → la 1ère valeur que le mapping a réussi à produire → ou 💥 si aucune valeur n'a été produite

• tryPick : 'U option → la même 1ère valeur wrappée dans Some → ou None si aucune valeur n'a été produite

Exemples :

let tryParseInt (s: string) =
    match System.Int32.TryParse(s) with
    | true,  i -> Some i
    | false, _ -> None

["1"; "2"; "?"] |> List.choose tryParseInt   // [1; 2]
["1"; "2"; "?"] |> List.pick tryParseInt     // 1
["1"; "2"; "?"] |> List.tryPick tryParseInt  // Some 1

choose est équivalente conceptuellement à 3 opérations en 1 : 1. map f qui renvoie une collection de 'U option 2. filter (Option.isSome) pour ne garder que les options contenant une valeur 3. map (Option.get) pour extraire ces valeurs

De même, pick et tryPick sont conceptuellement équivalentes à : → pick ≅ choose f >> head → tryPick ≅ choose f >> tryHead

Sélection vs mapping

• filter ou choose ?

• find/tryFind ou pick/tryPick ?

filter, find/tryFind opèrent avec un prédicat 'T -> bool, sans mapping

choose, pick/tryPick opèrent avec un mapping 'T -> 'U option

• filter ou find/tryFind ?

• choose ou pick/tryPick ?

filter, choose renvoient tous les éléments trouvés/mappés

find, pick ne renvoient que le 1er élément trouvé/mappé

Agrégation

Fonctions spécialisées

Opération	Sur élément	Sur projection 'T -> 'U
Maximum	max	maxBy projection
Minimum	min	minBy projection
Somme	sum	sumBy projection
Moyenne	average	averageBy projection
Décompte	length	countBy projection

[1; 2; 3] |> List.max  // 3
[ (1,"a"); (2,"b"); (3,"c") ] |> List.sumBy fst  // 6
[ (1,"a"); (2,"b"); (3,"c") ] |> List.map fst |> List.sum  // Equivalent explicite

Membre Zero

Les fonctions sum ne marchent que si le type des éléments dans la collection comporte un membre statique Zero et une surcharge de l'opérateur + :

type Point = Point of X:int * Y:int with
    static member Zero = Point (0, 0)
    static member (+) (Point (ax, ay), Point (bx, by)) = Point (ax + bx, ay + by)

let addition = (Point (1, 1)) + (Point (2, 2))
// val addition : Point = Point (3, 3)

let sum = [1..3] |> List.sumBy (fun i -> Point (i, -i))
// val sum : Point = Point (6, -6)

💡 On peut utiliser LanguagePrimitives.GenericZero pour récupérer le Zero d'un type :

let zeroP: Point   = LanguagePrimitives.GenericZero // Point (0, 0)
let zeroI: int     = LanguagePrimitives.GenericZero // 0
let zeroF: float   = LanguagePrimitives.GenericZero // 0.0
let zeroM: decimal = LanguagePrimitives.GenericZero // 0M
let zeroS: string  = LanguagePrimitives.GenericZero // 💥 
// Le type 'string' ne prend pas en charge l'opérateur 'get_Zero' 

Fonctions génériques

• fold (f: 'U -> 'T -> 'U) (seed: 'U) list

• foldBack (f: 'T -> 'U -> 'U) list (seed: 'U)

• reduce (f: 'T -> 'T -> 'T) list

• reduceBack (f: 'T -> 'T -> 'T) list

☝ f prend 2 paramètres : un "accumulateur" acc et l'élément courant x

⚠️ Fonctions xxxBack : tout est inversé / fonctions xxx ! → Parcours des éléments en sens inverse : dernier → 1er élément → Paramètres seed et list inversés (pour foldBack vs fold) → Paramètres acc et x de f inversés

💥 reduceXxx plante si liste vide car 1er élément utilisé en tant que seed

Exemples :

["a";"b";"c"] |> List.reduce (+)  // "abc"
[ 1; 2; 3 ] |> List.reduce ( * )  // 6

[1;2;3;4] |> List.reduce     (fun acc x -> 10 * acc + x)  // 1234
[1;2;3;4] |> List.reduceBack (fun x acc -> 10 * acc + x)  // 4321

("", [1;2;3;4]) ||> List.fold     (fun acc x -> $"{acc}{x}")  // "1234"
([1;2;3;4], "") ||> List.foldBack (fun x acc -> $"{acc}{x}")  // "4321"

Changer l'ordre des éléments

Opération	Sur élément	Sur projection 'T ->
Inversion	rev list
Tri ascendant	sort list	sortBy f list
Tri descendant	sortDescending list	sortDescendingBy f list
Tri personnalisé	sortWith comparer list

[1..5] |> List.rev // [5; 4; 3; 2; 1]
[2; 4; 1; 3; 5] |> List.sort // [1..5]
["b1"; "c3"; "a2"] |> List.sortBy (fun x -> x.[0]) // ["a2"; "b1"; "c3"] cf. a < b < c
["b1"; "c3"; "a2"] |> List.sortBy (fun x -> x.[1]) // ["b1"; "a2"; "c3"] cf. 1 < 2 < 3

Séparer

💡 Les éléments sont répartis en groupes.

Exemples en partant de [1..10]

Opération	Résultat (; omis)
Valeur initiale	[ 1 2 3 4 5 6 7 8 9 10 ]
chunkBySize 3	[[1 2 3] [4 5 6] [7 8 9] [10]]
splitInto 3	[[1 2 3 4] [5 6 7] [8 9 10]]
splitAt 3	([1 2 3],[4 5 6 7 8 9 10]) Tuple ❗

Grouper les éléments

Par taille

💡 Les éléments peuvent être dupliqués dans différents groupes.

Opération	Résultat (' et ; omis)
Valeur initiale	[ 1 2 3 4 5 ]
pairwise	[(1,2) (2,3) (3,4) (4,5) ] Tuples ❗
windowed 2	[[1 2] [2 3] [3 4] [4 5] ] Listes de 2
windowed 3	[[1 2 3] [2 3 4] [3 4 5] ] Listes de 3

Par critère

Opération	Critère	Retour
partition	predicate: 'T -> bool	('T list * 'T list)
		→ 1 tuple ([OKs], [KOs])
groupBy	projection: 'T -> 'K	('K * 'T list) list
		→ N tuples [(clé, [éléments associés])]

let isOdd i = (i % 2 = 1)
[1..10] |> List.partition isOdd // (        [1; 3; 5; 7; 9] ,         [2; 4; 6; 8; 10]  )
[1..10] |> List.groupBy isOdd   // [ (true, [1; 3; 5; 7; 9]); (false, [2; 4; 6; 8; 10]) ]

let firstLetter (s: string) = s.[0]
["apple"; "alice"; "bob"; "carrot"] |> List.groupBy firstLetter
// [('a', ["apple"; "alice"]); ('b', ["bob"]); ('c', ["carrot"])]

Changer de type de collection

Au choix : Dest.ofSource ou Source.toDest

De / vers	Array	List	Seq
Array	×	List.ofArray	Seq.ofArray
	×	Array.toList	Array.toSeq
List	Array.ofList	×	Seq.ofList
	List.toArray	×	List.toSeq
Seq	Array.ofSeq	List.ofSeq	×
	Seq.toArray	Seq.toList	×

Fonction vs compréhension

Les fonctions de List/Array/Seq peuvent souvent être remplacées par une compréhension c'est-à-dire une expression de construction d'une liste [...], d'un tableau [|...|] ou d'une séquence seq {...} respectivement. C'est une option à envisager pour améliorer la lisibilité.

Exemples pour les listes :

let list = [ 0..99 ]

list |> List.map f                   <->  [ for x in list do f x ]
list |> List.filter p                <->  [ for x in list do if p x then x ]
list |> List.filter p |> List.map f  <->  [ for x in list do if p x then f x ]
list |> List.collect g               <->  [ for x in list do yield! g x ]

Ressources complémentaires

Documentation de FSharp.Core 👍

• Array module
• List module
• Map module
• Seq module
• Set module