Études-Mathématique/Listes de base

From Lazi wiki
Jump to: navigation, search

Question

Le format unique actuel de liste pose problème comme il est utilisé:

  • Pas optimisé pour les listes infinies où l'on ne doit jamais commencer par la tête.
  • Utilisé en tant qu'ensemble (où là l'ordre n'a pas d'importance) ce qui pose un problème d'optimisation car pour une liste on commence souvent par la tête ce qui est plus lourd (par exemple pour chercher un élément).

Est-ce possible de réorganiser les listes pour ne pas avoir les problèmes ci-dessus ?

Étude

Fonctionnalités minimales d'une liste

Au minimum une liste doit permettre :

  • D'ajouter un élément à la fin.
  • De récupérer le premier élément et le reste de la liste.
  • De détecter si la liste est vide.

Les listes et Lazi

On ne peut pas définir une liste Lazi où les temps d'exécution soit en o(1). Donc la liste n'est pas une structure de base. Comme il existe de nombreuses fonctions sur les listes, il est bon de structurer toutes ces fonctions et donc si possible de les factoriser. Cela est utile pour simplifier le code mais aussi plus tard pour prouver des propriétés.

Fonctions de base

Récursion sur une chose

recThing continue de calculer (par la fonction "cont") tant que result retourne nothing. x est la valeur à calculer.

$Def recThing = $F result,cont,x = maybeOr ( result x , cont (recThing stop cont) x )

Liste ordonnée

Une liste est forcément finie puisqu'elle a par définition deux bouts. L'ordre d'ajout normal est à la queue, l'ordre de lecture normale est en partant de la tête. Mais on peut avoir des fonctions qui utilisent l'ordre inverse. C'est soit la fonction d'ajout soit la fonction de lecture qui est o(1). Comme les listes ordonnées peuvent être utilisées parfois sans ordre (par exemple pour chercher un élément), il est plus optimisé que ce soit la fonction d'ajout qui soit o(1).

Liste non ordonnée

Une liste non ordonnée est différente d'un ensemble car un ensemble est muni d'une relation d'égalité. Dans une liste non ordonnée aucun ordre entre les éléments n'est requis. Les fonctions de parcours pourront donc utiliser l'ordre le plus rapide.

Liste ordonnée en tant que non ordonnée

Étant donné que les deux structures sont identiques, on pourra utiliser les fonctions de la liste non ordonnée sur une liste ordonnée quand l'ordre n'a pas d'importance (par exemple pour une recherche d'élément où l'ordre n'a pas d'importance).

Nomenclature

  • list : pour les listes ordonnées avec l'ordre normal
  • rev : pour indiquer l'ordre inverse (par exemple listRevFold)
  • unord : pour indiquer sans ordre (par exemple forAllOnUnordList)

Réponse

Oui, on réorganise les listes à partir de la fonction "recThing" (voir étude).