inf-schule | Der Aufbau von Listen in Racket » Der Aufbau von Listen in Racket

Der Aufbau von Listen in Racket

Listenerstellung in Racket

Eine Liste in Racket ist unabhängig von ihrer Erstellung stets gleich aufgebaut:

Eine Liste ist entweder eine leere Liste, oder eine nicht-leere Liste.
Eine nicht-leere Liste besteht aus einer leeren Liste, an welche nacheinander beliebig viele neue Elemente angefügt wurden.
Das zuletzt angefügte Element bildet das First-Element (ebenfalls geläufig: Head), die restlichen Elemente bilden den Rest (Tail) der Liste. Der Rest ist somit wiederum eine Liste.

Wenn wir in Racket Listen erstellen kann dies über zwei Funktionen geschehen cons oder list. Die Erstellung der Liste (0, 1, 2, 3) würde jeweils wie folgt aussehen:

(cons 0 (cons 1 (cons 2 (cons 3 empty))))

(list 0 1 2 3)

In der zugrundeliegenden Logik erstellen jedoch beide Ausdrücke die gleiche Liste nach dem selben Prinzip:

Wollen wir auf die einzelnen Bestandteile der Liste zugreifen so gibt die Funktion first für eine übergeben Liste das First-Element zurück, die Funktion rest den Rest.

Aufgabe 1: Gleichheit von Ausdrücken

(a) Welche der folgenden Ausdrücke produzieren identische Listen?
Ordne je einem orangen Ausdruck einen blauen Ausdruck zu.

Listen erweitern in Racket

Wenn wir in Racket Listen erweitern möchten kann auch dies über zwei verschiedene Funktionen geschehen conscons oder append. Die beiden Funktion weisen jedoch eine grundlegend andere Funktionalität auf.

Aufgabe 2: Signaturen von Listenfunktionen

Um uns Unterschiede in den Funktionsweisen klarzumachen lohnt sich ein Blick auf die Signaturen. Hier gibt es ein paar Neuerungen.

Die Signaturen für die Funktionen first und rest sehen wie folgt aus:

first: ((list-of %a) -> %a)
rest: ((list-of %a) -> (list-of %a))

(a) Erkläre wofür list-of und %a in der Signatur stehen.
Betrachte hierzu die folgenden Ausdrücke und die übergebenen und erzeugten Daten:


(first (list 1 2 3 4))    
;(list-of natural) -> natural

(rest (list 1 2 3 4))
;(list-of natural) -> (list-of natural)

(first (list "Hallo" "Welt" "!"))
;(list-of string) -> string

(rest (list "Das" 1 "ist" 2 "eine" #t "gemischte Liste"))
;(list-of any) -> (list-of any)

(b) Wähle eine korrekte Signatur für:

cons:

append:

cons in anderen Racket-Versionen

In unserer Racket-Version ist die Eingabe (cons 1 2) nicht möglich, da daraus keine Liste entsteht. In manchen Racket-Versionen ist (cons 1 2) jedoch ein valider Ausdruck, dieser konstruiert dann allerdings keine Liste, sondern ein Paar. Um eine Liste zu erzeugen, muss wie gewohnt auf einer empty-Liste aufgebaut werden.