Jean-Jacques BOURDIN

Université Paris 8
Labo IA, Dépt. Informatique
2, rue de la Liberté
93526 Saint-Denis Cedex
FRANCE

Programmation Fonctionnelle
Premier semestre 2019-2020

Le dernier partiel écrit aura lieu le 2/9/2020 en amphi B1. Entre 11 et 13h.

Tout étudiant qui n'a pas encore rendu son propre projet doit prendre contact au plus vite avec l'enseignant sauf à accepter d'être compté absent.

À partir du 19 août, 14h, de nouvelles séances de révision seront données sur le serveur Discord (ou sur un BBB). Les liens seront donnés sur cette page.

Dans tous les cas je reste disponible par mail pour toute question.

Une note va donc être affichée sur votre ENT. Elle tient compte de votre second partiel pour ceux qui l'ont passé ou simplement du premier.

Dans tous les cas, il sera possible de passer un "second partiel" à la fin des cours de second semestre, à une date que nous fixerons via un sondage en ligne.

Puisqu'il ne sera pas possible de faire un partiel en mai, ni juin, je vous propose deux modalités à choisir :

un partiel écrit tout début septembre (si nous avons le droit d'accueillir les étudiants...).
des oraux comme on fait des révisions, où nous avançons sur un exercice et l'un passe, partage son écran et répond à des questions. Puis le suivant passe, partage son écran et répond à des questions.
Dites-moi ce que vous en pensez.

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
- Langage
  Lisp
  VLisp
  xbvl
  Scheme
- Méthode
  1. Dans l'onglet application, trouvez DrRacket, cliquez et une fenêtre s'ouvre.
  2. Sous xterm taper
    racket &
    une fenêtre Lisp s'ouvre.
Il faut d'abord choisir un langage.
Dans la fenêtre du haut tapez "#lang racket" si ce n'est pas déjà affiché et ne faites plus rien dans cette fenêtre.

Ensuite, dans la fenêtre du bas, vous avez un "prompt" (>) et pouvez commencer à travailler.

Dans cette fenêtre, tapez des ordres en Scheme (on dira parfois Lisp dont scheme est un dialecte) (comme (+ 3 4) ou (load "exo1.l")). Lisp répond... et ainsi de suite.

Pour écrire votre programme, vous devriez utiliser emacs, qui va vous servir pour beaucoup d'autres choses.

Vous vous contentez de taper, dans un terminal, la commande
```
emacs exo1.l &
```
Vous pouvez trouver des raccourcis claviers pour emacs sur ma page : ICI .
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 vous parvient pas.
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))
(define (plpt2 a b)
    (if (< a b)
        a
        b)))
