Introduction à la programmation fonctionnelle

Philippe Muller

septembre 2004

Philippe Muller Introduction à la programmation fonctionnelle

Introduction à la programmation fonctionnelle
Réfléchir aux principes de base de la pro-
grammation et de l’informatique à travers
Objectif du cours:
l’apprentissage d’un langage simple mais
puissant.
Différence entre
“programmation” (concept abstrait)
“programmation sur machine” (réalisation particulière d’un
processus de conception).
→ relative indépendance du langage vis à vis des problèmes de
programmation
le choix du langage tient à deux choses:
puissance d’expression pour résoudre des problèmes complexes
et
facilité d’utilisation et d’apprentissage pour se concentrer sur
l’essentiel
→ choix de la programmation fonctionnelle
n
Philippe Muller Introduction à la programmation fonctionnelle
La programmation fonctionnelle ?

concept fondamental: l’abstraction traiter une chose complexe en la

divisant en choses plus simples et en ignorant les détails.
objets de base : la fonction un programme est un ensemble de
fonctions traitant des données d’entrée
des langages interprétés
instructions / interprété au fur et à mesure —> machine
6= langages compilés :
instructions / préparation (compilation) / execution
avantage/ inconvénients
évaluation / débuggage plus souple
plus lent (mais on peut toujours compiler)

Philippe Muller Introduction à la programmation fonctionnelle

Le langage choisi : Camel

la programmation fonctionnelle est une famille de langage très

proches, dont le plus célèbre est LISP développé au MIT.
le successeur de LISP: scheme: plus léger, plus simple et aussi
puissant, utilisé pour l’éducation ou le scriptage (ex: Gimp)
mais pas de typage des données ; on utilisera donc un autre langage
fonctionnel typé:
Camel

Philippe Muller Introduction à la programmation fonctionnelle

A retenir

processus de calcul : êtres abstraits mis en œuvre dans les ordinateurs ;

données : ou information, objets manipulés par les processus ;
programme : contrôle évolution des processus ;
langage de programmation : traduit les processus de façon symbolique
interprète : traduit les processus écrit dans un langage de
programmation.

Philippe Muller Introduction à la programmation fonctionnelle

Elements de base de la programmation

Le langage de programmation :
permet de donner des instructions ;
constitue un cadre d’organisation des processus de
calcul.
Pour la programmation on distingue souvent deux sortes ”d’objets”:
les données (par ex. les nombres)
les procédures (par ex. l’addition de nombres)

Philippe Muller Introduction à la programmation fonctionnelle

Elements du langage

des expressions primitives (nombres, fonctions de base)

des moyens de composition pour construire des expressions composees
d’expressions primitives
des moyens d’abstraction pour nommer et manipuler des objets
composés comme un tout, comme si c’était une expression
primitive.

Philippe Muller Introduction à la programmation fonctionnelle

Les expressions
l’interprète Camel évalue des expressions

> Caml Light version 0.74

#1230 ;;
- : int = 1230
la réponse précise le type de la réponse avec sa valeur.

