Méthodologie de la Programmation Fonctionnelle
Premier semestre 2011-2012

Généralités
"Let's Play!"
"Let's have fun!"
"Let It Play!"(Métaprogrammation)
Le partiel
Vos sujets de projets

Généralités
- Plan
- Méthode
  Sous xterm taper
  drscheme &
  une fenêtre Lisp s'ouvre.
  Il faut d'abord choisir un langage. Deux méthodes au choix :
  - Dans la fenêtre du haut tapez "#lang racket" et ne faites plus rien dans cette fenêtre.
  - Dans l'onglet "langage" choisir "Selectionner un langage"
    Une liste est proposée, si vous avez comme moi "essential of programming language (3rd edition)" c'est le choix à prendre.
  Ensuite, dans la fenêtre du bas, vous avez un "prompt" et pouvez commencer à travailler.
  Dans cette fenêtre, tapez des ordres en Lisp (comme (+ 3 4) ou (load "exo1.l")). Lisp répond... et ainsi de suite.
  Quand tout fonctionne bien, envoyez votre travail par mail: Utilisez, s'il vous plait, votre adresse mail donnée par l'université. Sinon, parfois, ma réponse ne peut pas vous parvenir.
  Mon adresse : jj
  à : ai.univ-paris8.fr
- Travaux et évaluation
  - Premier partiel
  - Projet en binômes
  - Second partiel
  - Oral, si nécessaire
"Let's Play !"
1. Syntaxe
```
(fct par81 par82 ... par_n)
```
2. Premières Fonctions...
```
(define (carre n)
    (* n n))
(define (negatif n)
    (if (< n 0)
       #t
       #f))
```
3. ...récursives
  - Définition
    Est récursif tout ce qui est récursif
  - Principe
    1. Trouver une sortie
    2. Déduire le i-ième cas du (i-1)-ième cas
    3. Vérifier que, entre le (i-1)-ième cas et le i-ième cas, on s'est dirigé vers la sortie.
    Exemple
    s(n) = 0 + 1 + 2 + 3 +...+ (n-1) + n
    1)Pour quelle valeur s(n) est-elle connue ? Pour n=0 c'est 0.
    2)Si je connais s(n-1), comment en déduire s(n) ?
    s(n) = s(n-1) + n
    D'où la fonction
```
(define (s n)
  (if (= n 0)
      0
      (+ (s (- n 1)) n)))
```
  - Fonctions numériques
    Pour toutes les questions ci-dessous, les faire et les faire tourner sur machine.
    1. Somme des carrés des premiers entiers
    2. Somme des cubes des premiers entiers
    3. Somme des puissances quatre des premiers entiers
    4. Valeur Absolue d'un nombre
    5. Racine
      La racine carrée, r, d'un nombre x, est le nombre tel que r * r == x.
      - Plus petit nombre entier supérieur ou égal à la racine
      - Plus grand nombre entier inférieur ou égal à la racine
      - Nombre entier le plus proche de la racine
    6. Multiplication avec uniquement des soustractions et des additions
      On note : a x b = ((a - 1) x b) + b
    7. Division avec uniquement des soustractions et des additions
      On note : a / b = ((a - b) / b) + 1
    8. Puissance n du nombre p.
    9. Pair/Imapir
      Donnez une fonction qui renvoie #t (resp #f) si un nombre est pair (resp. impair).
    10. Reste de la division avec uniquement des soustractions et des additions
      À quoi est égal le reste de a par b si a est plus petit que b ?
      Notez que : reste(a,b) = reste((a - b),b), si a n'est pas plus petit que b.
    11. Plus grand diviseur commun
      On note : pgcd(a,a) = a
      si a > b, pgcd(a,b) = pgcd(a - b, b)
      si a < b, pgcd(a,b) = pgcd(a, b - a)
