Comment concaténer des listes dans erlang sans créer de listes imbriquées?

Question

J'essaie d'être un bon erlanger et d'éviter "++". J'ai besoin d'ajouter un tuple à la fin d'une liste sans créer une liste imbriquée (et j'espère sans avoir à le recréer et à l'inverser). Compte tenu de tuple T et listes L0 et L1:

Quand j'utilise [T | L0] Je reçois [tuple, sélection0].

Mais quand j'utilise [L0 | T], j'obtenir la liste imbriquée [[sélection0] | tuple]. De même, [L0 | L1] renvoie [[liste0] | liste1].

Suppression des parenthèses de liste externes L0 | [T] génère une erreur de syntaxe.

Pourquoi "|" pas symétrique? Y at-il un moyen de faire ce que je veux en utilisant "|"

Answer 1

| n'est pas "symétrique" car une liste non vide a une tête et une queue où la tête est un élément unique et la queue est une autre liste. Dans l'expression [foo | bar]foo désigne la tête de la liste et bar est la queue. Si la queue n'est pas une liste correcte, le résultat ne sera pas non plus une liste correcte. Si la tête est une liste, le résultat sera simplement une liste avec cette liste comme premier élément.

Il est impossible d'ajouter à la fin d'une liste chaînée en moins de O (n) heure. C'est pourquoi l'utilisation de ++ pour cela est généralement évitée. S'il y avait une syntaxe spéciale à ajouter à la fin de la liste, il faudrait quand même prendre le temps O (n) et l'utilisation de cette syntaxe ne ferait pas plus de "bon erlanger" que d'utiliser ++.

Si vous souhaitez éviter le coût O (n) par insertion, vous devez ajouter un préfixe, puis l'annuler. Si vous êtes prêt à payer le coût, vous pouvez tout aussi bien utiliser ++.

Un peu plus de détails sur la façon dont les listes de travail:

[ x | y ] est ce qu'on appelle une cellule contre. En termes de C, c'est essentiellement une structure avec deux membres. Une liste appropriée est soit la liste vide ([]) ou une cellule cons dont le second membre est une liste correcte (dans ce cas, le premier membre est appelé sa tête, et le second membre est appelé sa queue). Lorsque vous écrivez [1, 2, 3], cela crée les cellules suivantes: [1 | [2 | [3 | []]]]. C'est à dire. la liste est représentée comme une cellule contre dont le premier membre (sa tête) est 1 et le second membre (la queue) est une autre cellule. Cette autre contre-cellule a 2 comme tête et encore une autre contre-cellule comme sa queue. Cette cellule a 3 comme sa tête et la liste vide comme sa queue.

La traversée d'une telle liste se fait récursivement en agissant d'abord sur la tête de la liste puis en appelant la fonction de traversée sur la queue de la liste. Maintenant, si vous voulez ajouter un élément à cette liste, c'est très simple: vous créez simplement une autre cellule dont la tête est le nouvel élément et dont la queue est l'ancienne liste. L'ajout d'un élément est cependant beaucoup plus coûteux car la création d'une seule cellule n'est pas suffisante.Vous devez créer une liste qui est la même que l'ancienne, sauf que la queue de la dernière contre-cellule doit être une nouvelle contre-cellule dont la tête est le nouvel élément et dont la queue est la liste vide. Vous ne pouvez donc pas ajouter à une liste sans passer par toute la liste, qui est O (n).