L07 - Types énumérables et compréhensions

Ce texte présente les types énumérables (seq) et explique comment on peut écrire du code générique, qui soit indépendant de la structure de données. Ce cours détaille aussi les compréhensions, fonctionnalité permettant de manipuler élégamment des ensembles.

Un type énumérable (ou collection) est un type regroupant un ensemble de valeurs. Par exemple, la liste, le tableau ou la table de hachage sont des types énumérables. Il en existe beaucoup d'autres et l'on peut en créer soi-même. Pour chacun de ces types, on trouve des fonctions pour les manipuler dans la bibliothèque standard.

List

Dans le monde fonctionnel, la liste est l'un des types les plus utilisés (plus que les tableaux, par exemple). On a vu comment manipuler des listes et comment les parcourir dans la dernière leçon.

Je ne vais pas m'attarder dessus (les fonctions sont simples à utiliser). Les fonctions sont décrites dans le manuel, section listes

Comme vous pouvez le voir, la plupart des fonctions sont d'ordre supérieur. Par exemple, pour savoir si une liste d'entiers contient (au moins) une valeur négative, on écrira :

[fsharp]
List.exists (fun x -> x < 0) mylist

Parmi les fonctions indispensables à connaitre, il y map qui transforme une liste (en utilisant la fonction donnée) :

[fsharp]
> [1..10] |> List.map (fun x -> x * x);;
val it : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]

Et la fonction filter qui ne garde que les éléments correspondant au prédicat (une fonction qui renvoie un booléen). Voici un exemple qui ne fait rien d'utile, mais qui montre bien le fonctionnement et comment on peut cumuler les fonctions :

[fsharp]
> [1..10] |> List.map (fun x -> x + x + 1)
          |> List.filter (fun x -> x % 3 = 0)
          |> List.map (fun x -> x, x / 2)
          |> List.rev;;
val it : (int * int) list = [(21, 10); (15, 7); (9, 4); (3, 1)]

Il existe aussi la fonction iter, qui permet d'appeler une fonction sur chacun des éléments de la liste. Elle ne construit pas de nouvelle liste, contrairement à map.

Seq

Tous les types énumerables sont regroupés sous l'interface IEnumerable (appelée aussi « seq »). La bibliothèque standard fournit un certain nombre d'opérations pour ces types énumérables. Le manuel liste les fonctions disponibles.

[fsharp]
> let print_seq s = Seq.iter (printfn "- %A") s;;
val print_seq : #seq<'a> -> unit

Le #seq<'a> signifie : tout type compatible avec seq, et paramétré par a. Unit correspond, en gros, au type void de certains langages. C'est un type particulier, qui n'admet qu'un seule valeur, notée ().

[fsharp]
> print_seq [1..3];;
- 1
- 2
- 3

Voici quelques autres types énumérables : string, Array2 (tableau à 2 dimensions), Array3 (devinez !), Set (ensemble sans doublon), LazyList (liste paresseuse), Map (ensemble associatif).

Le plus simple pour initialiser ces types est souvent de passer par une liste. Ces types possèdent généralement une fonction of_seq pour faire la conversion. Par exemple :

[fsharp]
> print_seq "foo";;
- 'f'
- 'o'
- 'o'

> let s = [4; 1; 2; 4; 2] |> Set.of_seq;;
val s : Set<int>

> print_seq s;;
- 1
- 2
- 4

La fonction fold, populaire dans le monde fonctionnel, permet d'appliquer une fonction sur chaque élément de la collection, en utilisant un accumulateur tout au long du calcul. Ce qui correspond au calcul : f(..(f (f s i0) i1)..) iN

Puisque ce n'est pas toujours simple à comprendre, pour faire la somme des éléments d'une collection, il suffit d'appeler fold en lui donnant l'opérateur + :

[fsharp]
> let sum l = Seq.fold (+) 0 l;;
val sum : #seq<int> -> int

> sum [|1 .. 10|];;
val it : int = 55

En pratique, on peut appeler directement Seq.sum. La fonction reduce est une version de fold qui utilise le premier élément comme accumulateur. Pour récupérer l'élément maximum (Seq.max dans la bibliothèque) :

[fsharp]
> let smax s = Seq.reduce max s;;
val smax : #seq<'a> -> 'a

> smax [|4; 1; 10; 7; 3|];;
val it : int = 10

> smax "hello";;
val it : char = 'o'

Encore un autre exemple, la fonction mapi ressemble à la fonction map. Elle est paramétrée par une fonction à deux éléments : l'élément courant et son indice.

[fsharp]
> let enumerate x = Seq.mapi (fun n e -> n, e) x;;
val enumerate : #seq<'b> -> seq<int * 'b>

> enumerate "foobar";;
val it : seq<int * char> = seq [(0, 'f'); (1, 'o'); (2, 'o'); (3, 'b'); ...]

