Probleme – Les chaînes : ce que l'immuabilité coûte et rapporte

1. Une chaîne compte des octets, pas des lettres.

String.length "informatique" = 12
String.length "ete" (sans accent) = 3
String.length "ete" (avec deux accents aigus) = 5
le caractere d'indice 1 de ce dernier a pour code 169

Le mot accentué a trois lettres et cinq octets : chaque lettre accentuée en occupe deux en codage UTF-8. Et s.[1] ne rend pas une lettre, mais l'octet $169$, qui est la seconde moitié du codage de la première lettre — un caractère qui n'existe pas isolément.

La leçon est générale et vaut aussi pour C : le type char est un octet, et une chaîne est une suite d'octets. Tant que les données sont en ASCII, octets et caractères coïncident et rien ne se voit. Le premier accent sépare les deux notions. On ne parcourt donc pas une chaîne accentuée « caractère par caractère » sans savoir ce qu'on fait.

2. Compter les occurrences.

(* compte s c : nombre d'occurrences de l'octet c dans s.
   Precondition  : aucune.
   Postcondition : 0 <= resultat <= String.length s. *)
let compte s c =
  let n = String.length s in
  let k = ref 0 in
  (* INVARIANT : !k est le nombre d'occurrences de c parmi les i premiers
     octets de s.        VARIANT : n - i. *)
  for i = 0 to n - 1 do
    if s.[i] = c then incr k
  done;
  !k

Terminaison : une boucle for sur un intervalle fini ; le variant $n-i$ décroît de $1$ par tour. Correction : l'invariant vaut trivialement avant le premier tour ($k=0$, zéro octet examiné) ; le corps ajoute $1$ exactement quand le nouvel octet est le bon. À la sortie, $i=n$ : $k$ compte les occurrences dans toute la chaîne. Complexité : $\Theta (n)$ en temps, $\Theta (1)$ en espace. Le jeu de tests, partitionné : chaîne vide, aucune occurrence, une, toutes.

3. Le coût de la concaténation répétée.

let repete_concat n =
  let s = ref "" in
  for _ = 1 to n do s := !s ^ "a" done;
  !s

s1 ^ s2 alloue une chaîne neuve de longueur $|s_1|+|s_2|$ et y recopie les deux : c'est $\Theta (|s_1|+|s_2|)$. Le tour de rang $k$ recopie $k-1$ octets, d'où un total de ${\sum }_{k=1}^n(k-1)=n(n-1)/2=\Theta (n^2)$. La mesure :

n = 10 000  temps 0,026 s
n = 20 000  temps 0,085 s
n = 40 000  temps 0,329 s
n = 80 000  temps 1,268 s

Chaque doublement multiplie le temps par $3,3$ puis $3,9$ puis $3,9$ : quadratique, comme le @ de l'exercice 2.4 et pour exactement la même raison.

Et l'on ne peut pas contourner par une écriture en place : la chaîne est immuable, et le compilateur le dit sans détour.

let s = "abc" in s.[0] <- 'z'
Error: Syntax error: strings are immutable, there is no assignment syntax for
       them.
Hint: Mutable sequences of bytes are available in the Bytes module.

Le module Bytes n'est pas au programme ; ce que l'annexe autorise, c'est de travailler dans un char array, qui est mutable, et de ne produire la chaîne qu'à la fin. La règle pratique est la même que pour les listes : on n'ajoute pas dans une boucle à une structure immuable.

4. Ce que l'immuabilité rapporte. Elle supprime une catégorie entière de fautes. En C, passer un char<em> à une fonction, c'est lui donner le droit d'écrire dedans : qui veut se protéger doit soit écrire const, soit faire une copie défensive — le chapitre chap:langage-c en donne le prix. En OCaml, une chaîne peut être partagée par dix structures sans aucune copie, parce que personne ne peut la modifier. Le partage devient gratuit, et il n'y a aucun aliasing* à surveiller.

C'est le même marché que pour les listes : on paye une recopie à chaque construction, on encaisse un partage sans risque à chaque lecture. Le mauvais usage consiste à construire souvent ; le bon, à lire souvent.