Scheme

RÉCURSION SUR LES LISTES

QUELQUES RAPPELS

(CAR '(1 2)) ---> 1
(CDR '(1 2)) ---> (2)
(CONS 1 '(2)) ---> (1 2)

(CONS '(1 2) '(3))
---> ((1 2) 3)

LES "TYPES" SCHEME SONT:

ATOMES

CONSTANTES

NOMBRES: 1, 2, ...

BOOLÉENS: #T, #F

CHAÎNES DE CARACTÈRES:
"Bonjour toto"

SYMBOLES
(VARIABLES)

LISTES

LISTES = PRÉSENCE D'AU MOINS
UN DOUBLET
ATOME = PAS DE DOUBLET

==> ( ) EST . . . UN ATOME !

PRÉDICAT FONDAMENTAL:
(NULL? <ARG>) --> TESTE SI <ARG> EST ( )

FONCTIONS USUELLES:
(PAIR? <ARG>) --> TESTE SI <ARG> EST UNE LISTE (AU MOINS UN DOUBLET)
(NUMBER? <ARG>) --> TESTE SI <ARG> EST UNE CONSTANTE DE TYPE NOMBRE
(EQUAL? <ARG1> <ARG2>)
--> TESTE SI <ARG1> ET <ARG2> SONT DEUX ÉLÉMENTS SCHEME IDENTIQUES

FONCTIONS SUR LES LISTES:
(LENGTH L) --> NBRE D'ÉLÉMENTS
(REVERSE L) --> INVERSE L
(APPEND L1 L2) --> "CONCATÈNE" L1 ET L2
(= MET BOUT À BOUT)

(CONS '(1 2) '(3 4))
--> ((1 2) 3 4)

(LIST '(1 2) '(3 4))
--> ((1 2) (3 4))

(APPEND '(1 2) '(3 4))
--> (1 2 3 4)

FABRIQUER UNE LISTE RÉCURSIVEMENT

FABRIQUER LA LISTE DES ENTIERS
DE N A 1

N = 5
--> (5 4 3 2 1)

  (5 4 3 2 1)
  = (CONS 5 '(4 3 2 1))

  N = 0 --> ()


EN SCHEME, CELA S'ÉCRIT :


(DEFINE (IOTA N)

 (COND ((= N 0) ())   ; TEST D'ARRÊT

       (ELSE (CONS N 

                   (IOTA (- N 1))))))

                 ; APPEL RÉCURSIF

Exemple iota (programme : iota.drs)

PARCOURS RÉCURSIFS

CALCULER LE NOMBRE D'ÉLÉMENTS
D'UNE LISTE

  (OUR-LENGTH L)
  = (+ 1 (OUR-LENGTH (CDR L)))

  (OUR-LENGTH    ( )) --> 0
             ==> (NULL? L) EST VRAI


(DEFINE (OUR-LENGTH L)

 (COND ((NULL? L) 0)   ; TEST D'ARRÊT

       (ELSE (+ 1

                (OUR-LENGTH (CDR L))))))

QUAND ON PARCOURT UNE LISTE L,
LE TEST D'ARRET EST (NULL? L)

"CONCATÉNER" DEUX LISTES:

(OUR-APPEND L1 L2)
= "CONCATÉNER" DEUX LISTES
--> ON PARCOURT LA PREMIERE LISTE L1

  (OUR-APPEND '(1 2 3) '(4 5 6))
  = (CONS 1 (OUR-APPEND '(2 3) '(4 5 6)))

  (OUR-APPEND ( ) '(4 5 6))
  --> (4 5 6)



--> L1
--> (CDR L1)


(DEFINE (OUR-APPEND L1  L2)

 (COND ((NULL? L1) L2)   ; TEST D'ARRÊT

       (ELSE (CONS (CAR L1)

                   (OUR-APPEND (CDR L1) L2)))))

POUR FAIRE UN TRAITEMENT
RÉCURSIF D'UNE LISTE L:

SI (NULL? L) EST VRAI, ALORS STOP

SINON FAIRE UN TRAITEMENT SUR (CAR L), AVEC UN "APPEL RÉCURSIF" SUR (CDR L)

Scheme