```
3. ...récursives
  - Définition
    Est récursif tout ce qui est récursif
  - Principe
    1. Trouver une sortie
    2. Trouver une règle générale permettant de passer d'un cas i à un cas j.
    3. Vérifier que, entre le cas i et le cas j, 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. produit des naturels jusqu'à n,
    5. produit des carrés des entiers naturels jusqu'à la valeur n,
    6. puissance p du nombre n,
    7. Addition par +1 et -1.
      Nous supposons ne pas pouvoir faire d'addition différente de +1 ou -1. Comment générer l'addition de deux entiers ?
      
      Il faut trouver la borner et voir quelle règle générale permet de l'atteindre.
    8. Soustraction par +1 et -1.
    9. Multiplication avec uniquement des soustractions et des additions
      On note : a x b = ((a - 1) x b) + b
    10. Division avec uniquement des soustractions et des additions
      On note : a / b = ((a - b) / b) + 1
    11. Puissance n du nombre p.
    12. Pair/Impair
      Donnez une fonction qui renvoie #t (resp #f) si un nombre est pair (resp. impair).
    13. 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.
    14. 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)
    15. 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
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 (srt n) (srt_aux n 0)) (define (srt_aux n a) (if (= n 0) a (srt_aux (- 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 c'est fatiguant d'écrire cette série de cons. Nous les remplaçons par une apostrophe :
```
(car (cdr '(4 3 2))
```
  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...

(define (premierl l)
  (if (pair? l)
      (car l)
     '()))
; Combien cette liste a-t-elle d'éléments ?
(define (nbele l)
  (if (pair? l)
     (+ 1 (nbele (cdr l)))
     0))
; Quelle est la somme de ses éléments ?
(define (soml l)
  (if (pair? l)
     (+ (car l) (soml (cdr l)))
     0))

(define (estvide l)
   (if (pair? l)
     #f
     #t))

Écrivez les fonctions suivantes, concernant les listes :

Est-ce un singleton ?
Est-ce un doubleton, un tripleton, un quadrupleton, un quiqueton...?
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 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 calcule l'élément médian d'une liste.
Pouvez-vous écrire toutes ces fonctions en récursivité terminale ?

Manipulation des listes
1. Concaténation
  Concaténer deux listes c'est fabriquer une liste formée de tous les éléments de ces deux listes dans l'ordre.
  (concat '(7 3 9) '(A c b)) -> '(7 3 9 A c b)
  (define (concat l1 l2) (if (estvide l1) l2 (cons (car l1) (concat (cdr l1) l2))))
2. À faire :
  - concaténer en récursivité terminale
  - renvoyer le miroir de la liste
3. Donnez une fonction d'une liste qui renvoie son dernier élément.
4. Donnez une fonction d'une liste l qui renvoie une liste formée de la valeur absolue de chacun des éléments de l.
5. Est-ce que m appartient à la liste l?
  Il suffit de regarder le premier élément, s'il existe. Si c'est lui, voilà, on a la réponse. Sinon, il faut savoir si m appartient au reste de la liste l : (cdr l).
  (define (appartient m l) (if (pair? l) (if (= m (car l)) #t (appartient m (cdr l))) #f))
  - Belongs
    "One element belongs to a list if it is its first element or if it belongs to the rest of the list. If there is no list, it doesn't belongs!"
    (define (belongs x l) (if (not (pair? l)) #f (if (= x (car l)) #t (belongs x (cdr l)))))
    Le plus grand de la liste
    (define (plgd2 a b) (if (< a b) b a)) (define (plgdl l) (plgdl_aux (cdr l) (car l))) (define (plgdl_aux l cand) (if (pair? l) (plgdl_aux (cdr l) (plgd2 cand (car l))) cand))
  - 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).

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

concat
Ce n'est pas compliqué, 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))))))))))

Vous devez maintenant trouver le moyen de faire le même calcul avec des concaténations et, surtout, en récursivité terminale.

Tris
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)))

Il ne reste plus qu'à insérer tous les éléments un à un dans une liste triée.

Le tri rapide

Principe : on prend un élément de la liste, nommé le pivot, par exemple le premier. On fait deux sous-listes avec ceux qui sont plus grands, d'une part, plus petits de l'autre, que le pivot. Il ne reste plus qu'à trier ces deux listes indépendamment et à recoller les trois morceaux. Vous le faites au plus vite.

let et letrec
On peut "affecter" une variable "locale" avec let :

(define (foct n m)
  (if (= n 0) m
    (let ((a (- n 1))
	  (b (+ m 1)))
      (foct a b))))

Ici, a n'est pas utilisable pour calculer b. Elle le serait avec letrec.

(define (fff) (load "Prog/Lisp/quic.l"))

(define (estvide l)
  (if (pair? l) #f #t))
(define (concat l1 l2)
  (if (estvide l1) l2
    (cons (car l1) (concat (cdr l1) l2))))
(define (range2 l)
  (if (< (car (cdr l)) (car l))
      (cons (cadr l) (cons (car l) '()))
    l))
(define (qs l)
  (if (estvide l) l
    (if (estvide (cdr l)) l
      (if (estvide (cddr l)) (range2 l)
	(qs_aux (car l) (separe (car l) (cdr l) '() '()))))))
(define (qs_aux pivot deuxlistes)
  (concat (qs (car deuxlistes))
	  (cons pivot (cadr deuxlistes))))
(define (separe pivot l lpt lgd)
  (if (estvide l)
      (cons lpt (cons lgd '()))
    (if (< (car l) pivot)
	(separe pivot (cdr l) (cons (car l) lpt) lgd)
      (separe pivot (cdr l) lpt (cons (car l) lgd)))))

Vos méthodes faisant parcourir deux fois la liste, pour en prendre les petits éléments d'une part, les grands d'autre part, d'autres solutions ont été données en cours. En voici une qui utlise le let.

(define (qs3 l)
  (if (unpair l) '()
	(if (unpair (cdr l)) l
	  (if (unpair (cddr l)) (range2 l)
		(let ((deuxl (separe (car l) (cdr l))))
		  (let ((petits (qs3 (car deuxl)))
				(grands (qs3 (cdr deuxl))))
			(concat petits (cons (car l) grands))))))))
;> (qs3 '(9 8 2 7 1 10 12 6 5 23 31 14 15 -1 6 5))
.'(-1 1 2 5 5 6 6 7 8 9 10 12 14 15 23 31)

On peut remplacer les deux "let" consécutifs par un "letrec" et dans ce cas les deux associations (petits et grands) tiendront compte de l'association précédente.

(define (qs3 l)
  (if (unpair l) '()
	(if (unpair (cdr l)) l
	  (if (unpair (cddr l)) (range2 l)
		(letrec ((deuxl (separe (car l) (cdr l)))
		         (petits (qs3 (car deuxl)))
				 (grands (qs3 (cdr deuxl))))
			  (concat petits (cons (car l) grands)))))))
;> (qs3 '(9 8 2 7 1 10 12 6 5 23 31 14 15 -1 6 5))
.'(-1 1 2 5 5 6 6 7 8 9 10 12 14 15 23 31)

Backquote

La quote permet de ne pas évaluer.

La backquote permet de ne pas évaluer sauf si on trouve une virgule.

`(1 2 3 ,(+ 4 5))
  vaut
  '(1 2 3 9)

Et avec un @ on passe directement une liste.

(define (concat2 la lb)
  `(,@la ,@lb))

Facile, non ?

Quelques suppléments
cond et cas
On peut remplacer les séries de "if" par des "cond" ou des "case".

(define (fibcond n)
  (cond ((= n 0) 1)
	((= n 1) 1)
	(else (+ (fibcond (- n 1))
		 (fibcond (- n 2))))))
(define (fibcase n)
  (case n
	((0) 1)
	((1) 1)
	(else (+ (fibcase (- n 1))
		 (fibcase (- n 2))))))
;> (fibcase 5)
;8
;> (fibcase 6)
;13
;> (fibcond 5)
;8
;> (fibcond 6)
;13

funcall, map et les leurs
Il peut être intéressant de faire une fonction qui permet d'appliquer automatiquement le même traitement à tous les éléments d'une liste.

(define (carre n)
  (* n n))
(define (funcall fct liste)
  (if (unpair liste) '()
	(cons (fct (car liste))
              (funcall fct (cdr liste)))))
;> (funcall carre '(7 8 1 2 9 3 8 11 0))
;'(49 64 1 4 81 9 64 121 0)

Il vous reste à faire la fonction qui prend un premier paramètre, la fonction à appliquer, par exemple carre, et un deuxième paramètre, la liste et qui renvoie la somme des carrés de tous les éléments de la liste. Mais avec comme paramètre cube, c'est la somme des cubes...

Mais, et si on change l'opération ? Si on passe à la multiplication par exemple ? Il faut dans ce cas appliquer ce nouveau paramètre. Écrivez la fonction muchfun :
;> (muchfun + carre '( 1 2 3 0)) ;= 14

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 normales. Il suffit de vérifier que, si le car est une sous-liste, x lui appartient.

;
(define (appartient x l)
  (if (unpair l)
      #f
      (if (pair? (car l))
          (if (appartient x (car l))
             #t
             (appartient x (cdr l)))
          (if (equal? x (car l))
              #t
              (appartient x (cdr l))))))
;> (appartient 5 '((1 (2) (3 4 5 () 6)) (a b c)))
;#t
;> (appartient 'a '((1 (2) (3 4 5 () 6)) (a b c)))
;#t
;> (appartient 'b '((1 (2) (3 4 5 () 6)) (a b c)))
;#t
;> (appartient 'e '((1 (2) (3 4 5 () 6)) (a b c)))
;#f

Notons que "equal?" sert à tester l'egalite quand il ne s'agit pas de nombres.

Étendons maintenant ce principe à des listes de listes.

(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 regardons 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.

Images en Lisp

(define (ee) (load "Prog/Lisp/gra.l"))
(require graphics/graphics)
;La fonction suivante n est pas utlisee
(define (dessine_sur port)
  ((draw-line port) (make-posn 30 30) (make-posn 100 100))
  ((draw-line port) (make-posn 100 100) (make-posn 170 30))
  ((draw-ellipse port) (make-posn 50 50) 100 100)
  ((draw-ellipse port) (make-posn 100 90) 100 200 "red")
  ((draw-solid-ellipse port) (make-posn 50 100) 30 20 "cyan")
)
(define (findes port)
  (close-viewport port)
; viewport disappears
  (close-graphics)
; again, nothing appears to happen, but
; unclosed viewports (if any) would disappear
)
(define (dessine_vis port)
; make-posn fabrique une position a partir des deux coordonnees
  ((draw-polygon port) (list (make-posn -120 -120)(make-posn 120 -120)(make-posn 120 120)(make-posn -120 120)) (make-posn 140 130))
  ((draw-ellipse port) (make-posn 50 30) 150 180)
  ((draw-ellipse port) (make-posn 70 90) 45 20 "magenta")
  ((draw-solid-ellipse port) (make-posn 80 90) 15 15 "blue")
  ((draw-ellipse port) (make-posn 130 90) 45 20 "magenta")
  ((draw-solid-ellipse port) (make-posn 140 90) 15 15 "blue")
  ((draw-line port) (make-posn 90 160) (make-posn 150 160) "red")
  ((draw-line port) (make-posn 120 100) (make-posn 120 150))
)
(define (face)
  (open-graphics)
; nothing appears to happen, but the library is initialized...
  (define viz (open-viewport "visage" 300 300))
  (dessine_vis viz)
; attendre un peu pour voir l image
  (sleep 20)
  (findes viz)
)

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 (estvide 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 ou définir la fonction asso qui permettent, 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é:

(define (asso n la)
  (if (estvide la) la
    (if (= (caar la) n) (cadar la)
      (asso n (cdr la)))))

;? 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.
Voici donc les deux fonctions vues en cours permettant de créer de telles listes :


(define (creerla l1 l2)
  (if (estvide l1) l1
    (if (estvide l2) l2
      (cons `(,(car l1) ,(car l2))
	    (creerla (cdr l1) (cdr l2))))))
