Lazi

Listes dans le sens d'haskell

Contexte

L'ordre par défaut des listes lazi est à l'envers des listes hakell. Mais ce n'est pas pratique pour les listes infinies car elles n'ont pas de dernier élément. J'avais changé pour des raisons exposées dans mes notes perso lazi "Ordre des listes".
Je m'apperçois maintenant que pour les listes infinies seulement l'ordre d'Haskell permet d'avoir une structure unique liste finie/liste infinie.

Question

L'ordre des listes comme Haskell est-il mieux ?

Étude

Comparaison

Ordre $T[ tête, reste ] (comme Haskell)

Avantages :

  • compatibilité avec le standard du lambda calcul
  • compatibilité avec les listes infinies
  • parcours dans l'ordre plus facile

Inconvéniants :

  • la construction des listes se fait avec des opérateurs associatifs à droite

Ordre $T[reste,dernier] (inverse d'Haskell)

Avantages :

  • Créer une liste à partir d'une autre en ajoutant une chose à la fin est plus courant que la même chose en ajoutant au début.
  • la construction des listes se fait avec des opérateurs associatifs à gauche

Inconvéniants :

  • incompatibilité avec les listes infinies

Solution possibles

Deux constructeurs

Un pour ajouter au début et un à la fin.
Donc une liste à la structure suivante :
Maybe $T[end_or_start_bin, élément, reste ]

C'est trop compliqué.

Utiliser l'ordre d'Haskell $[tête,reste]

Une liste est une fonction

Le code, essai 4 (retenu)

L'idée est de généraliser. Une liste prend en argument une fonction d'usage et un accumulateur et doit retourner un accumulateur. La liste vide retourne l'accumulateur tel quel et toListAdd passe tous les argument à la fonction d'usage qui fait ce qu'elle veut.

$Def emptyList = $F f,r → r

/*
Ajoute un élément (elem) en tête (place=1b) ou queue (place=0b) à une liste (list).
f est dite "fonction d'usage".
*/
$Def toListAdd = $F place,list,elem → $F f,r → f r place list elem

/*
Liste constituée d'un seul élément, placé. Remarquons qu'une liste singleton est orientée, suivant que l'élément se trouve à droite ou à gauche de la liste vide.
*/
$Def singletonList = $F place,elem → $F f,r → f r place emptyList elem

/*
À partir d'une fonction de folding left(dir=1b) ou right(dir=0b), cré une fonction d'usage de liste.
La fonction de folding prend en argument : r elem et retourne r.
On utilise une récursion interne (on a g = foldToUsage dir f) par optimisation.
*/
$Def foldToUsage = $F dir,f →

// optimisation légère de
// "$F dir,f → recurse $F g → $F r,place,list,elem → if( dir =b place ; list g (f r elem) ; f (list g r) elem )"
// car dir est fixé avant la récursion.
if(dir
,
recurse $F g → $F r,place,list,elem → if( place; list g (f r elem) ; f (list g r) elem )
,
recurse $F g → $F r,place,list,elem → if( place; f (list g r) elem; list g (f r elem) )
)

/*
Classique fold sur une liste, dans la direction dir (1b: du début vers la fin).
*/
$Def listFold = $F dir, f, r, l → l (foldToUsage dir f) r
$Def listFoldLeft = listFold 1b
$Def listFoldRight = listFold 0b

/*
On oncatène en ajoutant les éléments de l1 au début de l2, en respectant l'ordre.
*/
$Def concatList = $F l1,l2 → listFoldRight ($F e,r → toListAdd 1b r e) l2 l1

/*
Pareil que foldToUsage mais l'accumulateur est un Maybe et la récurrence s'arrête si il prend la valeur "nothing".
*/
$Def foldMaybeToUsage = $F dir,f →

// Comme le code est utilisé récursivement on optimise en mettant le "if(dir" en dehors de la récurrence. Voir foldToUsage pour une version plus didactique de cette optimisation.
if( dir
,
recurse $F g → $F r,place,list,elem →
if( place
,
$Let newR = f r elem;
if(isThing newR ; list g newR; newR)
,
$Let newR = list g r;
if(isThing newR ; f newR elem; newR)
)
,
recurse $F g → $F r,place,list,elem →
if( place
,
$Let newR = list g r;
if(isThing newR ; f newR elem; newR)
,
$Let newR = f r elem;
if(isThing newR ; list g newR; newR)
)
)

$Def listFoldMaybe = $F dir, f, r, l → l (foldMaybeToUsage dir f) r

/*
Pareil que foldMaybeToUsage mais s'arrête dans la situation inverse : quand l'accumulateur n'est pas un nothing. De ce fait à la place d'une fonction de folding, puisque l'accumulateur vaut toujours nothing, on ne le passe pas en argument et c'est une fonction de recherche qui prend un seul argument qui est l'élément de la liste et retourne un Maybe.
*/
searchToUsage = $F dir,f →

// Voir foldMaybeToUsage pour la compréhension du code.
if( dir
,
recurse $F g → $F place,list,elem →
if( place
,
$Let newR = f elem;
if(isThing newR; newR ; list g newR)
,
$Let newR = list g r;
if(isThing newR ; newR ; f elem)
)
,
recurse $F g → $F place,list,elem →
if( place
,
$Let newR = list g r;
if(isThing newR ; newR ; f elem)
,
$Let newR = f elem;
if(isThing newR; newR ; list g newR)
)
)

/*
Recherche un élément dans la liste et retourne un Maybe: nothing si pas trouvé. f est une fonction de recherche (voir searchToUsage). r n'est pas un accumulateur mais la valeur retournée quand si liste est vide.
*/
$Def listSearch = $F dir, f, r, l → l (searchToUsage dir f) r

/*
La liste est-elle vide.
*/
$Def isEmptyList = $F l → l ($F r,place,list,elem → 0b) 1b

/*
Retourne just le premier (place=1b) ou just le dernier élément de la liste ou nothing si elle est vide .
*/
$Def extremityListMaybe = $F place,l →

l
($F r,ePlace,list,elem →
if( place =b ePlace ; just elem ; replaceNothing (extremityListMaybe place list , just elem) )
)
nothing

/*
Retourne le premier (place=1b) ou le dernier élément de la liste.
*/
$Def extremityList = $F place,l → getThing \ extremityListMaybe place l

/*
Retourne la liste moins le premier (place=1b) ou le dernier élément.
*/
$Def listRemainder = $F place,l →

l
($F r,ePlace,list,elem →
if(place =b ePlace
,
list
,
if(isEmptyList list; emptyList; toListAdd ePlace (listRemainder place list) elem)
)
)
emptyList

/*
Retourne un format de liste Maybe $T[elem,tail] : nothing pour la liste vide et sinon l'élément de tête et le reste.
*/
$Def listToData = $F dir,l → listFold dir ($F r,x → just $T[x,r] ) nothing l

/*
Pareil que listFold mais pour 2 listes de même taille l et m.
*/
$Def 2listFold = $F dir,f,r,l,m →

// On parcourt l avec comme accumulateur l'accumulateur à retourner plus la liste des éléments de m sous forme de couple $T[element, reste de la liste ]. On n'a pas besoin de marqueur de fin de liste pour cette structure car les deux listes font la même taille.
pairFirst \
listFold
dir
($F $T[r,$T[y,remainder]],x → $T[ f r x y, remainder ]
)
$T[r, listFold (¬b dir) ($F r,x → $T[x,r] ) nothing m]
l

/*
Pareil que 2listFold mais retourne nothing si une erreur est retournée, soit parce que les deux listes ont des tailles différentes, soit parce que la fonction de folding (qui retourne un maybe), retourne un nothing.
*/
$Def 2listFoldMaybe = $F dir,f,r,l,m →

// Voir 2listFold pour le fonctionnement.
// L'accumulateur de listFoldMaybe est un Maybe. f retourne un Maybe mais n'en prend pas un. mm est la partie de la liste à traiter, sous forme de donnée (un Maybe $T[elem, reste ], le Maybe est pour la fin de liste).
$Let res =
listFoldMaybe
dir
($F $T[r,mm],x →
if(isThing mm // la liste m n'est pas finie ?
,
$Let $T[y,remainder] = getThing mm;
$Let newR = f r x y;
if( isThing newR; just $T[getThing newR,remainder]; nothing )
,
nothing
)
)
$T[r, listToData (¬b dir) m]
l
;
// Reste à vérifier que ce qui reste de la liste m est vide (si m était plus long on doit retourner nothing).
if(isThing res
,
$Let $T[newR,mm] = res;
if(isThing mm; nothing; just newR)
,
nothing
)

Cette solution est retenue car faire un fold sur une liste est le plus rapide que l'on puisse obtenir : il n'y a pas de teste pour savoir si la liste est finie ni de récupération de donnée.

Le code, essai 3 (échec)

L'idée est d'enlever le "stop"

/*
Ajoute un élément (elem) en tête (place=1b) ou queue (place=0b) à une liste (list).
*/
$Def toListAdd = $F place,list,elem → $F dir,f,r →

if(dir =b place
,
list dir f \ f r elem
,
f (list dir f r) elem
)

Mais ça devient compliqué pour par exemple construire listTail

Le code, essai 2 (échec)

L'idée est de généraliser

/*
Ajoute un élément (elem) en tête (place=1b) ou queue (place=0b) à une liste (list).
*/
$Def toListAdd = $F place,list,elem → $F f → f place list elem

Ça ne marche pas car on doit alors donner l'information pour la liste vide et la concaténation

Le code, essai 1 (bonne idée mais trop lourd)

list dir f r
entrées :

  • dir : direction du fold : ( 1b pour de la tête vers la queue, 0b pour de la queue vers la tête )
  • f : la fonction d'accumulation f r e :
    • entrée :
      • r l'accumulateur en cours
      • x l'élément de la liste
    • retourne : $T[ stop, r ]
      • stop : 1b si le fold doit stopper là, sinon 0b
      • r : l'accumulateur résultant
  • r : l'accumulateur, comme dans les fold de listes.
sortie : le couple $T[ r, Maybe l ] où
  • r : l'accumulateur résultant
  • Maybe l : nothing si on n'a jamais stoppé, sinon just le reste de la liste

$Def emptyList = $F dir,f,r → $T[ r, nothing ]

$Def isEmptyList = $F l → pairFirst \ l 0b ($F r,x → $T[ 1b,0b ]) 1b

$Def singletonList = $F x,dir,f,r →

$Let $[stop,newR] = f r x;
$T[ newR, if(stop; just emptyList; nothing) ]

/*
Ajoute un élément (elem) en tête (place=1b) ou queue (place=0b) à une liste (list).
*/
$Def toListAdd = $F place,list,elem → $F dir,f,r →

if(dir =b place
,
$Let $T[stop,newR] = f r elem ;
if(stop; $T[newR, just list]; list dir f newR)
,
$Let[ newR, ml ] = list dir f r;
if( isNothing ml; singletonList elem dir f newR; $T[ newR, just \ toListAdd place (getThing ml) elem ] )
)

/*
Concaténation des listes l1 et l2
*/
$Def concatList = $F l1,l2 → $F dir,f,r →

if(dir
,
$Let[ newR, ml ] = l1 dir f r;
if( isNothing ml; l2 dir f newR; $T[ newR, just \ concatList (getThing ml) l2 ] )
,
$Let[ newR, ml ] = l2 dir f r;
if( isNothing ml; l1 dir f newR; $T[ newR, just \ concatList l1 (getThing ml) ] )
)

/*
Récupère l'élément de tête (dir=1b) ou de queue et le reste de la liste. Il est nécessaire que la liste ne soit pas vide.
*/
$Def getExtremityAndRestList = $F dir,l →

$Let[ x, ml ] = l dir ($F r,x → $T[1b,x]) nothing;
$T[x, getThing ml]
$Def getExtremityList = $F dir,l → pairFirst \ getExtremityAndRestList dir l
$Def getRestList = $F dir,l → pairSecond \ getExtremityAndRestList dir l
$Def getHeadList = getExtremityList 1b
$Def getLastList = getExtremityList 0b
$Def getTailList = getRestList 1b
$Def getInitList = getRestList 0b

/*
Reconstruit la liste pour qu'elle soit rapide d'accès dans un certain sens (ord, 1b: de la tête vers la queue). Permet aussi de réduire la taille de la formule constituant la liste. Cette fonction peut être pratique si on a construit une liste par des opérations diverses et qu'elle est par la suite destinée essentiellement à être lue dans un certain sens.
*/
$Def reconstructList = $F ord,l → l (¬b ord) ( $F r,x → $T[0b,toListAdd ord r x] ) emptyList

/*
Comme toListAdd mais pour une fonction f sans stop et un parcours dans le sens de la liste. Le résultat n'est donc pas vraiment une liste mais est plus rapide.
*/
$Def toListAddNoStop = $F list,elem → $F f,r → list f \ f r elem

$Def emptyListNoStop = $F f,r → r

/*
Comme reconstructList mais sans stop. Voir toListAddNoStop.
Si l est reconstruite par reconstructListNoStop, l f r réalisera un fold rapide qui retourne directement l'accumulateur.
*/
$Def reconstructListNoStop = $F l →

// On parcours l dans l'ordre inverse pour ne pas changer l'ordre des éléments.
l 0b ( $F r,x → toListAddNoStop r x ) emptyListNoStop

Rapidité

Il sera courant que la liste sera construite à base de toListAdd. Un fold sur la liste sera alors au moins aussi rapide qu'avec l'ancienne liste.

On obtient donc au final une liste agnostique de point de vue du sens, pouvant être infinie et au moins rapide que les listes standards. De plus le sens de parcours devient un paramètre et on a une meilleurs symétrie des fonctions.

Implémentation

On garde l'opérateur +le et l'ordre par défaut (inverse d'Haskell) pour ne pas avoir à changer un grand bout de code et pour garder l'opérateur d'ajout associatif à gauche.

  1. Répertorier les traductions de listes utilisant la représentation en paire dans :
    • le source lazi
    • translate
    • compute
    • les testes
  2. Enregistrer la rapidité actuelle des évaluations pour pouvoir comparer avec la nouvelle version.
  3. Créer une branche git. Utiliser un autre répertoire pour le code source dans cette branche de manière à continuer la doc dans la branche Master.
  4. Traduire en utilisiant toListAdd et emptyList.

Réponse

On peut créer une liste agnostique sur son orientation, au moins aussi rapide, et supportant les listes infinies. Le changement utilisant cette liste (voir code essai 4) est fait.