7 Polynome

In den letzten beiden Kapiteln haben wir zwei neue Arten von Datendefinitionen kennengelernt: Summentypen (in Form von Aufzählungen und Intervallen), mit denen man zwischen verschiedenen Möglichkeiten auswählen kann. Produkttypen (in Form von Datendefinitionen für Strukturen), mit denen man Daten zusammenfassen und gruppieren kann.

In vielen Fällen ist es sinnvoll, Summen und Produkte miteinander zu kombinieren, also zum Beispiel Summentypen zu definieren, bei denen einige Alternativen einen Produkttyp haben; oder Produkttypen bei denen einige Felder Summentypen haben.

7.1 Beispiel: Kollisionen zwischen Shapes

(define-struct gcircle (center radius))

; A GCircle is (make-gcircle Posn Number)

; interp. the geometrical representation of a circle

(define-struct grectangle (corner-ul corner-dr))

; A GRrectangle is (make-grectangle Posn Posn)

; interp. the geometrical representation of a rectangle

; where corner-ul is the upper left corner

; and corner-dr the down right corner

Das interessante an diesen beiden Definitionen ist, dass Kreise und Rechtecke viele Gemeinsamkeiten haben. Beispielsweise können beide verschoben, vergrößert oder gezeichnet werden. Viele Algorithmen sind für beliebige geometrische Formen sinnvoll und unterscheiden sich nur in den Details. Nennen wir die Abstraktion, die beliebige geometrische Figuren bezeichnet, beispielsweise Shape. Nehmen wir an, wir haben bereits eine Funktion, die für beliebige geometrische Formen bestimmen kann, ob sie überlappen:

; Shape Shape -> Boolean

; determines whether shape1 overlaps with shape2

(define (overlaps shape1 shape2) ...)

Auf Basis dieser und ähnlicher Funktionen können wir weitere Funktionen programmieren, die völlig unabhängig vom konkreten Shape (ob Kreis oder Rechteck) sind, beispielsweise eine Funktion, die für drei Shapes testet ob sie paarweise überlappen:

; Shape Shape Shape -> Boolean

; determines whether the shapes overlap pairwise

(define (overlaps/3 shape1 shape2 shape3)

(and

(overlaps shape1 shape2)

(overlaps shape1 shape3)

(overlaps shape2 shape3)))

Die Funktion overlaps muss zwar unterscheiden, was für eine genaue Form ihre Parameter haben, aber die Funktion overlaps/3 nicht mehr. Dies ist eine sehr mächtige Form der Abstraktion und Code-Wiederverwendung: Wir formulieren abstrakte Algorithmen auf Basis einer Menge einfacher Funktionen wie overlaps und können dann diese Algorithmen auf alle Arten von Shapes anwenden.

Die Funktion overlaps/3 steht also wirklich für eine ganze Familie von Algorithmen: Je nachdem, was für Shapes ich gerade als Argument verwende, machen die Hilfsfunktionen wie overlaps etwas anderes, aber der abstrakte Algorithmus in overlaps/3 ist immer gleich.

Schauen wir uns nun an, wie wir Datentypen wie Shape und Funktionen wie overlaps definieren können. Um die Menge der möglichen geometrischen Figuren zu beschreiben, verwenden wir einen Summentyp, dessen Alternativen die Produkttypen von oben sind:

; A Shape is either:

; - a GCircle

; - a GRectangle

; interp. a geometrical shape representing a circle or a rectangle

Nicht alle Algorithmen sind wie overlaps/3 — sie sind unterschiedlich je nachdem welches Shape gerade vorliegt. Wie bereits aus dem Entwurfsrezept für Summentypen bekannt, strukturieren wir solche Funktionen, indem wir eine Fallunterscheidung machen.

Beispiel:

; Shape Posn -> Boolean

; Determines whether a point is inside a shape

(define (point-inside shape point)

(cond [(gcircle? shape) (point-inside-circle shape point)]

[(grectangle? shape) (point-inside-rectangle shape point)]))

In dieser Funktion fällt auf, dass in den Zweigen des cond Ausdrucks Hilfsfunktionen aufgerufen werden, die wir noch implementieren müssen. Man könnte stattdessen die Implementation dieser Funktionen auch direkt in den cond Ausdruck schreiben, aber wenn die Alternativen eines Summentyps Produkte sind, so werden diese Ausdrücke häufig so komplex, dass man sie besser in eigene Funktionen auslagern sollte. Außerdem ergeben sich durch die Auslagerung in separate Funktionen häufig Gelegenheiten zur Wiederverwendung dieser Funktionenen.

In unserem Beispiel sehen die Implementationen dieser Hilfsfunktionen wie folgt aus:

Bei manchen Funktionen haben gleich mehrere Parameter einen Summentypen. In diesem Fall kann man erst für den ersten Parameter die Fallunterscheidung machen, dann geschachtelt für den zweiten Parameter usw. Häufig kann man jedoch auch die Fallunterscheidungen zusammenfassen. Dies ist beispielsweise bei dem oben angesprochenen overlaps der Fall:

; Shape Shape -> Boolean

; determines whether shape1 overlaps with shape2

(define (overlaps shape1 shape2)

(cond [(and (gcircle? shape1) (gcircle? shape2))

(overlaps-circle-circle shape1 shape2)]

[(and (grectangle? shape1) (grectangle? shape2))

(overlaps-rectangle-rectangle shape1 shape2)]

[(and (grectangle? shape1) (gcircle? shape2))

(overlaps-rectangle-circle shape1 shape2)]

[(and (gcircle? shape1) (grectangle? shape2))

(overlaps-rectangle-circle shape2 shape1)]))

Auch hier haben wir wieder die Implementierung der einzelnen Fälle in Funktionen ausgelagert. Die Tatsache, dass wir in den beiden letzten Fällen die gleiche Funktion aufrufen, illustriert, dass diese Hilfsfunktionen die Wiederverwendung von Code fördern. Hier die Implementation der Hilfsfunktionen.

7.2 Programmentwurf mit Polynomtypen

Das Entwurfsrezept aus Abschnitt Entwurfsrezept zur Funktionsdefinition ergänzen wir wie folgt:

1. Wenn Sie eine Funktion programmieren möchten, die Informationen als Eingabe erhält oder als Ausgabe produziert, die man am besten durch Polynomtypen repräsentiert, so sollten Sie vor dem Programmieren dieser Funktion diesen Polynomtyp definieren (falls sie ihn nicht schon im Kontext einer anderen Funktion definiert haben).

   Ein Polynomtyp ist dann sinnvoll, wenn in ihrer Problemstellung unterschiedliche Arten von Informationen unterschieden werden, die jeweils als Produkttyp formuliert werden können, die aber ein gemeinsames Konzept repräsentieren.

   Ein wichtiger Punkt ist, dass man Daten mit Polynomtypen hierarchisch organisieren kann. Die Feldtypen der Produkte, die man definiert, können also selber wieder einen Polynomtyp haben. Wenn also ein Produkttyp sehr viele Felder hat, oder ein Summentyp sehr viele Alternativen, so deutet dies darauf hin, dass Sie eine tiefere Hierarchie (durch Verschachtelung von Polynomtypen) verwendensollten.

2. Im zweiten Schritt, der Definition der Funktionssignatur und der Aufgabenbeschreibung, ändert sich nichts — allerdings können und sollten Sie nun natürlich die Namen der definierten Polynomtypen verwenden.

3. Nichts ändert sich im dritten Schritt. Wie immer bei Summentypen sollten Sie mindestens einen Test pro Alternative definieren.

4. Bei der Definition des Funktionstemplates gibt es nun zwei Dimensionen: Den Summentyp und die Produkttypen in (einigen seiner) Alternativen.

   Falls wir als äußerstes einen Summentyp haben, so sollten wir zunächst in einem cond Ausdruck alle Fälle unterscheiden.

   Für alle Alternativen, die Produkttypen sind, sollte in der Regel eine Hilfsfunktion definiert werden, die diesen Fall abdeckt. Diese Hilfsfunktion sollten sie in diesem Schritt auch nur (durch erneute Anwendung dieses Entwurfsrezepts) bis zum Template-Schritt implementieren.

   Nur wenn die Implementation dieses Falls wahrscheinlich sehr einfach ist, sollten die Selektoren für die Felder des Produkts in das Template mit aufgenommen werden.

   Allerdings gibt es einen wichtigen Fall, in dem sie keinen cond Ausdruck zur Unterscheidung der Alternativen ins Template aufnehme sollte, nämlich dann, wenn es möglich ist, die Funktion abstrakt zu formulieren — sie also die Fälle nicht unterscheiden, sondern lediglich bereits existierende Funktionen aufrufen, die auch auf Basis des Polynomtyps implementiert wurden. Als Beispiel haben wir die overlap/3 Funktion gesehen.

5. In diesem Schritt sollten sie aus dem Template ein lauffähiges Programm machen. Da sie im vorherigen Schritt eventuell Templates für Hilfsfunktionen definiert haben, müssen sie auch diese Hilfsfunktionen nun implementieren.

6. Testen sie. Falls Tests fehlschlagen, gehen sie zurück zum vorherigen Schritt.