(define (creerlaf l fct)
  (if (estvide l) l
      (cons `(,(car l) ,(fct (car l)))
	    (creerlaf (cdr l) fct))))

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))))))

Métaprogrammation

Principe
Écrire une fonction qui écrit une fonction, ou des fonctions, voilà la métaprogrammation.

Essayons
D'abord, voici un programme qui se propose de fabriquer la dérivée d'une fonction (attention, dans un premier temps la fonction à dériver est donnée sous la forme d'une liste).

; Une fonction classique pour commencer
(define (unpair l)
  (not (pair? l)))

; Deux exemples pour voir comment seront présentées les "fonctions-listes"

(define deffct1 '(define (fct1 x) (+ x (* x x))))
(eval deffct1)

(define deffct2 '(define (fct2 x) (* (+ x 5) (+ x 5))))
(eval deffct2)

On voit que les fonctions sur lesquelles on va travailler sont simplement présentées comme des listes. Il faut les évaluer pour pouvoir s'en servir.

;> (eval deffct1)
;> (fct1 5)
;30

Maintenant reprenons deux fonctions classiques :

(define (fact n) (if (= n 0) 1 (* n (fact (- n 2)))))
(define (som n)  (if (= n 0) 0 (+ n (som (- n 2)))))

Ces deux fonctions se ressemblent tellement qu'il doit être possible de trouver une fonction qui les génère automatiquement.


(define (faitfct nom oper neutre para)
  (list 'define (list nom para)
	`(if (= ,para 0) ,neutre
	,(list oper para (list nom `(- ,para 1))))))
;> (faitfct 'fact '* 1 'n)
;'(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))
;> (eval (faitfct 'fact '* 1 'n))
;> (fact 5)
;120
;>

Adaptez maintenant la fonction faitfct pour qu'elle prenne un paramètre de plus, la fonction à appliquer à n si on veut, par exemple, la somme du carré des premiers entiers, ou de leur cube...

Hanoi, les tours

Voici le programme vu le mercredi 27/11.

(define (hh) (load "Prog/Lisp/hanoi.l"))
(define (affiche n dep arr)
  (printf "~a de ~a a ~a\n" n dep arr))
;; plus joli comme affichage, non ?
(define (exaffiche n dep arr)
  (print n)
  (print " ")
  (print dep)
  (write " a ")
  (writeln arr))
(define (hanoi n dep arr tmp)
  (if (= n 1) (affiche 1 dep arr)
    (begin
     (hanoi (- n 1) dep tmp arr)
     (affiche n dep arr)
     (hanoi (- n 1) tmp arr dep))))
;; > (hanoi 5 'triangle 'carre 'rond)
;; 1 de triangle a carre
;; 2 de triangle a rond
;; 1 de carre a rond
;; 3 de triangle a carre
;; 1 de rond a triangle
;; 2 de rond a carre
;; 1 de triangle a carre
;; 4 de triangle a rond
;; 1 de carre a rond
;; 2 de carre a triangle
;; 1 de rond a triangle
;; 3 de carre a rond
;; 1 de triangle a carre
;; 2 de triangle a rond
;; 1 de carre a rond
;; 5 de triangle a carre
;; 1 de rond a triangle
;; 2 de rond a carre
;; 1 de triangle a carre
;; 3 de rond a triangle
;; 1 de carre a rond
;; 2 de carre a triangle
;; 1 de rond a triangle
;; 4 de rond a carre
;; 1 de triangle a carre
;; 2 de triangle a rond
;; 1 de carre a rond
;; 3 de triangle a carre
;; 1 de rond a triangle
;; 2 de rond a carre
;; 1 de triangle a carre

Fractales

Voici le programme vu le mercredi 27/11, écrit par M. Jouandeau.

(define (frfr) (load "Prog/Lisp/sierp.l"))
(require 2htdp/image)
(define (sierpinski0 d) (triangle d 'solid 'black))
(define (sierpinski n d)
  (if(= n 0) (sierpinski0 d)
     (above (sierpinski (- n 1) d)
       (beside (sierpinski (- n 1) d) (sierpinski (- n 1) d))
    )))
(define (tryit)
  (sierpinski 5 10))
(define (essai)
  (beside/align "bottom"
		(sierpinski 0 20) (sierpinski 1 20)
		(sierpinski 2 20) (sierpinski 3 20) (sierpinski 4 20))
  (beside (sierpinski 3 40) (sierpinski 4 20) (sierpinski 5 10)))

À vous maintenant de faire tout ce qu'on peut imaginer comme courbes et dessins de fractales.

Divers

Lambda

(define A 6) ; vous connaissez
(define (plgd2 a b)
  (if (< a b) b a))
(define (gdpl a b)
  ((lambda (x y) (if (< x y) y x)) a b))
(define (f x y) (if (= x y) x
		  (if (< x y)
		      (f x (- y x))
		    (f (- x y) y))))
(define (g x y)
  ((lambda (x y) (if (= x y) x
		  (if (< x y)
		      (g x (- y x))
		    (g (- x y) y)))) x y))

Lecture
On a parfois besoin de lire des valeurs fixées par l'utilisateur. La fonction read fait ce travail.

(define (fib)
  (fibrt (read)))
(define (fibrt n)
  (fibrtaux n 2 1 1))
(define (fibrtaux n i pred ante)
  (if (< n i) pred
    (fibrtaux n (+ i 1) (+ pred ante) pred)))

Dernière mise à jour de ce document :

23/7/2020

Programmation Fonctionnelle Premier semestre 2019-2020

Généralités