Beispiel: Rationale Zahlen
Eine rationale Zahl besteht aus zwei Integer-Werten (x,y), die einen Bruch x/y darstellen. Z.B. stellen (1,7), (3,21) und (168,1176)
alle 1/7 dar. (-1,3) und (1,-3) stehen beide für -(1/3). Alle sind wohldefiniert, wobei beachtet werden muss, dass nur Zahlen
(x,y) mit y ≠ 0 wohldefiniert sind.
Es ist möglich, eine einzige rationale Zahl auf unendlich viele Arten darzustellen. Daher macht es Sinn, die sogenannte kanonische Form zu
wählen, die nicht weiter reduziert werden kann. Ein Bruch kann immer eindeutig durch ein Paar (x, y) dargestellt werden, wobei
y > 0 und gcd(x, y) = 1. Gcd(x, y) (greatest common divisor) stellt den grössten gemeinsamen Teiler von x und
y dar. Im Einzelnen bedeutet dies, dass die einzige Darstellung von 0, die diesen Bedingungen genügt, (0,1) ist.
Das Ziel in diesem Abschnitt ist es, die rationalen Zahlen als Haskell-Zahlentyp festzulegen. Als erstes führen wir Rational
als Datentypen ein:
newtype Rational = Rat (Integer, Integer)
|
Der Funktion mkRat wird ein Paar von Integern übergeben, zurückgeliefert wird ein Rational in kanonischer Form:
mkRat :: (Integer, Integer) -> Rational
mkRat(x, y) = Rat(u div d) (v div d)
where u = (signum y) * x
v = abs y
d = gcd(u, v)
|
Rationale Zahlen werden nur durch den Gebrauch von
mkRat erzeugt, wodurch sichergestellt ist, dass alle rationalen Zahlen in
kanonischer Form vorliegen. Die vorgestellten Beispiele gibt es z.T.
hier. Der Typ
Rational wird als
neuer Typ deklariert und nicht als Typsynonym für
(Integer, Integer), weil sich z.B. die Vergleichsoperationen auf
Rational von
denen auf Paare unterscheiden.
Beispiel: (2, 1)<(3, 2) bei Paaren, bei rationalen Zahlen allerdings ist 2 > 3/2, dementsprechend wird definiert:
instance Eq Rational where
Rat x y == Rat u v = (x * v) == (v * y)
instance Ord Rational where
Rat x y < Rat u v = (x * v) < (v * y)
|
Die Definition von (<) ist nur dann korrekt, wenn sowohl Rat x y, als auch Rat u v in kanonischer Form vorliegen.
Rationale Zahlen können durch eine spezielle Funktion showRat angezeigt werden:
showRat(Rat x y) = if y == 1 then show x else show x ++ "/" ++ show y
|
Diese Definition benutzt die primitive Show-Funktion des Typen Integer und ausserdem den Operator ++ zur Konkatenierung von
zwei Strings. Problematisch ist, dass showRat Rational nicht als Mitglied der Typklasse Show deklariert. Diese Deklaration ist
allerdings notwendig, um Rational als gültigen Zahltyp festzulegen. Man kann die Default-Definition benutzen,
durch Einfügen der Ableitungsklausel in der Deklaration von Rational. Allerdings unterscheidet sich die resultierende
Funktion Show von showRat. Abgesehen von diesem Punkt kann Rational als Mitglied von Num wie folgt
deklariert werden:
instance Num Rational where
Rat x y + Rat u v = mkRat (x * v + u * y, y * v)
Rat x y - Rat u v = mkRat (x * v - u * y, y * v)
Rat x y * Rat u v = mkRat (x * u, y * v)
negate(Rat x y) = mkRat (-x, y)
fromInteger x = mkRat (x, 1)
|
Übrig bleibt die Definition von gcd. Es gibt zwei unterschiedliche Arten, diese Funktion zu spezifizieren.
Erstens
gcd x y ist der
grösste positive Integer
d, der sowohl
x als auch
y teilt.
Zweitens:
gcd x y = d, wenn
a)
d sowohl
x
als auch
y teilt und
b) für alle
e gilt: Wenn
e sowohl alle
x als auch
y teilt,
dann teilt
e auch
d.
In der ersten Spezifikation gilt
gcd(0,0) = undefined, weil jeder positive Integer 0 teilt,
also gibt es keinen grössten; in der zweiten Spezifikation gilt
gcd(0,0) = 0. Abgesehen von diesem einen Fall sind beide Definitionen
äquivalent. Mit der zweiten Spezifikation kann
gcd rekursiv nach Euklid berechnet werden.
gcd :: (Integer, Integer) -> Integer
gcd(x,y) = if y = 0 then x else gcd (y, x mod y)
|
Z.B. weil 0 mod 3 = 0, (-6) mod 4 = 2 und (-3) mod 1 = 0 erhalten wir:
gcd(0,3) = gcd(3,0) = 3
gcd(-6,4) = gcd(4,2) = gcd(2,0) = 2
gcd(-3,1) = gcd(1,0) = 1
|
Zuletzt kann Rational als eine Instanz der Typklasse Fractional deklariert werden:
instance Fractional Rational where
fromRational = id
Rat x y/Rat u v
| u < 0 = mkRat(-x * v, -y * u)
| u == 0 = error "division by 0"
| u > 0 = mkRat(x * v, y * u)
|