Définition d'objets et de structures de données récursives
----------------------------------------------------------

Listes chaînées : structure récursive
Une liste est soit :
- une liste vide                                           []
- une tête (un premier élément) et une queue (une liste)   t :: q

Une liste est un ensemble de cellules
  { elt: int; suite: *liste }

    longueur([]) = 0
longueur(t :: q) = 1 + longueur(q)

let rec longueur = function
  | []   -> 0
  | t::q -> 1 + longueur(q)


Terme : notion générale d'objet structuré, potentiellement récursif

[]
1 :: []
1 :: 2 :: 3 :: []

Syntaxiquement, j'ai utilisé :
- des nombres entiers
- un symbole pour la liste vide : []       Nil
- un symbole 'ajouter au début' : ::       Cons
- la concaténation de suites de symboles

1 :: :: [] 2
Toutes les suites de symboles ne sont pas acceptables
- :: doit être précédé d'un entier et suivi d'une liste
- la suite doit terminer par []

1 :: 2 :: 3 :: []
1 :: (2 :: (3 :: []))

Mes règles peuvent être traduites par une grammaire (algébrique,
a.k.a. non contextuelle)

(PIL)
liste  ->  []
       |   int :: liste

(IPF)
type liste = Nil
           | Cons of int * liste

En réalité, il s'agit d'une définition par clôture, permettant de
caractériser, parmi les séquences de symboles, celles qui sont bien
structurées. On cherche à définir un ensemble un ensemble 'liste'
(l'ensemble des listes).

Chaque règle d'inférence va correspondre à une forme de terme


---------- (a)
[] ∈ liste


(prémisses)
n ∈ ℕ      lst ∈ liste
---------------------- (b)
   n :: lst ∈ liste
(conclusion)

(a) [] ∈ liste
(b) ∀n∈ℕ, ∀lst∈liste, n :: lst ∈ liste


Principe de récurrence associé :

Soit une propriété P telle que
(a) P([])
(b) ∀n∈ℕ, ∀lst, P(lst) -> P(n :: lst)
Alors
∀lst ∈ liste, P(lst)

(b') ∀n∈ℕ, ∀lst∈liste, P(lst) -> P(n :: lst)

Et aussi, possibilité de définir des fonctions par récurrence



Digression syntaxe/sémantique
Syntaxe : 1 :: 2 :: 3 :: [], ou Cons(1, Cons(2, Cons(3, Nil)))
Sémantique : la liste formée par 1, 2, 3
Ici on a une bijection entre les deux, car il n'y a qu'une manière
syntaxique de construire chaque objet (voir notion d'algèbre libre).


Généralisation
--------------

Signature : ensemble des symboles utilisés, chacun associé à une arité
L'arité d'un symbole est le nombre d'autres objets avec lesquels il
doit être combiné

Signature des listes :
- Nil, d'arité 0   (prend 0 paramètres)
- Cons, d'arité 2  (prend 2 paramètres)

Étant donnée une signature Σ, on définit l'ensemble T(Σ) des termes
sur Σ par les règles d'inférence suivantes :

Pour chaque symbole f d'arité n, on a une règle

t₁ ∈ T(Σ)      ...     tₙ ∈ T(Σ)
--------------------------------
     f(t₁, ..., tₙ) ∈ T(Σ)

Cas particulier de l'arité 0 : pas de paramètres, donc pas de
prémisses => axiome.


Notion de 'sorte' : permet, dans la signature, d'indiquer la nature de
chaque paramètre (correspond à des types)

- Nil ne prend de paramètres : liste    ( () ⟶ liste )
- Cons prend un paramètre int et un paramètre liste : ℕ x liste ⟶ liste

Parmi les différents types utilisables :
- les types de base (ℕ, ...)
- le type des termes qu'on est en train de définir


Un arbre binaire, c'est : un ensemble de nœuds, tel que chaque nœud a
un fils gauche et un fils droit (et l'ensemble est bien connexe/acyclique).

Un arbre binaire, c'est :
- soit l'arbre vide (qu'on appelle dans les notes de cours 'Feuille')
- soit un nœud, qui possède un élément, et deux sous-arbres

Signature correspondante :
- Symbole F, d'arité 0         F: arbre
- Symbole N, d'arité 3         N: arbre x ℕ x arbre -> arbre

       1
      / \
     2  
    / \


       1
      / \
     2  F 
    / \
    F F

N(N(F, 2, F), 1, F)

---------
F ∈ arbre

a₁∈arbre     n∈ℕ     a₂∈arbre
-----------------------------
     N(a₁,n,a₂) ∈ arbre

Définition d'une fonction 'taille' (nombre de nœuds ~ nombre d'éléments)
taille(F) = 0
taille(N(a₁, n, a₂)) = 1 + taille(a₁) + taille(a₂)

Définition d'une fonction 'hauteur' (nombre de nœuds à parcourir pour
arriver à une feuille)
hauteur(F) = 0
hauteur(N(a₁, n, a₂)) = 1 + max(hauteur(a₁), hauteur(a₂))

Variante : feuille d'arité 1,    F: ℕ ⟶ arbre


Autre famille d'exemples : représenter la syntaxe d'un programme,
d'une formule logique, d'une expression arithmétique...

1 + 2 x 3

Signature :
- des nombres entiers (ℕ)                       n   : A
- des symboles binaires +, x, etc, d'arité 2    Add : A x A ⟶ A

Add(1, Mult(2, 3))
Avec le mauvais parenthésage on pourrait avoir Mult(Add(1, 2), 3)
Mais la forme de terme rend explicite la structure.

Syntaxe Add(1, Mult(2, 3))
pour représenter l'expression arithmétique 1 + 2 x 3
(qui si on applique ensuite la sémantique de l'arithmétique donne 7)

Définition d'une fonction d'évaluation :
eval(n) = n
eval(Add(a₁, a₂)) = eval(a₁) + eval(a₂)
eval(Mult(a₁, a₂)) = eval(a₁) * eval(a₂)


Programmation objet :
un arbre binaire est soit une feuille, soit un nœud.

abstract class Arbre {
    abstract int taille();
    abstract int hauteur();
}

class Feuille extends Arbre {
    int taille() { return 0; }
}

class Nœud extends Arbre {
    int elt;
    Arbre a1, a2;
    int taille() { return 1 + a1.taille() + a2.taille(); }
}