Introduction à la Programmation Fonctionnelle (PF1)
Le cours 9
Voici le cours 9 ainsi que le TP9.
Dans le TP8, l'exercice 5 demandait un peu de rigueur. Il s'agissait de calculer xn par dichotomie [division systématique de l'exposant par 2] mais aussi de manière itérative ! Si l'on ne sent pas immédiatement [gasp] la solution, il faut essayer de généraliser le problème. La version récursive enveloppée [cours 5 page 6] donnait :
xn = (x2)n/2 si n est pair
xn = x * (x2)n/2 si n est impair
La seconde ligne montre qu'une généralisation du calcul de xn pourrait donc être f(x,n,a)=axn. Si la fonction f est programmable, on pourra en déduire xn puisque xn = f(x,n,1). Tâchons donc de programmer récursivement f :
f(x,0,a) = a
n pair --> f(x,n,a) = a xn = a (x2)n/2 = f(x2,n/2,a)
n impair --> f(x,n,a) = a xn = a x (x2)(n-1)/2 = a x (x2)n/2 = f(x2,n/2,ax)
où n/2 signifie la division entière de n par 2 [au sens de quotient]. Observons tout de suite que f est itérative, donc se nommera plus joliment iter et que a étant un accumulateur [c'est lui qui est le résultat final d'après la première ligne] se nommera acc :
(define ($expt x n) ; n entier naturel, dichotomie itérative, O(log n) opérations
(local [(define (iter x n acc)
(cond ((= n 0) acc)
((even? n) (iter (sqr x) (quotient n 2) acc))
(else (iter (sqr x) (quotient n 2) (* acc x)))))]
(iter x n 1)))
L'exercice à maîtriser à fond est celui de la résolution approchée par la méthode de Newton d'une équation f(x)=0. Vous pouvez lire de belles explications dans le livre d'Abelson & Sussman Structure et Interprétation des Programmes Informatiques [à la BU !] cité dans ma page de bibliographie. Mais le Scheme qu'ils utilisent [MIT Scheme] n'est pas exactement le même que Racket, il faudra donc plus conserver les idées que le code proprement dit, qu'il faudra parfois adapter. Par exemple, ils n'utilisent pas local mais une variante let enseignée uniquement dans l'option PF2. Voici une solution en Racket :
(define (une-racine f a0 h) ; a0 = approximation initiale, h = precision
(local [(define (Df x)
(/ (- (f (+ x h)) (f x)) h)) ; cf TP2, exo 8
(define (assez-bonne? a)
(< (abs (f a)) h))
(define (ameliore a)
(- a (/ (f a) (Df a)))) ; Newton...
(define (iter a)
(if (assez-bonne? a)
a
(iter (ameliore a))))]
(iter a0)))
> (une-racine (lambda (x) (- (* x x x) 2)) #i1 #i0.0001) ; racine cubique de 2
1.2599338173836314
> (une-racine sin #i3 #i0.0001) ; calcul de pi
3.1415926532544156
> (une-racine (lambda (x) (- x (cos x))) #i1 #i0.0001) ; solution de x = cos(x)
0.7391131535431725
Je vous conseille vivement de faire l'exercice 6.8.11 du livre de cours PCPS...
Voici une ancienne solution d'étudiant améliorant la fonction (miro n) sur l'art numérique. Il s'agissait de construire itérativement une image contenant n rectangles aléatoires :
(define (miro n)
(local [(define SCENE (rectangle 600 600 'solid "black"))
(define (randcolor) (make-color (random 256) (random 256) (random 256)))
(define (iter n IMG) ; n : nbr de carrés restants à poser, IMG est l'image en construction
(if (= n 0)
(place-image (text "V. Rougier" 32 "white") 500 570 IMG)
(iter (- n 1) (place-image (rectangle (random 70) (random 80)
(if (<= (random 3) 1) 'solid 'outline)
(randcolor))
(+ 100 (random 400)) (+ 100 (random 400))
IMG))))]
(iter n SCENE)))
Et une solution possible du dernier exercice du TP8, sur la méthode de Monte-Carlo pour calculer une valeur approchée de pi. Il y a deux manières de calculer la probabilité qu'une fléchette lancée au hasard dans un carré de côté C tombe dans le disque inscrit dans ce carré. Si N est le nombre de lancers et S le nombre de succès, la probabilité est égale à S/N. Mais elle est aussi égale au rapport des aires, soit (pi*C2/4)/C2, c'est à dire pi/4. D'où pi = 4S/N. En notant que ce résultat ne dépend pas de C [c'était prévisible], on peut faire C=2 pour simplifier, d'où un rayon de 1.
(define (flechettes N) ; retourne une valeur approchée de pi
(local [(define (iter nb S) ; il reste nb expériences, S accumule le nombre de succès
(if (= nb 0)
(exact->inexact (/ (* 4 S) N))
(local [(define x (* 2 (random))) ; (random) tombe dans ]0,1[
(define y (* 2 (random)))]
(if (< (+ (sqr (- x 1)) (sqr (- y 1))) 1) ; point intérieur ?
(iter (- nb 1) (+ S 1))
(iter (- nb 1) S)))))]
(iter N 0)))
> (flechettes 2000)
#i3.132
Et tant que nous y sommes, pour une préparation à l'examen final, le même calcul via une animation. Le Monde mathématique est une structure (img,nb,s) à trois champs : l'image img en construction [puisqu'on veut garder les traces des anciennes fléchettes], le nombre nb d'expériences restantes, et le nombre s de succès :
; Je definis le Monde a l'exterieur car je vais me servir de cette structure
; en-dehors de la fonction monte-carlo, pour en exploiter les resultats.
(define-struct monde (img nb s)) ; le Monde est un triplet contenant l'image
(define (monte-carlo n) ; version non MVC : la Vue est dans le Modele
(local [(define SIZE 400) ; dimension du monde
(define R (/ SIZE 2)) ; rayon du cercle tangent aux bords de la scene
(define R^2 (sqr R))
(define FOND (place-image (circle R 'outline "blue") R R (rectangle SIZE SIZE 'outline "white")))
; Le Monde est un triplet (img nb s) signifiant : on a deja tire nb points
; qui sont dans l'image img, et dont s sont dans le cercle.
; Le define-struct est fait en-dehors de cette fonction car on s'en sert apres...
(define INIT (make-monde FOND 0 0))
(define (final? m) ; Monde --> Boolean
(= n (monde-nb m)))
(define (suivant m) ; Monde --> Monde
(local [(define x (random SIZE))
(define y (random SIZE))
(define succes? (< (+ (sqr (- x R)) (sqr (- y R))) R^2))] ; dans le cercle ?
(make-monde (place-image (circle 2 'solid (if succes? "red" "black"))
x y (monde-img m))
(+ (monde-nb m) 1)
(if succes? (+ (monde-s m) 1) (monde-s m)))))
(define (dessiner m) ; Monde --> Scene
(monde-img m))]
(big-bang INIT
(on-draw dessiner)
(on-tick suivant 1/100)
(stop-when final?))))
(local [(define N 200) (define res (monte-carlo N))]
(printf "Valeur approchee de pi avec ~a points : ~a (bof...)\n"
N (/ (* #i4.0 (monde-s res)) N)))
