5 Datendefinition durch Alternativen: Summentypen

Die Datentypen, die wir bisher kennengelernt und genutzt haben, umfassen Zahlen, Strings, Wahrheitswerte sowie in informellen Datendefinitionen definierte Datentypen wie Temperatur.

Um realistische Anwendungen zu programmieren, ist es hilfreich, ein größeres und flexibel erweiterbares Repertoire an Datentypen zu haben. In diesem Kapitel schauen wir uns an, wie man mit Datentypen unterschiedliche Situationen unterscheiden kann und wie diese Datentypen den Entwurf von Programmen beeinflussen.

5.1 Aufzählungstypen

Häufig hat man den Fall, dass ein Datentyp nur eine endliche aufzählbare Menge von Werten enthält. Wir nennen solche Datentypen Aufzählungstypen oder Enumerationstypen. Hier ist ein Beispiel, wie ein Aufzählungstyp definiert wird:

; A TrafficLight is one of:

; – "red"

; – "green"

; – "yellow"

; interp. each element of TrafficLight represents which colored

; bulb is currently turned on

Das Programmieren mit Aufzählungstypen ist sehr einfach. Wenn eine Funktion einen Parameter hat, der einen Aufzählungstyp hat, dann enthält das Programm typischerweise eine Fallunterscheidung, in denen alle Alternativen des Aufzählungstyps separat voneinander behandelt werden. Hier ein Beispiel:

; TrafficLight -> TrafficLight

; given state s, determine the next state of the traffic light

(check-expect (traffic-light-next "red") "green")

(define (traffic-light-next s)

(cond

[(string=? "red" s) "green"]

[(string=? "green" s) "yellow"]

[(string=? "yellow" s) "red"]))

Manchmal ist eine Funktion auch nur an einer Teilmenge der möglichen Werte eines Aufzählungstypen interessiert. In diesem Fall werden nur die interessanten Fälle abgefragt und der Rest ignoriert. Ein Beispiel dafür ist die on-mouse-event Funktion aus Das Universe Teachpack, die eine Eingabe vom Aufzählungstypen MouseEvent erhält. MouseEvent ist folgendermaßen definiert:

; A MouseEvt is one of:

; – "button-down"

; – "button-up"

; – "drag"

; – "move"

; – "enter"

; – "leave"

; interp. the kind of mouse event that has been triggered

In der Funktion on-mouse-event interessieren wir uns nur für die Alternative "button-down". Für alle anderen Alternativen von MouseEvent, lassen wir den Zustand unverändert.

Es kann auch sein, dass ein Funktionsparameter einen Aufzählungstyp hat, aber die Funktion trotzdem keine Fallunterscheidung vornimmt, weil hierzu eine Hilfsfunktion aufgerufen wird. Dennoch ist es eine gute Heuristik, im Schritt 3 des Entwurfsrezepts aus Abschnitt Entwurfsrezept zur Funktionsdefinition mit einem Funktionstemplate zu starten, welches alle Fälle des Parameters unterscheidet. Beispielsweise würde das Template für die traffic-light-next Funktion von oben so aussehen:

(define (traffic-light-next s)

(cond

[(string=? "red" s) ...]

[(string=? "green" s) ...]

[(string=? "yellow" s) ...]))

Wie sie sehen, können sie einen großen Teil einer Funktionsdefinition quasi mechanisch generieren, indem Sie systematisch den Schritten aus dem Entwurfsrezept folgen.

5.2 Aufzählungstypen mit überprüfbaren Signaturen

Allerdings ist es, wie so oft in der Programmierung, sinnvoll, solchen wiederkehrenden Konzepten einen Namen geben. Mit Hilfe der signature Form kann ein Name definiert werden, der im folgenden dann für die angegebene Signatur steht.

(define TrafficLight (signature (enum "red" "green" "yellow")))

; interp. each element of TrafficLight represents which colored

; bulb is currently turned on

Mit Hilfe dieser Definition kann die traffic-light-next Funktion dann wie folgt definiert werden.

(: traffic-light-next (TrafficLight -> TrafficLight))

; given state s, determine the next state of the traffic light

(check-expect (traffic-light-next "red") "green")

