Nous apprenons maintenant à manipuler des listes d'éléments, en utilisant des fonctions haut-niveau, transformant des listes entières en d'autres listes par un simple appel de fonction.
Il y a essentiellement trois types de fonctions de transformation de listes :
Chacun de ces trois types correspond à une fonctionnelle.
Commençons par la suppression d'éléments. Si on souhaite supprimer un élément particulier, il n'y a pas d'opération prédéfinie pour cela. La raison est simplement que les listes ne sont pas conçues pour supporter efficacement cette opération, supprimer un élément arbitraire est une opération demandant potentiellement de parcourir toute la liste, et donc n'est pas encouragé.
Ce qui est plus typique des opérations de listes est de supprimer tous les éléments qui ne nous satisfont pas. En passant à la négation on ne veut garder que les éléments qui vérifient une propriété, donnée de nouveau par un prédicat. On veut donc filtrer les éléments pour garder ceux qui vérifie un critère. La fonction correspondante s'appelle filter
On veut parfois utiliser à la fois les éléments vérifiant le critère, et pour un autre but les éléments ne vérifiant pas le critère. On peut filtrer deux fois la même liste, comme dans l'exemple pour obtenir list1 et list2. Mais cela oblige à faire deux fois le travail, on peut donc utiliser la fonction partition pour cela :
Notez qu'on peut utiliser filter pour supprimer un élément d'une liste :
Cela supprime toutes les occurences de elt de la liste, pas uniquement la première. Et le caractère linéaire de l'algorithme est clair puisque filter teste tous les éléments.
La deuxième transformation consiste à modifier chaque élément, indépendamment. Chaque élément est remplacée par une valeur, cette valeur dépendant uniquement de l'élément remplacé. Il nous faut donc une fonction, qui nous dit à chaque élément par quoi le remplacer. Nous avons déjà vu cette fonction dans le cadre des conteneurs :
Notez que l'ordre des images est conservé par rapport à l'ordre des éléments. Puisque chaque élément est individuellement transformé en un autre. La liste obtenue a la même longueur que la liste initiale.
La définition de map peut être donnée par cette équation :
On peut reparenthéser le type de map ainsi :
On peut maintenant interpréter map comme une fonction qui transforme une fonction sur les éléments en une fonction sur les listes d'éléments, tout comme nous l'avons fait pour exists et for_all. En ce sens map est un combinateur qui transforme une fonction en une fonction plus puissante.
Il existe une variante de map, lorsqu'on souhaite que l'image d'un élément dépendent aussi de sa position dans la liste. La fonction à appliquer prend alors deux arguments : l'entier représentant la position de l'élément dans la liste, et l'élément lui-même.
Une application importante de cette fonction est d'indicer les éléments d'une liste, c'est-à-dire transformer chaque élément en une paire d'un élément et de son indice dans la liste.
Une autre application classique est de faire le produit cartésien de deux listes Core.Std.List.cartesian_product, c'est-à-dire obtenir l'ensemble des paires formées d'un élément d'une première liste et d'un élément d'une deuxième liste.
Ce code est assez peu compréhensible, et pas tout à fait correct puisqu'on obtient une liste de listes de paires, et non une liste de paires. Il faut comprendre que map fait un calcul pour tous les éléments d'une liste, c'est une sorte de boucle for. Le premier map ici fait varier elt1 sur la list1, le second fait varier elt2 sur list2, et on retourne toutes les paires (elt1,elt2).
On peut rendre le code plus lisible avec cette transformation raisonnable, consistant à nommer les fonctions anonymes.
ou bien on peut utiliser des astuces syntaxiques, compréhensibles uniquement par les experts (donc à prohiber, mais c'est rigolo néanmoins) :
Cette mauvaise solution suggère néanmoins l'existence d'une bonne solution. Il suffit d'introduire un opérateur binaire pour remplacer l'incompréhensible |> List.map @@. Cet opérateur est souvent noté >|=, mais dans Core.Std.List il est noté >>|, c'est simplement la notation infixe de map. Nous avons déjà vu map dans plusieurs contextes, et donc cet opérateur aussi est fréquent, et donc mérite d'être connu et utilisé. On obtient :
Il faut lire les lignes de droite à gauche : pour tout elt1 dans list1, pour tout elt2 dans list2, construire la paire (elt1, elt2).
Pour terminer le produit cartésien, il faudrait pouvoir agglutiner toutes les listes ensembles. Ceci nous amène aux fonctionnelles construisant des listes plus longues.
L'opération de base pour combiner des listes est de faire l'union des deux listes. Techniquement on appelle cette opération une concaténation, car
Les deux listes concaténées doivent avoir le même type. Il n'y a pas de piège par ailleurs, et la fonction s'appelle append. On peut aussi utiliser l'opérateur infixe @.
La complexité de append est linéaire dans la longueur du premier argument : les éléments de la première liste sont ajoutés un par un à la deuxième liste. Du coup, @ est associatif à droite, ce qui optimise la complexité :
Dans tous les cas, on évitera d'écrire :
Cette opération prend un temps linéaire dans la longueur de la liste. Lorsqu'on veut utiliser une séquence en ajoutant des éléments en fin de séquence, la structure de données adaptée n'est pas la liste, mais la file à double extrémité.
rev_append est une version légèrement plus efficace de la concaténation (la complexité asymptotique est la même), mais qui renverse l'ordre des éléments de la première liste. Il arrive souvent que l'ordre des éléments n'a pas d'importance, et il arrive aussi régulièrement que la première liste soit de toute façon à l'envers. rev est la fonction qui renverse l'ordre des éléments d'une liste, rev_append est donc une composition de rev et append.
Nous avons aussi :
append combine deux listes en une seule. Pour combiner une liste de listes en une seule, comme on en a besoin pour finir le produit cartésien, on utilise la concaténation généralisée, qui se nomme flatten ou concat dans la librairie standard, et concat dans Core. Une liste de listes peut être interprétée comme une liste de lignes, donc comme un tableau bi-dimensionnel. Transformer un tableau en liste, c'est mettre les lignes à la suite les unes des autres, de manière à former une seule longue ligne. Le nom flatten vient de là : on aplatit un tableau en un liste.
On termine le produit cartésien :
L'emplacement du concat n'est pas très intuitif. En fait la fonction serait plus lisible s'il n'était pas du tout présent. C'est en fait possible, mais il faut changer la fonction map = (>>|) par une fonction combinant map et concat. C'est la fonction bind, et l'opérateur infixe (>>=), qui le font. Malheureusement bind n'est pas (encore) dans la librairie standard, mais on le définit facilement.
Notons que la fonction donnée en deuxième argument de bind doit retourner une liste, ce qui explique que la dernière ligne de cartesian_product soit une liste singleton, et non pas une simple paire.
bind est donc la fonction annoncée en début de section, qui prenant une liste, construit une nouvelle liste en remplaçant chaque élément $e$, par une liste d'éléments en fonction de $e$. Il suffit donc de lui donner la liste, et la fonction calculant la liste d'images de chaque élément.
La fonction bind est tellement importante que nous ferons une section complète sur comment l'utiliser, puis nous ferons un cours complet sur cette fonction dans d'autres contextes que celui des listes.
Ces 6 fonctions ont donc des rôles bien déterminés, qui couvrent la plupart des transformations de liste à liste dont nous pouvons avoir besoin.
