Paare     Listen
car cdr length append reverse
null? pair? list?
set-car! set-cdr! append! reverse!

Paare und Listen


 

Paare

Die "eigentlich wichtige" Datenstruktur von scheme sind die Listen, nicht die Paare. Will man wirklich mit Paaren arbeiten, dann will man zwei Daten zu einem isolierten Element Paar verknüpfen. Für Scheme typisch ist, dass der Typ der beiden verknüpften Daten völlig belanglos ist, da in dem Datenobjekt Paar sowieso nicht die Inhalte gespeichert werden, sondern nur Zeiger auf diese. Das kann man grafisch folgendermaßen veranschaulichen:

Paar

Erzeugt wird ein solches Paar durch die Funktion cons.
Funktionen für den lesenden Zugriff sind car und cdr.
Ein Beispiel:

  (define mein-Paar (cons 3 5))
  mein-Paar                   => (3 . 5)
  (car mein-Paar)             => 3
  (cdr mein-Paar)             => 5

Auch ein schreibender Zugriff ist möglich und zwar mit set-car! und set-cdr! :

  (set-car! mein-Paar 'mein)
  (set-cdr! mein-Paar 'Paar)
  mein-Paar                   => (mein . paar)

 


 

Listen

Eigentlich benötigt man diese Paare jedoch für Listen. In Listen wird der zweite Zeiger nicht verwendet, um auf einen zweiten Datenwert zu zeigen, sondern um auf ein weiteres Listenelement zu zeigen. Ein grafische Darstellung sieht dann so aus:

Liste mit zwei Elementen

Ein Beispiel:

  
  (define meine-Liste (cons 3 (cons 5 '())))
  meine-Liste                 => (3 5)
  (car meine-Liste)           => 3
  (cdr meine-Liste)           => (5)
  (cadr meine-Liste)          => 5
  (cddr meine-Liste)          => ()

(cadr liste) und (cddr liste) sind Kurzschreibweisen für die Schachtelungen (car (cdr liste)) und (cdr (cdr liste)) . Diese Kurzschreibweisen sind bis zu 4 "a's" und "d's" , die auch gemischt auftauchen können zulässig.

Die Schreibweise für eine leere Liste ist auch im o.a. Beispiel zu sehen: '().

Die Länge einer Liste bestimmt die Funktion length. Im Beispiel also:

  (length meine-Liste)          => 2

Weitere Funktionen und Hinweise s.u. aus der Scheme - Hilfe

 


 

pair?

Procedure: (pair? obj)

Liefert #t für ein pair, anderenfalls #f.

 


 

cons

Procedure:(cons obj1 obj2)

Erzeugt ein Paar. Ist das zweite Element eine Liste, entsteht eine Liste.

 


 

car

Procedure: (car <Paar oder Liste>)

Gibt den Inhalt des ersten Elementes zurück.

  (car '(a b c))          =>  a

 


 

cdr

Procedure: (cdr <Paar oder Liste>)

Gibt den Inhalt des ersten Elementes zurück. Bei einer Liste ist das die Restliste !

  (cdr '(a b c))          =>  (b c)

ca...r cd...r

Procedure: (caar pair)
Procedure:(cadr pair)
    ...                   ...
Procedure:(cdddar pair)
Procedure:(cddddr pair)

s.o.

 


 

set-car!

Procedure: (set-car! pair obj)

Setzt den Wert des ersten Elementes neu.

 


 

set-cdr!

Procedure: (set-cdr! pair obj)

Setzt den Wert des zweiten Elementes neu.

 


 

null?

Procedure:(null? obj)

Liefert #t für eine leere Liste, sonst #f.

 


 

list?

Procedure:(list? obj)

Liefert #t für eine Liste, sonst #f.

 


 

list

Procedure:(list obj ...)

Liefert eine Liste aus den übergebenen Elementen.

  (list 'a (+ 3 4) 'c)            =>  (a 7 c)
  (list)                          =>  ()

 


 

length

Procedure:(length list)

Liefert die Länge der Liste.

  (length '(a b c))               =>  3
  (length '(a (b) (c d e)))       =>  3 !!!
  (length '())                    =>  0

 


 

append

Procedure: (append list ...)

append Liefert eine aus den übergebenen Listen gebildete neue Liste zurück. Wichtig ist der Unterschied zu append! :

  (define meine-Liste (cons 3 (cons 5 '())))
  meine-Liste                                 => (3 5)
  (append meine-Liste (list 7 9))             => (3 5 7 9)
  meine-Liste                                 => (3 5) !!!!
  (append! meine-Liste (list 7 9))            => (3 5 7 9)
  meine-Liste                                 => (3 5 7 9)  !!!!

Der Unterschied ist, dass im einen Fall die Umgebung verändert wurde: Die Variable meine-Liste hat einen neuen Wert. Im anderen Fall ändert er sich nicht. Wegen der Bedeutung, die eine Änderung der Umgebung hat, sind alle derartigen Funktionen mit dem Ausrufungszeichen gekennzeichnet. Also auch die Funktionen set-car! und set-cdr! (s.o.) und reverse! .

 


 

reverse

Procedure:(reverse list)

Gibt eine umgekehrte Liste zurück. Ganz wichtig: Die Umgebung wird dabei nicht verändert. Daher wäre die Formulierung "dreht die Liste um" falsch. Das macht die Funktion reverse! .

  (reverse '(a b c))              =>  (c b a)
  (reverse '(a (b c) d (e (f))))  =>  ((e (f)) d (b c) a)

 


 

list-tail

Procedure:(list-tail list k)

Gibt die Restliste ab dem k - ten Element zurück.

 


 

list-ref

Procedure:(list-ref list k)

Gibt das k - te Element einer Liste zurück.

  (list-ref '(a b c d) 2)                 =>  c

 


 

member

Procedure: (memq obj list)
Procedure:(memv obj list)
Procedure: (member obj list)

Liefert die Restliste ab dem ersten "Treffer" zurück. Zu den Unterschieden siehe die Beispiele.

  (memq 'a '(a b c))              =>  (a b c)
  (memq 'b '(a b c))              =>  (b c)
  (memq 'a '(b c d))              =>  #f
  (memq (list 'a) '(b (a) c))     =>  #f
  (member (list 'a)
          '(b (a) c))             =>  ((a) c)
  (memq 101 '(100 101 102))       =>  unspecified
  (memv 101 '(100 101 102))       =>  (101 102)

 


 

assoc

Procedure:(assq obj alist)
Procedure:(assv obj alist)
Procedure:(assoc obj alist)

Liefert bei Assoziationslisten die Teilliste zum ersten "Treffer" zurück. Zu den Unterschieden siehe die Beispiele.

  (define e '((a 1) (b 2) (c 3)))
  (assq 'a e)                =>  (a 1)
  (assq 'b e)                =>  (b 2)
  (assq 'd e)                =>  #f
  (assq (list 'a) '(((a)) ((b)) ((c))))
                             =>  #f
  (assoc (list 'a) '(((a)) ((b)) ((c))))
                             =>  ((a))
  (assq 5 '((2 3) (5 7) (11 13)))
                             =>  unspecified
  (assv 5 '((2 3) (5 7) (11 13)))
                             =>  (5 7)