OCaml
Traitement de liste

Liste.Carte

List.map a la signature ('a -> 'b) -> 'a list -> 'b list qui en anglais est une fonction qui prend une fonction (nous l'appelons la fonction de mappage) d'un type (à savoir 'a ) à un autre type (à savoir 'b ) et une liste du premier type. La fonction renvoie une liste du second type où chaque élément est le résultat de l'appel de la fonction de mappage sur un élément de la première liste.

List.map string_of_int [ 1; 2; 3; 4 ]
#- [ "1"; "2"; "3"; "4" ] : string list

Les types 'a et 'b ne doivent pas nécessairement être différents. Par exemple, nous pouvons mapper des numéros sur leurs carrés tout aussi facilement.

let square x = x * x in
List.map square [ 1; 2; 3; 4 ]
#- [ 1; 4; 9; 16 ] : int list

Agréger les données dans une liste

Les fonctions List.fold_left et List.fold_right sont des fonctions d' ordre supérieur qui implémentent la logique externe de l'agrégation de listes. L'agrégation d'une liste, parfois également appelée réduction d'une liste, signifie le calcul d'une valeur dérivée de l'inspection séquentielle de tous les éléments de cette liste.

La documentation du module List indique que

• List.fold_left fa [b1; ...; bn] est f (... (f (fa b1) b2) ...) bn .
• List.fold_right f [a1; ...; an] b est f a1 (f a2 (... (f an b) ...)) . (Cette dernière fonction n'est pas récursive.)

En anglais simple informatique List.fold_left fa [b1; ...; bn] revient à parcourir la liste [b1; ...; bn] gardant la trace d'un accumulateur initialement défini sur a : chaque fois que nous voyons un élément dans la liste, nous utilisons f pour mettre à jour la valeur de l'accumulateur, et lorsque nous avons terminé, l'accumulateur est la valeur finale de notre calcul. La fonction List.fold_right est similaire.

Voici quelques exemples pratiques:

Calculer la somme totale d'une liste de nombres

List.fold_left ( + ) 0 lst

Calculer la moyenne d'une liste de flotteurs

let average lst =
  let (sum, n) =
    List.fold_left (fun (sum, n) x -> (sum +. x, n + 1)) (0.0, 0) lst
  in
  sum /. (float_of_int n)

Ré-implémenter le traitement de base des listes

Les fonctions List.fold_left et List.fold_right sont si générales qu'elles peuvent être utilisées pour implémenter presque toutes les autres fonctions du module liste:

let list_length lst = (* Alternative implementation to List.length *)
  List.fold_left ( + ) 0 lst

let list_filter predicate lst = (* Alternative implementation to List.filter *)
  List.fold_right (fun a b -> if predicate a then a :: b else b) lst []

Il est même possible de réimplémenter la fonction List.iter , rappelez-vous que () est l'état global du programme pour interpréter ce code comme un exemple supplémentaire d' agrégation de liste :

let list_iter f lst = (* Alternation implementation to List.iter *)
  List.fold_left (fun () b -> f b) () lst

Ces exemples sont destinés à être un matériel d'apprentissage, ces implémentations n'ont aucune vertu sur les fonctions correspondantes de la bibliothèque standard.