list

Bien que la structure list soit immuable, son contenu est mutable.

Aussi appelée liste immuable, list est une structure de liste ordonnée, immuable et simplement chaînée de cellules d'indirection ref. Ainsi, bien que la structure d'une list soit immuable, les éléments qu'elle contient sont mutables.

Mis à part ce détail important, une list est similaires à un tuple. Elle en décline toutefois une variante au contenu mutable, mais dépourvu d'effet de bord.

Cette protection contre les effets de bord implique que toutes les opérations qui consistent à construire une nouvelle instance list nécessitent la duplication complète de la structure, y compris des références, de la ou des listes qui la constituent (La structure immuable list est représentées en bleu dans le schéma ci-contre).

De cette manière, le fait de modifier la valeur d'un élément d'un objet list ne présente absolument aucun risque d'effet bord sur d'autres lists ou variables qui auraient été utilisées pour construire cette liste immuable (nous parlons bien de l’immuabilité de la structure et non des valeurs qui forme son contenu).

Cependant, cela signifie également que la plupart des opérations sur les listes immuables nécessitent des temps de traitement à croissance linéaire qui dépendent du nombre d'éléments $O(n)$.

Pour créer une nouvelle liste immuable, il suffit d'utiliser le constructeur list. Cet opérateur peut être utilisé aussi bien comme constructeur que comme convertisseur.

(define 'v0 (list 3))      # Constructeur d'un vecteur à 3 éléments vides.
(display v0)
 
(define 'v1 (list[1 2 3])) # Ici, il s'agit d'un constructeur par conversion.
(display v1)               # Le contenu est initialisé à partir d'un tuple.

⇒

(list[(nothing) (nothing) (nothing)])
(list[1 2 3])

Le moyen le plus performant pour accéder au contenu d'une list consiste à utiliser un itérateur ou un énumérateur pour accéder successivement à chaque élément dans l'ordre du chaînage.

(define 'v (list 5))
 
(define 'i (iterator v))
(define '$c 0)
 
(while{i}
  {
    (set! (next i) $c) # Affecter l'élément de la liste
    (set! $c (+ $c 1)) # à l'aide d'un compteur...
  }
)
 
(display v)

⇒

(list[0 1 2 3 4])

Comme vous pouvez le constater, l'itérateur retourne la cellule d'indirection de l'élément en cours. On peut donc l'affecter sans problème.

Si la liste n'est pas trop longue, on peut aussi utiliser la position index des éléments pour accéder au contenu. Toutefois, pour atteindre l'élément n, une opération en $O(n-1)$ est nécessaire pour par parcourir la liste jusqu'à l'élément voulu.

(define 'v (list[1 2 3]))
(display (v 2))

⇒

3

Dans le cas où vous souhaitez atteindre le tout premier élément d'une liste immuable, il est recommandé d'utiliser car plutôt que la résolution indexée. car est une opération réalisée en temps constant $O(1)$.

(define 'v (list[1 2 3]))
(display (car v))

⇒

1

Il est très facile d'ajouter des éléments dans une liste immuable. Cependant, cette opération nécessite la création d'une nouvelle liste. Les structures de liste immuable ne peuvent pas être modifiées. On ne peut donc pas les agrandir sans en créer de nouvelles.

(define '$v (list[]))
(set! $v (+ $v 1 2 3))
(display $v)

⇒

(list[1 2 3])

Pour ajouter des éléments dans une liste immuable, le plus simple consiste à utiliser l'opérateur +. Comme cet opérateur est variadique, on peut indiquer autant d'éléments à ajouter que nécessaire. l'opérateur crée alors une seule nouvelle liste et y ajoute l'ensemble des éléments proposés en une seule opération. Cela est plus performant que l'ajout successif des éléments un par un.

L'opérateur concat permet de concaténer plusieurs structures list en une seule.

(define 'a (list[1 2 3]))
(define 'b (list[4 5 6]))
(define 'c (list[7 8 9]))
 
(define 'd (concat a b c))
(display d)

⇒

(list[1 2 3 4 5 6 7 8 9])

Pour une question de performance, il est plus avantageux de concaténer plusieurs listes immuables en une seule opération. Cela évide de devoir dupliquer plusieurs fois les structures des conteneurs.

Pour découper les listes immuables, il suffit d'utiliser les opérateurs cdr, tail, head ou slide.

• cdr : Retourne une nouvelle liste immuable composée des élément de la liste source à partir du deuxième élément jusqu'à la fin.
• tail : Permet de construire une nouvelle liste immuable à partir des n derniers éléments de la liste.
• head : Réalise une opération similaire mais en considérant les n premiers éléments.
• slice : Retourne une nouvelle liste contenant les n éléments à partir d'une position donnée p.

(define 'v (list[1 2 3 4 5 6 7 8 9]))
(display (cdr v))
(display (tail v 3))
(display (head v 3))
(display (slice v 5 2))

⇒

(list[2 3 4 5 6 7 8 9])
(list[7 8 9])
(list[1 2 3])
(list[6 7])

Comme toutes autres collections, il est possible d'obtenir la taille d'une liste immuable à l'aide de length. Une liste fournit aussi une valeur de vérité qui est (false) lorsqu'elle est vide.

• +
• array
• string