Scheme

RÉCURSION SUR LES LISTES

FONCTIONS USUELLES SUR LES LISTES

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

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

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

CAR, CDR, CONS, NULL? SONT LES QUATRE FONCTIONS INDISPENSABLES POUR LES RÉCURSIONS SUR DES LISTES

LES "TYPES" SCHEME SONT:

ATOMES

CONSTANTES

NOMBRES: 1, 2, ...

BOOLÉENS: #T, #F

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

SYMBOLES
(VARIABLES)

   LISTES

UN "DOUBLET" :
STRUCTURE DE LA MÉMOIRE INTERNE DE L'ORDINATEUR
--> PERMET D'"ATTACHER" LES ÉLÉMENTS DANS UNE LISTE (SORTE DE COLLE...)

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

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

PRÉDICATS USUELS:
(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

REMARQUE:

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

(APPEND L1 L2) --> "CONCATÈNE" L1 ET L2
(= MET BOUT À BOUT)

Exemple null?

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)

PARCOURIR UNE LISTE: SÉQUENCES SONORES

SÉQUENCE SONORE =
LISTE D'"ÉVÉNEMENTS" MIDI
(<NOTE> <DATE> <DURÉE> <VÉLOCITÉ> <CANAL>)

EXEMPLE: "AUCLAIRDELALUNE" =
'((60 0 450 120 0) (60 500 450 120 0) (60 1000 450 120 0) (62 1500 450 120 0) (64 2000 950 120 0) (62 3000 950 120 0))

JOUER-MIDI
= JOUE UN EVENEMENT (FONCTION MZSHARE)
PROBLÈME: FAIRE LA FONCTION JOUER-LISTE-AT ??


(DEFINE (JOUER-LISTE-AT D L)

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

        (ELSE (JOUER-MIDI (DATE-EVT (CAR L) D))

              (JOUER-LISTE-MIDI D (CDR L)))))

                ;APPEL RÉCURSIF



(DEFINE (DATE-EVT E D)

  (LIST (CAR E) 

        (+ D (CADR E)) 

        (CADDR E) 

        (CADDDR E) 

        (CAR (CDDDDR E)))

PARCOURIR UNE LISTE:

APPEL RÉCURSIF:
L REMPACÉ PAR (CDR L)

TEST D'ARRÊT:
(NULL? L)

IMPROVISER UNE LISTE D'ÉVÉNEMENTS
(RANDOM N)
--> NBRE AU HASARD ENTRE 0 ET N-1



(DEFINE (IOTA-RANDOM N)

  (COND ((= N 0) ())

        (ELSE (CONS (LIST (+ (RANDOM 80) 40) 

                          (* N 100) 100 120 0)

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


(DEFINE (IMPRO N) 

  (JOUER-LISTE-AT (MIDI-GET-TIME) 

                  (REVERSE (IOTA-RANDOM N))))

Exemple jouerliste (programme : jouerliste.drs)

AUTRES 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