# 10 + (3*4);;
- : int = 22
+, /, * sont des opérateurs décrivant des procédures primitives, les
nombres sont des expressions primitives.
Une expression composée est formée à partir d’expressions (primitives ou
non) et d’opérateurs, terminée par ; ;
operateur
z}|{
3
|{z} + (5 ∗ 4) ; ;
| {z }
expression expression

Philippe Muller Introduction à la programmation fonctionnelle

Les types de base d’expressions

les entiers (int) : les nombres entiers relatifs.

les réels (float) : nombres décimaux. 1.67
les booléens : le vrai (true) et le faux (false).
les caractères (char) : ’a’ ’X’ ’&’
les chaı̂nes de caractères (string) “bonjour”
Les opérateurs n’acceptent que certains types comme arguments. Par
exemple, + ne prend que des entiers :

# "toujours" + 29 ;;
Entrée interactive:
> "toujours" + 29 ;;
> ^^^^^^^^^^
Cette expression est de type string,
mais est utilisée avec le type int.

Philippe Muller Introduction à la programmation fonctionnelle

Les définitions

Pour manipuler des objets, nécessité de les nommer: l’opérateur let

# let j = 20 ;;
j : int = 20
# 30 - j ;;
- : int = 10
# let k = 3* j + 27;;
k : int = 87
La définition est le moyen de base de l’abstraction.
Elle permet :
de représenter le résultat d’opérations composées ;
de construire des objets complexes par étapes
⇒ développement et test incrémental des programmes.
Pour cela il faut pouvoir définir des procédures, moyen d’abstraction plus
puissant que le nommage d’un objet, en nommant des opérations
composées à partir de paramètres.

Philippe Muller Introduction à la programmation fonctionnelle

Les fonctions

nécessité de manipuler des fonctions, avec paramètres de différentes

sortes, en nombre différents → besoin d’abstraire les fonctions
ce qui définit une fonction : ses paramètres (appelés variables en
maths) et la façon dont on la calcule ;
Par ex. carre : x → x*x
mais une fonction peut l’être de plusieurs choses: l’énergie cinétique
en physique,
EC: m v → 1/2mv 2
Pour définir une fonction on spécifie donc les paramètres et le corps:
let cinetik m v = 0.5 *. m *. v *. v ;;
retourne la fonction
cinetik : float -> float -> float = <fun>
A l’application d’une fonction, par ex. (cinetik 75.5 25.9), les
paramètres formels sont remplacés par les valeurs fournies.

Philippe Muller Introduction à la programmation fonctionnelle

Les expressions conditionnelles

Une expression conditionnelle permet l’évaluation d’une expression

différenciée selon une condition (vrai ou fausse). Par exemple la définition
de la valeur absolue est une expression conditionnelle :
|x| = x si 0 ≤ x
−x sinon
Elle se traduit en Camel par

let abs x = if x >=0 then x

else -x ;;

Philippe Muller Introduction à la programmation fonctionnelle

Conditionnelles (suite)

On peut utiliser les opérateurs suivants sur les conditions (booléens):

= égalité (opérateur polymorphe)
or “ou” logique
& “et” logique
not négation
exercice : x < y < 20
x ≤ 15

Philippe Muller Introduction à la programmation fonctionnelle

Exercices

1 Evaluer les expressions suivantes

10 ; ;
5 + 3 + 4;;
9 - 1. ; ;
6 / 2;;
let a = 3 ; ;
let b = a + 3 ; ;
a + (b * a) ; ;
a = b;;
if a = 4 then 6
else if b = 4 then 6+7+a
else 25 ; ;
2 Ecrire une fonction qui calcule la circonférence d’un cercle en
fonction de son rayon.

Philippe Muller Introduction à la programmation fonctionnelle

Processus et procédures : la récursion

1 Ecrire une procédure qui calcule la factorielle :

fact(n) = n ∗ (n − 1) ∗ · · · ∗ 3 ∗ 2 ∗ 1 = n ∗ fact(n − 1)
2 Ecrire une procédure qui calcule la suite de Fibonacci:
u(0) = 1
u(1) = 1
u(n) = u(n − 1) + u(n − 2)

Philippe Muller Introduction à la programmation fonctionnelle

A retenir :

Le sens d’une procédure est indépendant des noms des paramètres

formels:
let carre x = x * x ; ;
let carre y = y * y ; ;
Les noms des paramètres d’une procédure sont locaux au corps de la
procédure
let assez_bon estimation x =
(abs ((carre estimation) - x)) < .0001 ;;
let carre x = x * x;;

Philippe Muller Introduction à la programmation fonctionnelle

Exercices

Ecrire des fonctions réalisant les opérations suivantes :

1 calcul de la norme d’un vecteur (2d) donné par ses coordonnées
2 calcul de la moyenne de deux nombres (réels)
3 calcul du maximum de deux entiers
4 vérifier si 3 nombres correspondent aux longueurs des côtés d’un
triangle rectangle

Philippe Muller Introduction à la programmation fonctionnelle

Processus et procédures

Pour savoir programmer il faut :

connaı̂tre les éléments de base de la programmation
avoir l’expérience de la programmation :
connaı̂tre les procédures les plus utiles
être capable de prévoir le déroulement des acions qui suivra le
processus et de diriger ce déroulement par un programme.
et maintenant quelques formes typiques de déroulement de processus...

Philippe Muller Introduction à la programmation fonctionnelle

Exemple : extraction de racine carrée

différence entre fonctions mathématiques et fonctions programmées

fonction mathématique procédures informatiques

définit une valeur déterminée par un produit un résultat
ou plusieurs paramètres
√
ex x = y tel que 0 ≤ y et y 2 = x mais ne dit pas la valeur exacte...
propriétés réalisation

Philippe Muller Introduction à la programmation fonctionnelle

Exemple : extraction de racine carrée

and now for something completely different... la méthode de Newton par

approximations successives : √
au départ si y est une approximation de x, une meilleure approximation
est donnée par la moyenne de y et x/y .
Estimation Quotient x/y Moyenne
1 2 1.5
Exemple pour x = 2 : 1.5 1.333333 1.4167
1.4167 1.4118 1.41412
1.41412 ... ...
Exercice : écrire les procédures qui permettent de calculer la racine avec
cette méthode.

Philippe Muller Introduction à la programmation fonctionnelle

Exercices

Ecrire des fonctions réalisant les opérations suivantes :

1 le maximum de trois entiers.
2 la puissance quelconque d’un entier (fonction f (x, n) = x n )
Xi=n
3 la somme des entiers de 1 à n ( i)
i=1
i=q
X
4 la somme des entiers de p à q ( i)
i=p
5 la somme de deux entiers en utilisant la fonction suivante :
let inc n = 1 + n;;

Philippe Muller Introduction à la programmation fonctionnelle

Retour sur la récursion

rec. sémantique :
(fact 5) rec. syntaxique seulement :
→ 5*(fact 4) (racine1 2.0 1.0)
→→ 5*4*(fact 3) (racine1 2.0 1.5)
→→→ 5*4*3*(fact 2) (racine1 2.0 1.4167)
...→ 5*4*3*2*(fact 1) (racine1 2.0 1.41412)
...→ 5*4*3*2*1*(fact 0) 1.41412
puis “remontée” des appels

Philippe Muller Introduction à la programmation fonctionnelle

Les procédures et les structures de bloc

Racine1 : premier exemple de processus défini par un ensemble de

procédures mutuellement définies.

Décomposition d’un programme en procédures (sous-problèmes):

pourrait être arbitraire ? blocs de 10 lignes
→ non: l’important est que chaque procédure exécute une tâche
bien définie

on n’est pas obligé de s’occuper de la façon dont la procédure calcule

ce qu’on lui demande de calculer: ce qui nous intéresse est le résultat

L’utilisateur d’une procédure n’est pas forcément son auteur

→ il peut la recevoir comme une boı̂te noire venant d’un autre,
réalisant une certaine fonction (d’où l’importance de l’explicitation
des paramètres, “interface” unique entre la fonction et le
programmeur qui l’utilise.

Philippe Muller Introduction à la programmation fonctionnelle

Les noms locaux

on peut définir une liaison de (nom,valeur) dont la portée est le corps de

la procédure :
Exemple: pour max3

let max3 a b c =
let m=(max a b)
in (if m>c then m
else c);;
On peut définir plusieurs liaisons (évaluées indépendamment) :

let max3 a b c =
let m1=(max a b)
and m2=(max b c)
in (max m1 m2);;
si plusieurs définitions successives sont nécessaires, il faut imbriquer:
let a = 3.2/.53.5 in let b = a *. a in ...

Philippe Muller Introduction à la programmation fonctionnelle

Les procédures et les structures de bloc : noms
locaux

les noms des paramètres d’une procédure sont locaux au corps de la

procédure ; le nom d’un paramètre de fonction est une variable liée
(le sens de l’expression ne change pas si on renomme le paramètre).

une variable qui n’est pas liée est ... libre

l’ensemble des expressions pour lesquelles une liaison définit un nom

est appelé la portée de ce nom.

les variables liés déclarées comme paramètre d’une procédure ont

pour portée le corps de cette procédure.

les variables libres ont pour portée le corps du programme.

Philippe Muller Introduction à la programmation fonctionnelle

Les procédures et les structures de bloc : liaisons
locales

Sur l’exemple de la racine carrée, le programme est composée de

procédures séparées, permettant le contrôle de l’usage des noms.
⇒ inconvénient : seul l’appel à racine est utile vu de l’extérieur (ce qui
peut être un problème pour les gros programmes)
⇒ on peut enfermer les sous-procédures avec des liaisons locales.

let racine x =
let rec ameliore estimation x =
(moyenne estimation (x /. estimation))
and assez_bon estimation x =
(abs_float ((carre estimation) -. x)) < 0.0001
in let rec racine1 estimation x =
if (assez_bon estimation x)
then estimation
else (racine1 (ameliore estimation x) x)
in racine1 1.0 x ;;

Philippe Muller Introduction à la programmation fonctionnelle

Structure de données composées

Jusqu’ici on a vu uniquement des données primitives, des types fournis

par le langage.
Pour la plupart des problèmes on a besoin de représenter des données
plus complexes.
De même qu’à partir de procédures simples on peut faire des procédures
composées, on peut construire des types.

on veut faire une procédure qui donne le min et en même temps le max
de deux entiers. Mais une fonction ne renvoie qu’une valeur.
→ on peut utiliser un type composé de deux valeurs: un doublet.
Notation : (2,3)
let minmax x y = if x < y then (x,y) else (y,x);;
let minmax x y = (min x y), (max x y);;
De même on peut utiliser des triplets, des n-uplets... (tuples).

Philippe Muller Introduction à la programmation fonctionnelle

Utilisation des doublets

Comment récuperer une valeur de doublet ?

let zorgbl x y =
let m = minmax x y
in (2 * (fst m) + (snd m));;

let zorgbl x y =
let (m1,m2) = minmax x y
in (2* m1 + m2);;

Philippe Muller Introduction à la programmation fonctionnelle

Intérêt

regrouper des données liées intrinsèquement dans un seul objet.

Exemple : les vecteurs.
Si on écrit une somme de 2 vecteurs (à deux dimensions):

let som_vect x1 y1 x2 y2 = (x1+x2),(y1+y2) ;;

Plus structuré (plus abstrait):

let som_vect v1 v2 = (fst v1)+(fst v2), (snd v1)+(snd v2);;

Philippe Muller Introduction à la programmation fonctionnelle

Les Listes

Si on a besoin d’un nombre quelconque (et qui peut évoluer) de données

similaires, on ne peut se contenter de tuples (ex: dictionnaire de mots).
Pour cela on peut utiliser des listes: une liste est un ensemble de données
de même type.
on note une liste [ donnee1 ; donnee2 ; ... ; donneep ]
[ 2 ; 19 ; 16 ; 23 ; 20 ]
La liste vide est notée []
On peut extraire des éléments d’une liste grâce aux deux opérations
suivantes, hd(head), tl(tail):

hd [ 23 ; 45 ; 78 ] ; ; retourne 23
tl [ 23 ; 45 ; 78 ] ; ; retourne [ 45 ; 78 ]
On peut construire une liste avec les opérateurs suivants :

23::[ 45 ; 67 ] retourne [ 23 ; 45 ; 67]

[96 ; 23]@[ 45 ; 67 ] retourne [ 96 ; 23 ; 45 ; 67]

Philippe Muller Introduction à la programmation fonctionnelle

Les Listes

La liste est un type récursif:

une liste est <un élément>::<une liste>
→ la plupart des fonctions de listes peuvent etre exprimés de façon
récursive.
Ex: compter les éléments d’une liste :

let rec compter une_liste =

if une_liste=[] then 0
else (1 + compter (tl une_liste));;

Philippe Muller Introduction à la programmation fonctionnelle

Exercices

1 comment accéder au 3e élément de [1 ; 2 ; 3 ; 4 ; 5]

2 comment accéder à l’élément 7 de [ [1 ; 2 ; 3] ; [2 ; 7] ]
3 construire les listes avec :: et @
1 [1 ;2] ajouté devant l
2 [1 ;2] ajouté à l1 et [3 ;4]
3 l et 1 à la fin
4 une liste avec 1 ajouté devant l1 et 3 devant l2

Philippe Muller Introduction à la programmation fonctionnelle

Encore des exercices

1 Ecrire une fonction qui retourne le maximum d’une liste d’entiers.

2 Ecrire une fonction qui retourne la somme des éléments d’une liste
3 Ecrire une liste qui retourne la liste des carrés des éléments d’une
liste entière.
4 Ecrire la fonction map qui retourne la liste des éléments d’une liste
auxquels on a appliqué une fonction f.
ex: (map [1 ; 2 ; 3] carre) → [1 ; 4 ; 9]

Philippe Muller Introduction à la programmation fonctionnelle

Encore des exercices

1 dernier l
2 enlever 1 x l
3 enlever tous x l
4 append → concaténation (la refaire!)
5 reverse (inversion)

Philippe Muller Introduction à la programmation fonctionnelle

Fonctions d’ordre supérieur

On a pu remarquer que des procédures différentes se ressemblent dans

leur structure, par exemple :

let rec somme_n n =

if n=0 then 0
else n+ somme_n (n-1);;
let rec somme_carres n =
if n=0 then 0
else n*n+ somme_carres (n-1);;
On peut abstraire encore plus ces opérations en prenantPcomme
n=1
paramètre la fonction utilisée à chaque fois. (calculant n=p f (n)). Pour
cela on peut avoir des fonctions comme paramètres :

let rec somme f n =

if n=0 then (f 0) else (f n)+ (somme f (n-1));;

Philippe Muller Introduction à la programmation fonctionnelle

Utilisation
Comment alors désigner la fonction utilisée dans le cas de somme n et
somme carres ?
On pourrait redéfinir une fonction identité (et une fonction carré), mais
on peut aussi désigner la fonction par sa définition en la notant :
fun x -> x (et fun x -> x*x)
D’où :

let somme_n n = somme (fun x -> x) n;;

let somme_carre n = somme (fun x -> x*x) n;;
Si on revient sur le type de somme :
(int -> int) -> int -> int = <fun>
On voit qu’en appliquant un paramètre à somme on a une expression de
type int -> int (une fonction !).
On pourrait donc écrire encore plus simplement :

let somme_n = somme (fun x -> x) ;;

(Quel est son type ?)
...on peut donc aussi avoir des fonctions qui ont pour résultat une
fonction.
Philippe Muller Introduction à la programmation fonctionnelle
Exercices

écrire des fonctions calculant

1 la fonction dérivée (approchée) d’une fonction réelle, sachant que :

f (x) − f (x0 ) f (x0 + e) − f (x0 )

f 0 (x0 ) = lim = lim
x→x0 x − x0 e→0 e
2 la composition de deux fonctions (f o g). L’appliquer à: f n , et la
dérivée de (f o g).
3 le zéro d’une fonction monotone par dichotomie.
4 écrire une fonction filtre qui ne garde d’une liste que les éléments
qui vérifient une condition passée en paramètre.

Philippe Muller Introduction à la programmation fonctionnelle

Encore plus

écrire une fonction qui effectue un parcours de liste en effectuant une

même opération sur tous les éléments ; l’appliquer pour faire des
fonctions qui respectivement:
fait la somme des éléments d’une liste
calcule la longueur d’une liste
teste si qqchose appartient à une liste
ajoute un élément à la fin d’une liste
refait la fonction map.
refait la fonction filtre
renverse une liste

Philippe Muller Introduction à la programmation fonctionnelle

Solutions

let rec parcours f el_neutre l =

if l=[] then el_neutre
else (f (hd l) (parcours f el_neutre (tl l)));;

let somme = parcours (fun x y -> (x + y)) 0 ;;

let longueur = parcours (fun x y -> (1 + y)) 0 ;;

let membre l a = parcours (fun x y -> (x=a) or y) false l ;;

let ajoute l a = parcours (fun x y -> x::y) [a] l ;;

let remap l f = parcours (fun x y -> (f x)::y) [] l;;

let refilter f = parcours (fun x y -> (if (f x) then x::y else y

let reverse = parcours (fun x y -> y@[x]) [];;

Conclusion : il faut factoriser !
Philippe Muller Introduction à la programmation fonctionnelle
Le filtrage
la définition d’une fonction par x -> .. (= “à x on associe ...”) peut se
diviser :
let rec truc = fun
0 -> 1
| 1 -> 1
| x -> (truc (x-1)) + (truc (x-2));;
Sur des couples :

let machin = fun

(0,0) -> 0
| (x,0) -> x+1
| (_,1) -> 2
| (x,y) -> y ;;
Sur des listes :
let rec quoi = fun
[a] -> a
| (t::q) -> quoi q;;
Philippe Muller Introduction à la programmation fonctionnelle
Rencontres du septième type

Dans certains cas on peut vouloir définir un objet en le représentant avec

des types différents. Par exemple un être humain peut être un désigné par
son nom où par un numéro (de sécu par exemple). Dans ce cas on peut
spécifier ce type de la façon suivante :

#type identite = Nom of string

| SS of int;;
#let j = Nom("jacko");;
j : identite = nom "jacko"
#let p = SS(109090190);;
p : identite = ss 109090190
Et on peut faire un filtrage pour traiter les cas :

let afficher = fun

(Nom x) -> print_string x
| (SS x) -> print_int x ;;

Philippe Muller Introduction à la programmation fonctionnelle

Encore une somme

Imaginons maintenant que l’on veuille construire un type complexe

mélangeant des types différents plus compliqués, par exemple des
expressions arithmétiques abstraites simples, comme :
2*x + y*x + 3
Comment faire ? Il faut d’abord analyser les expressions : une expression
correcte est formée avec un opérateur et deux arguments, qui sont aussi
des expressions :
(2 * x) + ((y * x) + 3)
Faire une liste ? impossible à cause des types différents ...→ le type
“somme”.

Philippe Muller Introduction à la programmation fonctionnelle

type expr = const of int
| operation of (int * ?? * int);;

type operateur = Plus | Moins | Mult | Div ;;

type expr = const of int

var of string
| op of (int * operateur * int);;

type expr = const of float

var of string
| op of (expr * operateur * expr);;

let exemple = op(op(const(2.),Mult,var("x")),Plus,op(....

Exercices :
simplification (des zéros et des uns).
dérivée symbolique d’une expression par rapport à une variable.

Philippe Muller Introduction à la programmation fonctionnelle

Construire un nouveau type : les ensembles

Quels opérations veut-on faire sur les ensembles ?

On va essayer d’isoler des opérations primitives sur les ensembles
toutes les operations doivent pouvoir se déduire des fonctions
primitives.
→ l’implantation ne dépendra que des opérations primitives ; en cas
de modifications, le reste ne changera pas.
Opérations primitives :
ens vide
est vide
ajoute elem
un elem
autres elems
appartient a

Philippe Muller Introduction à la programmation fonctionnelle

Les ensembles (2)

A partir de là, écrire :

union
intersection
est inclus
egaux
retire elem
listes des parties
(E = G ∪ a,
P(E ) = P(G ) ∪ (P(G ) ⊕ a)
Avec {E1 , E2 , ..., En } ⊕ a = {E1 ∪ {a}, E2 ∪ {a}, ..., En ∪ {a}}
creer ens, prenant une liste d’éléments et renvoyant l’ensemble les
contenants.

Philippe Muller Introduction à la programmation fonctionnelle

Les ensembles (3)

Maintenant, quelles propriétés doivent satisfaire les primitives pour

implémenter les ensembles ?
union un elem(a) autres elems(a)=a
un elem( ajoute elem a ens vide())=a
est vide(ens vide)= oui
...
Programmer les primitives en se basant sur des listes.
Comment améliorer certaines procédures (ajoute un élément, ...)

Philippe Muller Introduction à la programmation fonctionnelle

Un nouveau type : les arbres binaires

tout noeud a deux descendants: gauche et droit

arbres d’entiers: toute valeur à G ≤ valeur du noeud < valeur à
droite

Philippe Muller Introduction à la programmation fonctionnelle

Construire un nouveau type : les arbres binaires

Arbre binaire : opérations primitives

arbre vide
arbre est vide
arbres egaux
fils g
fils d
creer arbre
racine (valeur de la racine)

Philippe Muller Introduction à la programmation fonctionnelle

Les arbres binaires

Arbre binaire: opérations supérieures (dépendent des primitives

seulement)
somme des valeurs
hauteur
ajout arbre
ajout valeur
croissant val (arbre → liste)
insere liste int → arbre binaire
sous arbre

Philippe Muller Introduction à la programmation fonctionnelle

The end: Récapitulation des principes de base

décomposer le problème
isoler les parties
⇒ facile à modifier + facile à réutiliser
encore un exemple :
modifier “ensemble” avec arbre binaire
ens vide / est vide / ajoute elem / un elem / autre elem /
appartient
comparaison performances ?

Philippe Muller Introduction à la programmation fonctionnelle

Exo: les arbres de Huffman (préparation au TP)

parcours avec liste de 0,1 (codage huffman)

0 = aller à gauche
1 = aller à droite
get a [0 ; 1 ; 0 ; 1] —- sous arbre
feuille a [0 ; 1 ; 0 ; 1] — fail ou valeur
application: codage séquence, arbre binaire est arbre binaire de
lettre :
- code one
- decode one
- codage = “hello” → “0101010”
- decodage “0101010” → “hello”
-puis decodage (1 char, 1 suite)

Philippe Muller Introduction à la programmation fonctionnelle