Lazi

Liste indexée par les entiers naturels

Contexte

On peut voir la liste actuelle comme indexée par les entiers naturels mais codés par une liste où le cardinal de 0b donne l'entier naturel.

Question

Est-ce qu'il y aurait une structure de liste plus efficace que celle linéraire actuelle et étant basée sur une indexation d'entiers naturels ?

Étude

Bits de poid faible en premier

Le format :

À chaque étape il y a 3 valeurs :
- si la liste se termine, le contenu
- si la liste continue par un 0b
- si la liste continue par un 1b

$T[ contenu, $T[ liste 0b, liste 1b ] ]

Si les bits de poids faibles sont en premier alors pour parcourir linéairement la liste il faudrait sans cesse passer d'un côté à l'autre et donc ce serait très lourd.

Bits de poid fort en premier

Le problème est que deux nombres commencent pareils, comme "11111" et "1111", donc à moins de compléter les bits de poid fort par des zéro on ne peut pas avoir une liste pratique. Si on complète par des zéros alors il faut une étape supplémentaire.
Supposons que l'on complète par des 0 :
La liste est alors un arbre binaire où les feuilles sont le contenu.
L'élément de tête est numéroté 0.
Passer à la profondeur supplémentaire :

facile.
Ajouter un élément en queue :
Il faut stocker un nombre binaire pour savoir combien il y a d'éléments et savoir où ajouter le suivant. Si on doit passer à la profondeur suivante ce n'est pas très gros. Mais à chaque ajout d'élément il faut incrémenter le compteur donc c'est bien plus lourd que la liste classique.
Ajouter un élément en tête :
Il faut tout reconstruire.
Ajouter deux listes :
Il faut ajouter un à un les éléments de la liste en deuxièmes à celle en premier.
Fold :
La profondeur de la récursivité est la profondeur de l'arbre et non la longueur de la liste. Il est bien plus rapide d'accéder au début.
Contrôler que l'on est à la fin :
Il faut tenir le compte de l'endroit où l'on est (pas besoin de calculer) et vérifier si on est au dernier élément. Pour la moitier des cas on est dans un arbre plein et il n'y a pas d'autre vérif à faire que savoir si on est à la profondeur max. Dans le cas d'un arbre plein il y a un test par nœud ou feuille, donc deux fois plus qu'une liste simple.
Liste infinie :
Impossible.
Taille des données :
La liste simple a deux paires par nœud
La liste étudiée ici a une paire par nœud

Réponse

La liste où la base de l'arbre correspond au bit de poid fort est exponentiellement plus efficace, donc cela vaudrait le cout je pense à partir d'environ 100 éléments.
En conclusion ça serait plutôt à implémenter par un compilateur que directement en lazi où là je pense que ça ne gagnerait rien sauf pour les parcours partiels par le début.