Compréhensions

Les compréhensions permettent de manipuler, de manière élégante, les types énumérés. Pour chaque élément x de l'ensemble 1..10, renvoyer x au carré :

[fsharp]
> [for x in 1..10 -> x * x];;
val it : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]

Les crochets indiquent que l'on souhaite récupérer une liste. On aurait pu mettre [| .. |] pour avoir un tableau ou seq { .. } pour avoir un type énumérable paresseux. Dans les exemples plus complexes, on utilise le mot-clé yield pour renvoyer une valeur, au lieu de la flèche :

[fsharp]
> [ for i in 1..10 do if i % 2 = 1 then yield i ];;
val it : int list = [1; 3; 5; 7; 9]

> [|for c in "F# Rocks" do if c < 'o' then yield c|];;
val it : char array = [|'F'; '#'; ' '; 'R'; 'c'; 'k'|]

L'ensemble des carrés, pour tous les entiers entre 1 et 100 milliards (grâce aux accolades, cet ensemble est un générateur : les valeurs ne seront calculées que s'il y en a besoin) :

[fsharp]
> let nat = seq {for i in 1I .. 100000000000I -> i * i};;
val nat : seq<Math.BigInt>

Cet ensemble peut lui aussi être manipulé :

[fsharp]
> nat |> Seq.map (fun x -> x + 5I);;
val it : seq<Math.BigInt> = seq [6I; 9I; 14I; 21I; ...]

Le I après une constante indique que l'on souhaite une valeur de type Math.BigInt (entiers en précision arbitraire).

Une liste de listes :

[fsharp]
> [for i in 1..5 -> [1..i]];;
val it : int list list = [[1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]; [1; 2; 3; 4; 5]]

Si l'on utilise yield!, on ajoute les éléments de l'ensemble, plutôt que l'ensemble lui-même. On obtient alors une simple liste :

[fsharp]
> [for i in 1..5 do yield! [1..i]];;
val it : int list = [1; 1; 2; 1; 2; 3; 1; 2; 3; 4; 1; 2; 3; 4; 5]

Le i après le for n'est pas un simple identifiant, c'est un motif. On peut donc faire du pattern matching. On peut récupérer un couple :

[fsharp]
> [for i, c in enumerate ['a'..'z'] do if i % 3 = 0 then yield c];;
val it : char list = ['a'; 'd'; 'g'; 'j'; 'm'; 'p'; 's'; 'v'; 'y']

Il est aussi possible de combiner les compréhensions :

[fsharp]
> [for i in 1..3 do
   for j in 1..3 do yield i, j];;
val it : (int * int) list
= [(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3)]

Exemple pour afficher les éléments de l'ensemble associatif dont la clé est impaire :

[fsharp]
> let h = Map.of_seq [11, "foo"; 14, "bar"; 5, "f#"];;
val h : Map<int,string>

> [for i in h do if i.Key % 2 = 1 then yield i.Value];;
val it : string list = ["f#"; "foo"]

Exemples pour finir :

[fsharp]
> let data = [for i in 0..8 -> [1 .. i]];;
val data : int list list

// liste infinie
> seq { while true do yield! [1; 2] };;
val it : seq<int> = seq [1; 2; 1; 2; ...]

Comments

1. On Friday, March 6 2009, 21:42 by Stéphane

Certains exemples de ce cours semblent obsolètes.
Par exemple,
[for i in 1..100 when i%2=1->i];; ne marche pas. Avec l'aide du compilateur, on tombe sur
[for i in 1..100 do if (i%2=1) then yield i];;
De même [|for c in "F# Rocks" when c < 'o' -> c|];; peut être remplacé par [|for c in "F# Rocks" do if c < 'o' then yield c|];;

L'expression
let nat = {for i in 1N .. 100000000000N -> i * i};;
a besoin du mot-clé "seq"; mais là encore le comilateur nous l'indique gentiment...

Et tant que j'y suis,
[for i in 1..5 ->> [1..i]];; semble là aussi obsolète et peut être remplacée par
[for i in 1..5 do yield! [1..i]];;
en revanche,
[for i in 1..5 -> [1..i]];; continue de fonctionner tout en semblant être équivalente à
[for i in 1..5 do yield [1..i]];;

2. On Friday, March 13 2009, 00:52 by Laurent

Merci beaucoup ! Cela sera très utile aux lecteurs.
Et bien sûr, ça m'aidera le jour où je mettrai à jour tous ces articles (je manque de temps en ce moment).

3. On Tuesday, September 1 2009, 22:57 by Laurent

Voilà, j'ai eu le temps !

Je viens de reprendre les exemples et les explications, merci pour le commentaire. En effet, la flèche est équivalente à "do yield", mais elle n'est autorisée que pour le cas le plus simple du for.