(define (traffic-light-next s)

(cond

[(string=? "red" s) "green"]

[(string=? "green" s) "yellow"]

[(string=? "yellow" s) "red"]))

5.3 Intervalltypen

Betrachten Sie ein Programm, welches ein Ufo beim landen zeigen soll. Ein Programm hierzu könnte wie folgt aussehen:

; constants:

(define WIDTH 300)

(define HEIGHT 100)

; visual constants:

(define MT (empty-scene WIDTH HEIGHT))

(define UFO

(overlay (circle 10 "solid" "green")

(rectangle 40 2 "solid" "green")))

(define BOTTOM (- HEIGHT (/ (image-height UFO) 2)))

; A WorldState is a number.

; interp. height of UFO (from top)

; WorldState -> WorldState

; compute next location of UFO

(define (nxt y)

(+ y 1))

; WorldState -> Image

; place UFO at given height into the center of MT

(define (render y)

(place-image UFO (/ WIDTH 2) y MT))

; WorldState -> Boolean

; returns #true when UFO has reached the bottom, i.e. y > BOTTOM

(define (end-of-the-world y) (> y BOTTOM))

; wire everything together; start descend at position 0

(big-bang 0 (on-tick nxt) (to-draw render) (stop-when end-of-the-world))

Betrachten Sie nun folgende Erweiterung der Problemstellung:

The status line should say "descending" when the UFO’s height is above one third of the height of the canvas. It should switch to "closing in" below that. And finally, when the UFO has reached the bottom of the canvas, the status should notify the player that the UFO has "landed."

Der Datentyp, der sich in dieser Problemstellung versteckt, ist kein Enumerationstyp, denn es gibt eine unendliche Zahl unterschiedlicher Höhen (oder, sofern wir nur die ganzen Zahlen zählen, so viele unterschiedliche Höhen, dass es unpraktisch wäre, hierfür einen Aufzählungstypen zu definieren).

Daher verwenden wir Intervalle, um zusätzliche Struktur auf geordneten Datentypen wie Zahlen oder Strings zu definieren. Im folgenden konzentrieren wir uns auf (ganzzahlige oder nicht-ganzzahlige) Zahlen. Ein Intervall wird durch seine Grenzen definiert. Ein Intervall hat entweder eine untere und obere Grenze, oder es hat nur eine dieser Grenzen und ist zur anderen Seite offen.

In unserem Beispiel können wir die Datendefinition für den WorldState als Intervall ausdrücken, um eine Datendefinition zu haben, die die Intention der Problemstellung besser erfasst.

; constants:

(define CLOSE (* 2 (/ HEIGHT 3)))

; A WorldState is one of:

; – Number between 0 and CLOSE

; – Number between CLOSE and BOTTOM

; – BOTTOM

; interp. height of UFO (from top)

Nicht alle Funktionen, die einen Intervalltypen als Argument bekommen, nutzen diese zusätzliche Struktur. So kann zum Beispiel die render Funktion von oben so bleiben wie sie ist, weil das Intervall nur für die Statusanzeige aber nicht für das Ufo relevant ist.

Funktionen, die jedoch die zusätzliche Struktur des Intervalls benötigen, enthalten typischerweise einen cond Ausdruck, der die unterschiedlichen Intervalle unterscheidet.

; WorldState -> Image

; add a status line to the scene created by render

(define (render/status y)

(cond

[(<= 0 y CLOSE) (above (text "descending" 12 "black") (render y))]

[(< CLOSE y BOTTOM) (above (text "closing in" 12 "black") (render y))]

[(= y BOTTOM) (above (text "landed" 12 "black") (render y))]))

Es empfiehlt sich, diesen cond Ausdruck im Rahmen der Templatekonstruktion aus dem Entwurfsrezept direkt in das Template mit aufzunehmen. Allerdings findet die Fallunterscheidung nicht notwendigerweise als erstes statt sondern kann auch tiefer im Funktionsbody stattfinden. Dies bietet sich in unserem Beispiel an, denn wir haben gegen das DRY Prinzip verstoßen (Wenn wir die Farbe des Textes beispielsweise auf "red" ändern möchten, müssten wir drei Zeilen ändern). Deshalb ist es vorteilhaft, den konditionalen Ausdruck nach innen zu ziehen:

; WorldState -> Image

; add a status line to the scene created by render

(define (render/status y)

(above

(text

(cond

[(<= 0 y CLOSE) "descending"]

[(< CLOSE y BOTTOM) "closing in"]

[(= y BOTTOM) "landed"])

12 "black")

(render y)))

Intervalle liefern uns außer neuen Funktionstemplates auch Anhalte zum Testen: Typischerweise möchte man einen Testcase für jedes Intervall und insbesondere für die Intervallgrenzen haben.

5.4 Summentypen

Intervalltypen unterscheiden unterschiedliche Teilmengen der Zahlen (oder anderer geordneter Werte). Aufzählungstypen zählen die unterschiedlichen Elemente des Typs Wert für Wert auf.

Summentypen verallgemeinern Intervalltypen und Aufzählungstypen. Mit Summentypen können existierende Datentypen und individuelle Werte beliebig miteinander kombiniert werden. Ein Summentyp gibt verschiedene Alternativen an, von denen jeder Wert dieses Typs genau eine Alternative erfüllt.

Betrachten wir als Beispiel die string->number Funktion, die einen String in eine Zahl konvertiert, falls dies möglich ist, und andernfalls #false zurückgibt.

Hier ist die Definition eines Summentyps, der das Verhalten dieser Funktion beschreibt:

; A MaybeNumber is one of:

; – #false

; – Number

; interp. a number if successful, else false.

Damit können wir für string->number folgende Signatur definieren:

; String -> MaybeNumber

; converts the given string into a number;

; produces #false if impossible

(define (string->number str) ...)

Summentypen werden manchmal auch Vereinigungstypen (union types) genannt. In HTDP/2e werden sie Itemizations genannt.

In der Dokumentation der HTDP-Sprachen ist die Signatur von string->number so angegeben:

String -> (union Number #false)

Der Operator union steht für die “on-the-fly” Konstruktion eines anonymen Summentyps mit der gleichen Bedeutung wie unser MaybeNumber oben.

Was macht man mit einem Wert, der einen Summentyp hat? Wie bei Aufzählungs- und Intervalltypen auch ist typischerweise die einzige sinnvolle Operation die, welche die unterschiedlichen Alternativen voneinander trennt, beispielsweise im Rahmen eines cond Ausdrucks. Hier ein Beispiel:

; MaybeNumber -> MaybeNumber

; adds 3 to a if it is a number; returns #false otherwise

(check-expect (add3 5) 8)

(check-expect (add3 #false) #false)

(define (add3 a)

(cond [(number? a) (+ a 3)]

[else #false]))

Funktionen mit Summentypen unterscheiden sich in ihrer Entwurfsmethodik etwas von den Funktionen, die wir bisher kennengelernt haben. Deswegen gehen wir nochmal durch unser Entwurfsrezept (Entwurfsrezept zur Funktionsdefinition) und beschreiben, wie sich der Entwurf von Funktionen mit Summentypen vom allgemeinen Entwurfsrezept unterscheidet.

The tax on an item is either an absolute tax of 5 or 10 currency units, or a linear tax. Design a function that computes the price of an item after applying its tax.

5.4.1 Entwurf mit Summentypen

5.5 Unterscheidbarkeit der Alternativen

Was wäre, wenn wir in unserem letzten Beispiel statt zwei absoluten Steuersätzen ein kontinuierliches Spektrum hätten? Wir könnten unsere Datendefinition wie folgt abändern:

; A Tax is one of

; - a Number representing an absolute tax in currency units

; - a Number representing a linear tax rate in percent

So weit so gut – aber wie können wir in einem cond Ausdruck diese Fälle unterscheiden? Wir haben zwar das Prädikat number?, aber damit können wir nicht zwischen diesen beiden Fällen unterscheiden.

In unseren Summentypen ist es wichtig, dass man eindeutig unterscheiden kann, welche Alternative in einem Wert, der einen Summentyp hat, gewählt wurde. Daher müssen die Mengen der möglichen Werte für jede Alternative disjunkt sein.