On termine ce chapitre sur les listes en montrant comment utiliser la fonction bind, notée >>=, des listes, pour écrire simplement des algorithmes d'énumération, c'est-à-dire des algorithmes pour énumérer tous les éléments d'un ensemble.
Nous avons déjà vu que la fonction map applique une fonction à tous les éléments d'une liste. Composée avec concat, et si la fonction retourne des choix possibles associées à chaque élément, cela construit tous les choix pour tous les éléments de la liste.
Prenons un exemple. Construisons un algorithme qui choisit deux entiers, le premier entre 1 et 10 , le deuxième entre 1 et l'entier choisit en premier :
Pour toutes les valeurs de 1 à 10 , cela va appeler la fonction d'argument first_int. Pour chacun, pour toutes les valeurs de 1 à first_int, cela appelle ensuite la fonction d'argument second_int. Le résultat est donc bien la liste de toutes les paires que nous voulions. Notons que nous avions construit le produit cartésien de la même façon.
Nous pouvons faire des fonctions plus compliqués, selon le même principe. Par exemple, on peut énumérer toutes les permutations d'une liste :
Il suffit de choisir l'élément de tête, de le retirer de la liste, et de choisir une permutation des éléments restants. bind fait le travail de construire tous les choix possibles. Dans ce contexte, il faut lire une expression telle que list >>= fun elt ->comme " soit elt pris dans la liste list" .
Construisons maintenant toutes les sous-listes d'une liste : pour chaque élément, soit on le garde, soit on l'enlève. L'ordre des éléments gardés est conservé. Le principe est de procéder de droite à gauche (avec fold_right), à chaque élément, on choisit une des sous-listes du côté droit (dans subtails), ce qui permet de construire deux listes différentes selon qu'on prend ou laisse l'élément. Nous aurions aussi pu faire une fonction récursive, comme la précédente.
Comme dernier exemple, générons toutes les listes d'entiers positifs dont la somme vaut 5 :
De nouveau, on choisit la valeur du premier élément, on choisit le reste de la partition, et on en déduit une solution. Puisque >>= fait toutes les possibilités on obtient toutes les solutions possibles.
