Système listes et entiers

Un autre système plus simple peut alors être proposé, en donnant un sens plus simple au liste, et en prenant comme univers l'ensemble des entiers naturels. Un entier est un élément. Une liste est un opérateur qui s'applique à un élément i et qui retourne ce qu'elle contient à l'indice i. Si cette indice est plus grand que la liste, deux conventions sont envisagées. Soit on convient que cela retourne FAIL, une valeur absorbante spécifique au processus de calcul. C'est le point de vue tronqué. Soit on convient d'en prendre le modulo par la taille de la liste. Tous ce passe alors comme si la liste se répétait indéfiniment. C'est le point de vue harmonique. Le résultat n'est pas forcement un élément, il peut être une autre liste, auquel cas cela correspond à un autre opérateur qui peut, à son tour être appliqué à un entier. Et par currification il convient de pouvoir appliquer une liste d'argument ainsi. Reste à préciser ce que produit un entier lorsque celui-ci est appliqué à un entier alors qu'il ne le devrait pas puisque ce n'est pas un opérateur. Et bien la meilleur solution la moins arbitraire consiste à dire que cela produit justement la liste de ces deux entiers, et que un entier appliqué à une liste de k arguments produits une liste de k+1 arguments. On représente l'opération appliquant un terme sur un autre par le symbole >. Dans ce langage ainsi définie, nous avons par exemple :

(0,1,2,3) = 0>(1>(2>3))
(4,5,6,7)>1 = 5
4>(5>(6>7))1 = 5
(0,1,2,(5,6))>(3,1,7) = (6,7)
(8,9)>(1,2,3,4,5) = (9,2,3,4,5)

L'opération virgule "," est associative, par contre l'opération d'application ">" n'est pas associative. L'opértaion de composition "°" est associative :

( (1,2,(3,4)) ° (2,1) ° (1,0,2) )>(1,2) = 4

L'opération de composition parallèle "//" est aussi associative :

((5,4),(9,8),2,(7,6)) // (1,0) = ((4,0),(8,0),(2,1,0),(6,0))

L'opération de composition parallèle cyclique "///" est aussi associative :

((5,4),(9,8),2,(7,6)) /// (1,0) = (4,9,(2,1),7)