4. PCR
  "Polymeric Chain Reaction"
  - Définition
    
    f(0)=1
    
    f(1)=1
    
    f(n)= f(n-1) + f(n-2)
  - Premier algorithme
    (define (pcr n) (if (< n 2) 1 (+ (pcr (- n 1)) (pcr (- n 2)))))
5. Récursivité terminale
  - Principe
    Quand l'appel récursif est la dernière opération exécutée (on n'a plus rien à faire après) alors on peut parler de récursivité terminale.
  - Formulation
    Prenons un problème, la somme des n premiers entiers.
    s(n) = 0 + 1 + 2 + 3 + 4 + ... + (n-1) + n
    Soit une fonction de deux variables :
    s2(n,a) = a + 0 + 1 + 2 + 3 + 4 + ... + (n-1) + n
    s2(n,a) = a + s(n)
    Comment écrire une formulation récursive de s2 ?
    s2(0,a) = s(0) + a = a, et
    s2(n,a) = a + s(n)
    s(n) = n + s(n-1)
    donc
    s2(n,a) = a + n + s(n-1)
    or
    s2(n-1,b) = b + s(n-1)
    s(n-1) = s2(n-1,b) - b
    d'où
    s2(n,a) = a + n + s2(n-1,b) - b
    s2(n,a) = a + n - b + s2(n-1,b)
    si 0 = a + n - b (ou encore b = a + n)
    s2(n,a) = 0 + s2(n-1,b)
    s2(n,a) = s2(n-1, a + n)
    Nous pouvons donc écrire la formulation récursive terminale :
    (define (s n) (s2 n 0)) (define (s2 n a) (if (= n 0) a (s2 (- n 1) (+ n a))))
  - Exemples
    (define (f n) (f2 n 1)) (define (f2 n a) (if (< n 2) a (f2 (- n 1) (* n a))))
  - Refaire donc tous les exercices vus jusqu'ici en récursivité terminale !
  - Et Fibonacci ?
  - Division
  - Multiplication
  - pgcd
  - Plus petit multiple commun

"Let's Have Fun"

List Programming

Définition
Une liste est, soit la liste vide, notée (), soit un objet construit à partir d'un objet et d'une liste.
Fonctions élémentaires
- Construire
```
>(cons 3 (cons 2 ()))
= (3 2)
```
- Premier et reste, car, cdr
```
(car (cdr (cons 4 (cons 3 (cons 2 ())))))
3
```
  Mais quand on a un objet, comment savoir si c'est une liste ? Si c'est une liste non vide, c'est une "paire".
```
> (pair? 2)
#f
> (pair? '(5 6))
#t
> (pair? '())
#f
> 
```
  Les cinq fonctions indispensables sont donc :
  - cons
  - car
  - cdr
  - quote
  - pair?

Fonctions sur des listes
Quelques exemples, d'abord...
Le plus grand élément.

(define (plgd l)
  (if (pair? l)
	  (plgrd (car l) (cdr l))
	0))
(define (plgrd cand l)
  (if (pair? l)
	(if (< cand (car l))
		(plgrd (car l) (cdr l))
		(plgrd cand (cdr l)))
	cand))
;> (plgd ll)
;13

Écrivez les fonctions suivantes, concernant les listes :

Est-ce que la liste est vide ?
Est-ce un singleton ?
Est-ce un doubleton, un tripleton, un quadrupleton, un quiqueton...?
Combien cette liste a-t-elle d'éléments ?
Quel est son deuxième élément ?
Quel est son troisième élément ?
Quel est son quatrième élément ?
Quel est son cinquième élément ?
Quel est son n-ième élément ?
Quelle est la somme de ses éléments ?
Quelle est la somme des carrés de ses éléments ?
Quelle est la somme de ses éléments positifs ?
Quelle est le produit de ses éléments non nuls ?
Soit n, une valeur, combien d'éléments de la liste sont plus grands que n ?
Soit n, une valeur, combien d'éléments de la liste sont plus petits que n ?
Soit n, une valeur, y a-t-il autant d'éléments de la liste plus grands que n que d'éléments de la liste plus petits que n ?
La même chose à 1 près. Si à 1 près, la liste contient autant d'éléments plus grands que d'éléments plus petits que n, n est dit "médian".
À propos de deux paramètres n, un nombre, et l, une liste, faire une fonction qui renvoie #t (resp. #f) si n est médian de l (resp. sinon).
Donnez une fonction qui calculle l'élément médian d'une liste.
Pouvez-vous écrire toutes ces fonctions en récursivité terminale ?

