Paare
Listen
car
cdr
length
append
reverse
null?
pair?
list?
set-car!
set-cdr!
append!
reverse!
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:
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)
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:
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
Procedure: (pair? obj)
Liefert #t für ein pair, anderenfalls #f.
Procedure:(cons obj1 obj2)
Erzeugt ein Paar. Ist das zweite Element eine Liste, entsteht eine Liste.
Procedure: (car <Paar oder Liste>)
Gibt den Inhalt des ersten Elementes zurück.
(car '(a b c)) => a
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)
Procedure: (caar pair) Procedure:(cadr pair) ... ... Procedure:(cdddar pair) Procedure:(cddddr pair)
s.o.
Procedure: (set-car! pair obj)
Setzt den Wert des ersten Elementes neu.
Procedure: (set-cdr! pair obj)
Setzt den Wert des zweiten Elementes neu.
Procedure:(null? obj)
Liefert #t für eine leere Liste, sonst #f.
Procedure:(list? obj)
Liefert #t für eine Liste, sonst #f.
Procedure:(list obj ...)
Liefert eine Liste aus den übergebenen Elementen.
(list 'a (+ 3 4) 'c) => (a 7 c) (list) => ()
Procedure:(length list)
Liefert die Länge der Liste.
(length '(a b c)) => 3 (length '(a (b) (c d e))) => 3 !!! (length '()) => 0
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! .
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)
Procedure:(list-tail list k)
Gibt die Restliste ab dem k - ten Element zurück.
Procedure:(list-ref list k)
Gibt das k - te Element einer Liste zurück.
(list-ref '(a b c d) 2) => c
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)
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)