Ce que coûte un @

let rec infixe = function
  | Vide -> [] | Noeud (g,e,d) -> infixe g @ (e :: infixe d)

let rec infixe_acc a acc = match a with
  | Vide -> acc | Noeud (g,e,d) -> infixe_acc g (e :: infixe_acc d acc)

Les mesures, sur un peigne gauche — l'arbre où chaque nœud n'a qu'un fils gauche :

La première ligne quadruple à chaque doublement — $0,225\to 1,001\to 4,864\to 26,393$, soit des rapports $4,4$ ; $4,9$ ; $5,4$. C'est la signature du quadratique, et l'écart au facteur $4$ exact vient du ramasse-miettes, qui a de plus en plus de listes intermédiaires à récupérer. La seconde ligne reste sous la milliseconde : elle est linéaire.

L'explication. u @ v recopie intégralement u : c'est en $\Theta (|u|)$, et non en $O(1)$. Sur un peigne gauche, la première version calcule

$$T(n)=T(n-1)+\underset{\text{la recopie de }\text{infixe g}}{\underbrace{(n-1)}}+O(1),$$

d'où $T(n)=\Theta (n^2)$. À $n=40000$, ce sont $8\times 10^8$ recopies de maillons.

La seconde version ne fait jamais de concaténation : elle construit la liste de droite à gauche, par ajouts en tête. Chaque nœud coûte un ::, en $O(1)$, donc $\Theta (n)$ au total.

L'invariant qui fait comprendre la seconde écriture, et qui est la vraie difficulté :

(* Renvoie (parcours infixe de a) suivi de acc, sans jamais concatener. *)

La fonction ne calcule pas le parcours : elle calcule le parcours préfixé à une liste déjà construite. C'est ce paramètre supplémentaire qui remplace la concaténation — l'accumulateur est le « reste à écrire ». On retrouve la même idée que dans miroir_acc au chapitre chap:induction, et elle marchera à l'identique sur tous les parcours.

Deux avertissements pour finir.

Un. Sur un arbre équilibré, la version avec @ coûte $\Theta (n\log n)$ et non $\Theta (n^2)$ : chaque niveau recopie $O(n)$ maillons, et il y a $\log n$ niveaux. Le défaut ne se voit donc pas sur des données bien formées — il n'apparaît que sur le cas dégénéré, c'est-à-dire exactement quand tout va déjà mal.

Deux. L'ordre des arguments de l'accumulateur est contre-intuitif : infixe_acc g (e :: infixe_acc d acc) traite le sous-arbre droit en premier, alors que le parcours infixe le visite en dernier. C'est logique une fois qu'on l'a vu — on construit la liste par la fin — et c'est la faute classique de cette écriture.