Quelques fonctions de plus

Le second plus grand

(define (seco l)
  (if (pair? l)
	  (if (pair? (cdr l))
		  (second (min (car l) (cadr l))
				  (max (car l) (cadr l))
				  (cddr l))
		-1)
	-1))
(define (second un deux l)
  (if (pair? l)
	  (if (< un (car l))
		  (second (car l) un (cdr l))
		(if (< deux (car l))
			(second un (car l) (cdr l))
		  (second un deux (cdr l))))
	deux))
;> (seco ll)
;12

Le troisième plus petit
Le quatrième plus petit
Le cinquième plus petit
enlever, qui enlève un élément de la liste, c'est-à-dire qui fabrique une nouvelle liste sans l'élément paramètre :
```
 > (enlever 5 '(8 9 2 3 5 6 1 7))
'(8 9 2 3 6 1 7)
```
Second plus grand grâce à la fonction "enlever".
Enlever en récursivité terminale.

Enlever toutes les occurences (etlo).

 > (etlo 5 '(8 9 2 5 3 5 6 1 5 7))
'(8 9 2 3 6 1 7)

Enlever toutes les occurences sauf la première (etloslp).

 > (etloslp 5 '(8 9 2 5 3 5 6 1 5 7))
'(8 9 2 5 3 6 1 7))

"simplifie"
Qui fabrique une liste de toutes les valeurs présentes au moins une fois dans la liste (i.e. sans répétition).
"simplifie" sans récursivité terminale.
Nombre d'éléments d'une liste en récursivité terminale.

Fonctions sur les listes
Commençons par écrire une fonction qui permet de concaténer deux listes.

concat
Ce n'est pas complet, si la première liste est vide, c'est la seconde. Sinon, le premier membre de la concaténation est aussi le premier membre de la première liste et la suite n'est qu'une concaténation.

(define (conca l1 l2)
  (if (pair? l1)
	  (cons (car l1)
			(conca (cdr l1) l2))
	l2))
;> ll
;'(8 1 2 8 1 9 2 10 3 4 7 5 6 12 13 -1 7)
;> (conca ll ll)
;'(8 1 2 8 1 9 2 10 3 4 7 5 6 12 13 -1 7 8 1 2 8 1 9 2 10 3 4 7 5 6 12 13 -1 7)

Inversion (merci à Patrick Greussay et Daniel Goossens)

(de (reve l)
        (if (not (pair? l)) l
                 (if (not (pair? (cdr l))) l
                          (cons (car (reve (cdr l)))
                                        (reve (cons (car l) (reve (cdr (reve (cdr l))))))))))

Avec des concaténations
La fonction list fait un cons d'un élément et de la liste vide.

(define (inver l)
  (if (pair? l)
	  (conca (inver (cdr l))
			 (list (car l)))
	'()))
;> ll
;'(8 1 2 8 1 9 2 10 3 4 7 5 6 12 13 -1 7)
;> (inver ll)
;'(7 -1 13 12 6 5 7 4 3 10 2 9 1 8 2 1 8)

En récursivité terminale.
Tri
Il s'agit de ranger tous les éléments d'une liste. La première méthode consiste à fabriquer une liste déjà rangée (la liste vide est très bien rangée). À y inclure un élément, mais bien à sa place, pour que la liste reste rangée. Puis un second, puis un troisième, puis tous les autres.
C'est ce qu'on appelle le tri par insertion.
- La fonction d'insertion
  (define (ins a lt) (if (pair? lt) (if (< a (car lt)) (cons a lt) (cons (car lt) (ins a (cdr lt)))) (list a)))
- La fonction tri ?

Listes de listes
Une liste de listes est formée de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, elles-mêmes formées de listes, ...
Définissons d'abord la propriété "liste" qui répond oui si l'objet-paramètre est une liste. Nous utilisons pour cela le prédicat atom qui répond vrai si son paramètre est un objet élémentaire.

(define (liste? (l)
    (if (unpair l) #f
         (if (equal? l '()) #t
           (liste? (cdr l)))))

Une liste de listes est donc formée de listes. On regarde donc chacun de ses éléments et , si c'est une liste, on le traite comme tel.
Fonction appartient
Voyons d'abord la fonction appartient sur les listes d'éléments :

Étendons maintenant ce principe à des listes de listes. Il suffit de vérifier que, si le car est une sous-liste, x lui appartient.

(define (cher x l)
  (if (unpair l) #f
	(if (pair? (car l))
		(if (cher x (car l))
			#t
		  (cher x (cdr l)))
	  (if (equal? x (car l))
		  #t
		(cher x (cdr l))))))

Ensuite vous pouvez regarder la somme des éléments numériques d'une liste.

(define (unpair l) (not (pair? l))) (define (somlc l) (if (unpair l) 0 (if (pair? (car l)) (+ (somlc (car l)) (somlc (cdr l))) (if (equal? (car l) '()) (somlc (cdr l)) (+ (car l) (somlc (cdr l)))))))
Quelques essais :

(cadar (cddr '(1 (2) (3 4 5 () 6)))) (caddr (cddr '(1 (2) (3) (4 5 () 6)))) (cddr '(1 (2) (3) (4 5 () 6))) (caddr (cddr '(1 (2) (3) (4 5 () 6)))) (caaar '((1 (2) (3 4 5 () 6) (a b c) (d)))) (cadar (cddar '((1 (2) (3 4 5 () 6)) (a b c)))) (caddr (cddar '((1 (2) (3 4 5 () 6)) (a b c)))) (caddr (cddar '((1 (2) (3 4 5 () 6)) (a b c) (d)))) (caddr (cddar '((1 (2) (3 4 5 () 6) (a b c) (d))))) (cddar '((1 (2) (3 4 5 () 6) (a b c) (d))))

Quelques exemples :

Trouver le plus grand élément d'un liste de nombres.
Trouver le second plus petit élément d'une liste de nombres.
Trouver si un mot appartient à une liste de mots.
Trouver combien de fois un mot apparaît dans une liste.
À propos de la liste de définition d'une fonction, compter le nombre d'appels récursifs de cette fonction.

Listes Rangées
Nous nommerons liste rangée une liste qui soit ou bien la liste vide ou bien une liste formée de trois champs :. x est un nombre, l1 et l2 sont des listes rangées et tous les éléments de l1 sont plus petits (ou plus petits et égaux) que x tandis que tous les éléments de l2 sont plus grands que x.
Exemple :

'()
'(8 (5 () ()) (9 () (11 () ())))

sont des listes rangées Chercher un élément dans une telle liste est rapide, il suffit de savoir où chercher.

(define (yest x lr)
  (if (unpair lr) #f
	(if (= x (car lr)) #t
	  (if (< x (car lr))
		  (yest x (cadr lr))
		(yest x (caddr lr))))))

Fabriquer une telle liste à partir d'une liste de nombres n'est pas plus complexe :

(define (unpair l)
  (if (pair? l) #f #t))
(define (petits a l)
  (if (unpair l) '()
	  (if (< a (car l))
		  (petits a (cdr l))
		(cons (car l) (petits a (cdr l))))))
(define (grands a l)
  (if (unpair l) '()
	  (if (> a (car l))
		  (grands a (cdr l))
		(cons (car l) (grands a (cdr l))))))
(define (range4 l)
  (if (< (car l) (cadr l))
	  `(,(car l) () (,(cadr l) () ()))
	`(,(car l) (,(cadr l) () ()) ())))
(define (qsl l)
  (if (unpair l) l
	(if (unpair (cdr l)) `(,(car l) () ())
	  (if (unpair (cddr l))
		  (range4 l)
		`( ,(car l) ,(qsl (petits (car l) (cdr l)))
					,(qsl (grands (car l) (cdr l))))))))

Nous avons vu en cours une version améliorée de ces fonctions.

(define (separe pivot l)
  (separ pivot l '() '()))
(define (separ pivot l ptl gdl)
  (if (unpair l)
	  `(,ptl ,gdl)
	(if (< (car l) pivot)
		(separ pivot (cdr l) (cons (car l) ptl) gdl)
		(separ pivot (cdr l) ptl (cons (car l) gdl)))))
(define (tsl l)
  (if (unpair l) l
	(if (unpair (cdr l)) `(,(car l) () ())
	  (if (unpair (cddr l))
		  (range4 l)
		(let* ((sep (separe (car l) (cdr l)))
			   (pts (tsl (car sep)))
			   (gds (tsl (cadr sep))))
		  `(,(car l) ,pts ,gds))))))

Enfin, il fallait faire une fonction permettant de vérifier si une liste donnée est une liste rangée.

(define (okgd pivot lr)
  (if (unpair lr) #t
	(if (< pivot (car lr)) #f
	  (if (okgd pivot (cadr lr))
		  (okgd pivot (caddr lr))
		#f))))
(define (okpt pivot lr)
  (if (unpair lr) #t
	(if (> pivot (car lr)) #f
	  (if (okpt pivot (cadr lr))
		  (okpt pivot (caddr lr))
		#f))))
		
(define (estlr lr)
  (if (unpair lr)
	  (if (equal? lr '()) #t
		#f)
	(if (okgd (car lr) (cadr lr))
	  (if (okpt (car lr) (caddr lr))
		(if (estlr (cadr lr))
			(estlr (caddr lr))
		  #f)
		#f)
	  #f)))

Vous pouvez maintenant écrire :

une fonction donnant le plus grand élément d'une liste rangée.
une fonction donnant le second plus grand élément d'une liste rangée.
une fonction donnant le plus petit élément d'une liste rangée.
une fonction donnant la sous liste des éléments d'une liste rangée qui sont plus petits qu'une valeur donnée (second paramètre de votre fonction).
une fonction qui prend en entrée une liste rangée et qui renvoie la liste triée de tous les éléments de l'argument.
une fonction qui trouve l'élément médian d'une liste rangée.

Associations
Les listes d'association sont des listes de couples (a . b) où a est un "identifiant" et b est la valeur associée. Par exemple:
((couleur . rouge) (taille . grande) (forme . cube))
On peut utiliser la fonction assoc qui permet, pour un certain identifiant de déterminer la valeur associée. Prenons ici l'exemple d'une liste al qui donne pour tous les identifiants la valeur de leur carré:
;? al ;=((0 . 0) (1 . 1) (2 . 4) (3 . 9) (4 . 16) (5 . 25) (6 . 36)) ;? (assoc 4 al) ;= (4 . 16) ;? (car (assoc 4 al)) ;= 4 ;? (cdr (assoc 4 al)) ;= 16
Il est possible d'associer rapidement une liste comme al.
NB Reste à écrire la fonction "pairlis" qui fabrique une liste à partir de deux listes, par association des de "car" puis association de deux "cadr" etc.
Un exemple d'utilisation du "cond".
(define (lecond n) (cond ((= n 0) 1) ((= n 1) 1) (* (+ (lecond (- n 1)) (lecond (- n 2))))))

Dernière mise à jour de ce document :

05/01/12

Méthodologie de la Programmation Fonctionnelle Premier semestre 2011-2012

Généralités

"Let's Play !"

"Let's Have Fun"

Méthodologie de la Programmation Fonctionnelle
Premier semestre 2011-2012