Beispiel 2 - Zahlendarstellung
Übersicht: Beispiel 2 - Zahlendarstellung
Einleitung
Haskell unterstützt zwei verschiedene Ganzzahltypen: Integer und Int. Der Unterschied liegt in der Genauigkeit: Während Int den Ganzzahl-Datentyp aus klassischen Programmiersprachen mit Maschinenwort-Genauigkeit repräsentiert, stellt der Integer-Typ Ganzzahlen beliebiger Genauigkeit (also Größe) dar. Dieses Beispiel ignoriert die Existenz des sprachintegrierten Integer-Typen und zeigt die Implementierung eines Ganzzahl-Typen beliebiger Genauigkeit unter Zuhilfenahme von Listen und Int-Typ. Dabei soll der neue Typ natürlich den Typklassen-Mechanismus von Haskell ausnutzen und als Instanz einiger numerischer Klassen (Eq, Ord, Num) installiert werden, um bei seiner Verwendung Overloading und damit eine intuitive saubere Syntax auszunutzen.
Repräsentation und Normalisierung
Als Repräsentation unseres Zahlentypen verwenden wir eine Liste von Ziffern zu einer definierten Basis b. Als erstes definieren wir uns dazu einen einfachen passenden Datentypen:
01 newtype ArbInt = Norm [Digit]
02 base :: Int
03 base = 10
04
05 -- Auswickeln der Ziffernliste aus einem ArbInt
06 digits :: ArbInt -> [Digit]
07 digits (Norm xs) = xs
08
09 -- Konvertieren einer Ziffernliste zur Basis b in den sprachintegrierten Integer-Typ
10 convert :: [Int] -> Integer
11 convert = foldl (#) 0
12 where n # d = base * n + d
|
2-1.txt |
Codebeispiel 14
Der Konstruktor Norm steht hier symbolisch für die Normalisierung, die weiter unten gefordert werden wird, Digit wird ein Synonym für den Int-Typen sein (type Digit = Int) und die Ziffern unserer Zahlendarstellung repräsentieren. digits ist das Gegenstück zum ArbInt-Konstruktor und wickelt die Ziffernliste wieder aus einem ArbInt aus - dies ermöglicht nachfolgenden Funktionen für die Verarbeitung von ArbInts eine gewisse Abstraktion von der Implementierung (man kann dann schreiben "foo = ... . digits" statt "foo Norm xs = ... xs". convert schließlich wandelt eine Ziffernliste in den sprachintegrierten Integer-Typen um (ebenfalls formal unbegrenzter Wertebereich), in dem es die Multiplikation mit der Basis und Addition der nächsten Ziffer von links in die Liste faltet - dadurch wird die erste Ziffer n-1 mal, die zweite n-2 mal usw. mit der Basis multipliziert (wobei n die Ziffernzahl ist), womit sich jeweils die korrekte Stellenwertigkeit ergibt.
Zur Definition einer Zahl unseres Typen sind ein Objekt des Typs ArbInt und die dazugehörige Basis erforderlich. Beispiel: 42 entspricht hier b=4, x=222. Dieses Modell erlaubt jedoch bei gegebener Basis noch mehrere Varianten zur Darstellung derselben Zahl, so entspricht z.B. 100 unter anderem den Darstellungen [1,0,0], b=10, [10,0], b=10 und [0,0,0,0,100], b=10. Zur Vermeidung dieser Mehrdeutigkeiten definieren wir, daß 1. eine Zahl unseres Datentypen keine führenden (informationslosen) Nullen aufweisen darf. 2. wird für jede Ziffer x 0 <= x < b gelten, mit Ausnahme der ersten Ziffer, für die -1 <= x < b gilt. Die Ausnahme der ersten Ziffer dient der Repräsentation negativer Zahlen mittels der vorzeichenbehafteten Komplementdarstellung (signed complement representation). Diese Darstellung addiert zur einfachen negativen Wertigkeit der ersten Ziffer alle anderen Ziffern; "-111" entspricht in diesem Modell -100 + 10 + 1 = -89. Der Vorteil liegt in der einfachen Verarbeitung, es wird zu sehen sein, daß die negative Darstellung nicht als Sonderfall berücksichtigt werden muß - anders als bei der handelsüblichen Variante der negativen Zahlen (signed magnitude representation), die einfach aus ihrem absoluten Wert bereichert um eine Auszeichnung als negative Zahl besteht und für die eine Fallunterscheidung erforderlich ist.
Eine Konsequenz aus unseren Forderungen lautet, daß die 0 in unserem Datentypen nicht naiv mit [0] repräsentiert wird (genausogut könnte es [0,0,0] lauten), sondern mit der leeren Liste [] (entspricht mithin der Forderung nach der Eliminierung aller führenden Nullen). isZero wird ein Prädikat sein, daß genau diese Definition für ArbInts reflektiert und mithin von der Implementierung abstrahiert - nachfolgende Funktionen müssen nicht auf den Test auf leere Listen abstellen, sondern können einheitlich das isZero-Prädikat nutzen. Um unsere Spezifikation bezüglich der Ziffern eines ArbInts durchzusetzen definieren wir des Weiteren eine Normalisierungsfunktion:
01 -- Normalisieren, d.h., führende Nullen entfernen und Ziffern in die Basis "modulieren"
02 type Carry = int
03 norm :: [Int] -> ArbInt
04 norm = Norm . dropWhile (==0) . addCarry . foldr carry (0,[])
05
06 -- Eine Ziffer "modulieren" und ein Teilergebnistupel liefern
07 carry :: Digit -> (Carry,[Digit]) -> (Carry,[Digit])
08 carry x (c,xs) = ((x + c) div base, (x + c) mod base : xs)
09
10 isZero :: ArbInt -> Bool
11 isZero = null . digits
|
2-2.txt |
Codebeispiel 15
In dieser Form stellt norm quasi eine Aufwertung des Konstruktors Norm dar. Das Grundprinzip lautet, alle Zahlen der Liste (beginnend rechts bei der geringwertigsten) modulo b zu rechnen (das Ergebnis ist ein Wert x für den gilt 0 <= x < b und der das nächste Element in der Ergebnisliste repräsentiert), das Divisionsergebnis (das Vielfache der nächsten Potenz, das zwangläufig nicht mehr im aktuellen Element unterzubringen ist) als Carry der nächsten Zahl hinzuzuaddieren und den Vorgang mit dieser fortzusetzen. Zwischen die Zahlen der Liste wird dazu die carry-Funktion gefaltet, das Ausgangselement ist das Tupel (0,[]). carry kombiniert das Tupel mit dem aktuellen Listenelement und ergibt ein neues Tupel. Der erste Teil des Tupels repräsentiert den aktuellen Carry-Wert, der zweite Teil die bisherige Ergebnisliste. Nach der Faltung der Ursprungsliste erhalten wir allerdings unter Umständen einen Restcarry, da die Operation zwangsläufig mit Verarbeitung des höchstwertigen Elements der Ursprungsliste endet. Um diesen Restcarry gegebenenfalls in führende Elemente der Ergebnisliste umzusetzen, wird addCarry auf das Ergebnistupel angewendet.
01 -- Rekursive Carry-Funktion
02 addCarry :: (Carry,[Digit]) -> [Digit]
03 addCarry (c, xs) = if(-1 <= c) ^ (c < base) then c : xs
04 else addCarry (c div base, c mod base : xs)
|
2-3.txt |
Codebeispiel 16
addCarry berechnet ähnlich carry aus dem Restcarry mittels modulo b das nächste Listenelement, dieser Vorgang wird hier jedoch (da die Zahl der notwendigen zusätzlichen Listenelemente beliebig sein kann) in eine Rekursion eingebettet, die solange das Ergebnistupel fortführt (Carry durch Division neu berechnen, Ergebnisliste um Modulo erweitern), bis der Carry in der Basis b untergebracht werden kann (in diesem Fall terminiert addCarry und wickelt die Ergebnisliste aus dem Tupel aus). norm beraubt die so gewonnene Liste noch eventueller führender Nullen und kombiniert sie schließlich mit dem Konstruktor Norm zu einem ArbInt.
Für einige binäre Operationen wird es erforderlich sein, daß unsere Eingabewerte (ArbInt) bzw. ihre Ziffernlisten die gleiche Länge aufweisen. Um dies zu erreichen, wird die Funktion align definiert, die die jeweils kürzere Liste nach vorne hin mit Nullen auffüllt, bis sie genauso lang wie die andere Liste ist. Die notwendige Anzahl Nullen ist leicht durch die Subtraktion der Listenlängen zu errechnen, die kürzere Liste kann aus dem Vorzeichen der Listenlängendifferenz abgeleitet werden. Es ist zu beachten, daß das Ergebnis der Ausrichtungsprozedur natürlich kein ArbInt-Wert ist, da führende Nullen zugelassen werden und sogar erwünscht sind - align eignet sich also lediglich als Zwischenfunktion. Zur Erzeugung der Nullen nutzen wir die Prelude-Funktion replicate, die ein beliebiges Objekt vervielfacht und daraus eine Liste konstruiert - diese muß schließlich nur noch mit der kürzeren Eingabeliste konkateniert werden.
01 -- Zwei Ziffernlisten auf gleiche Länge erweitern
02 align :: ([Digit],[Digit]) -> ([Digit],[Digit])
03 align (xs,ys)
04 | n > 0 = (replicate n 0 ++ xs, ys)
05 | n <= 0 = (xs, replicate (-n) 0 ++ ys)
06 where n = length ys - length xs
|
2-4.txt |
Codebeispiel 17
Vergleichsoperatoren
Die Vergleichsoperationen folgen stets dem gleichen Grundprinzip und werden daher auf eine allgemeinere Funktion zurückgeführt, die mit den sprachintegrierten Vergleichsoperationen für die einzelnen Listenelemente (Int -> Int -> Bool) parametrisiert wird. Tatsächlich erfolgt die Parametrisierung mit Funktionen des Typs [Int] -> [Int] -> Bool bzw. [Digit] -> [Digit] -> Bool, diese sind jedoch für die besagten Vergleichsoperationen ebenfalls definiert. Das Prinzip dieser Funktion (translate) ist es, zwei ArbInt-Werte in Digit-Listen zu konvertieren, mit align auf gleiche Länge zu erweitern und anschließend die Vergleichsoperation auf die entstandenen Listen anzuwenden. Danach können wir den ArbInt-Typen direkt in den Vergleichs- und Ordnungsklassen Eq und Ord installieren:
01 -- Anwenden eines Prädikates auf zwei ArbInt-Werte
02 translate :: ([Digit] -> [Digit] -> Bool) -> (ArbInt -> ArbInt -> Bool)
03 translate op x y = op xs ys
04 where (xs, ys) = align (digits x, digits y)
05
06 -- Installation des ArbInt-Typen für Gleichheitstests
07 instance Eq ArbInt where
08 (==) = translate (==)
09
10 -- Installation des ArbInt-Typen für Vergleiche
11 instance Ord ArbInt where
12 (<=) = translate (<=)
|
2-5.txt |
Codebeispiel 18
Die Funktion für positive ArbInts (Listen von positiven Zahlen) ist offensichtlich, für negative ist sie leicht einzusehen: Die erste Ziffer bei negativen Zahlen ist immer gleich, bei folgenden Ziffern sind alle positiv und bei der größeren Zahl auch tatsächlich größer. Beim Vergleich einer negativen mit einer positiven Zahl bewirkt die negative erste Ziffer stets das korrekte Ergebnis. Das Problem der leeren Liste stellt sich nicht, da entweder beide Zahlen 0 sind oder aber ein alignment die leere Liste zu einer Liste von Nullen erweitert.
Addition und Subtraktion
Addition und Subtraktion lassen sich konzeptionell sehr leicht umsetzen, im Grundsatz werden alle Ziffern gleicher Potenz der beiden ArbInt-Werte zusammenaddiert bzw. subtrahiert. Die sich ergebende Zahl ist wertmäßig korrekt, jedoch kein ArbInt - es sind Ziffern x außerhalb von 0 <= x < b möglich (bei der Addition kann b überschritten werden, bei der Subtraktion können einzelne Ziffern negativ werden). Zusätzlich ist also eine Normalisierung mit der bereits oben definierten norm - Funktion erforderlich, die aus unserer Zahlenfolge wieder einen ordnungsgemäßen ArbInt macht. Vor der eigentlichen Addition der beiden Listen müssen sie zudem aus den oben genannten Gründen auf gleiche Länge erweitert werden (align). Die Korrektheit für negative Zahlen ergibt sich aus dem Prinzip der Darstellung (siehe oben), wir können Addition und Subtraktion sowie die Negation sofort installieren:
01 -- Installieren des ArbInt-Typen für Addition, Subtraktion und Negation
02 instance Num ArbInt where
03 x + y = norm (zippWith (+) (align (digits x,digits y)))
04 x - y = norm (zippWith (-) (align (digits x,digits y)))
05 negate x = norm . map neg . digits
06 where neg x = -x
|
2-6.txt |
Codebeispiel 19
negate macht aus einer positiven Zahl eine negative und vice versa. Das Prinzip ist, alle Ziffern mit negativem Vorzeichen zu versehen und die entstehende Liste zu normalisieren. Die Normalisierung führt zur Komplementdarstellung.
Multiplikation
Die Implementierung der Multiplikation wird auf dem klassischen Prinzip der schriftlichen Multiplikation aufbauen: Jede Ziffer wird mit dem Faktor multipliziert, die entstehenden Produkte werden zum Ergebnis aufsummiert. Da wir bereits über eine Implementierung der Addition über dem ArbInt-Typen verfügen, benötigen wir in erster Linie eine Funktion zur Ermittlung der Teilprodukte. Diese Funktion übernimmt als Parameter die beiden Faktoren und liefert die Teilprodukte als Liste von ArbInts (adäquat für die Addition). Das Prinzip ist die Transformation des 1. Faktors in eine Digit-Liste und anschließende Anwendung der Funktion mult1 auf jedes Digit. mult1 wird mit dem 2. Faktor parametrisiert und liefert das Produkt aus dem Digit und dem Faktor als ArbInt (d.h., mult1 führt auch die notwendige Normalisierung durch):
01 -- Erstellen einer Liste von Teilprodukten
02 sums :: ArbInt -> ArbInt -> [ArbInt]
03 sums x y = map (mult1 x) (digits y)
04
05 -- Einen ArbInt mit einer Ziffer multiplizieren
06 mult1 :: ArbInt -> Digit -> ArbInt
07 mult1 x d = norm (map (*d) (digits x))
|
2-7.txt |
Codebeispiel 20
Abschließend muß die Aufsummierung der Teilprodukte aus sums auf die Additions-Operation über ArbInt zurückgeführt werden. Die Teilprodukte müssen dazu geshiftet werden (das Produkt nach links verschieben und rechts mit Nullen auffüllen), um die Wertigkeit der jeweiligen Stelle zu berücksichtigen. Diese Leistung erbringt die schlußendliche Definition der ArbInt-Multiplikation. Diese faltet die Funktion splus von links ausgehend und beginnend mit dem Wert 0 in die Liste der Teilprodukte. splus addiert zwei ArbInt-Wert und shiftet den ersten zuvor um eine Stelle nach links:
01 -- Installieren des ArbInt-Typen für die Multiplikation
02 instance Num ArbInt where
03 x * y = foldl splus (Norm []) (sums x y)
04
05 -- Zwei ArbInt-Werte unter Shiften des Ersten addieren
06 splus :: ArbInt -> ArbInt -> ArbInt
07 splus x y = shift x + y
08
09 -- Einen ArbInt-Wert um eine Stelle nach links verschieben, rechts mit Nullen auffüllen
10 shift :: ArbInt -> ArbInt
11 shift (Norm xs) = if null xs then Norm [] else Norm (xs ++ [0])
|
2-8.txt |
Codebeispiel 21
Durch das Falten von links erfährt das erste Teilprodukt (entstanden aus den höchstwertigen Stellen) am Ende alle Shifts (bedingt durch den quasi-rekursiven Aufruf von splus), das niedrigwertigste Teilprodukt hingegen gar keinen.
Division
Zum Divisionsproblem versuchen wir uns im Rahmen dieser Arbeit lediglich an der Division eines ArbInt durch eine Ziffer und lassen den allgemeinen und komplizierten Fall einer Division ArbInt durch ArbInt außen vor. Das Prinzip wird dem der schriftlichen Division entsprechen, wir werden von links beginnend versuchen, jede Ziffer des ArbInt durch den Divisor zu teilen. Der ganzzahlige Teiler entspricht dabei unserem Ergebnis für diese Stelle, der Rest wird mit der Basis multipliziert und zur nächsten Ziffer addiert - mit dieser Summe wiederholt sich das Verfahren für die nächste Ziffer. Unsere Funktion quotrem1 wird dieses Verfahren umsetzen, in dem sie die Ziffernliste des ArbInt hernimmt und mit scanl jede Teilliste mit der besagten Operation (hier step1 d) faltet, beginnend mit einem Tupel (0,0). Der linke Teil des Tupels wird im Laufe der Faltung für jede Stelle den ganzzahligen Teiler anzeigen, der rechte den Rest für die entsprechende Ziffer. step1 multipliziert den bisherigen Restes mit der Basis, addiert die aktuelle Ziffer dazu und berechnet das nächste Tupel durch Division durch den Divisor bzw. Berechnung des Restes mit der Modulus-Funktion.
01 -- Division eines ArbInt durch eine Ziffer, liefert ein Tupel aus ganzzahligem Teiler und Rest
02 quotrem1 :: ArbInt -> Digit -> (ArbInt, Digit)
03 quotrem1 x d = finish1 (scanl (step1 d) (0, 0) (digits x))
04
05 -- Ein Divisionsschritt: Rest des vorigen Schrittes mit der Basis multiplizieren und Tupel mit ganzzahligem Teiler und Rest liefern
06 step1 :: Digit -> (Digit, Digit) -> Digit -> (Digit, Digit)
07 step1 d (q,r) x = (div y d, mod y d)
08 where y = base * r + x
09
10 -- Die ersten Elemente aller Tupel zu einer Ziffernliste zusammenfassen und normalisieren, das letzte zweite Element ist der Rest
11 finish1 :: [(Digit, Digit)] -> (ArbInt, Digit)
12 finish1 qrs = (norm (map fst qrs), snd (last qrs))
|
2-9.txt |
Codebeispiel 22
scanl aus quotrem1 liefert eine Liste von (Zwischen)Ergebnistupeln, deren erstes Element jeweils das Ergebnis der Stelle anzeigt. finish1 sammelt diese Elemente zu einer Ziffernliste zusammen (map fst) und normalisiert sie zu einem ArbInt. Der zweite Teil des Ergebnistupels von finish1 liefert den Rest der gesamten Division, in dem er ihn einfach vom letzten Tupel von scanl übernimmt.
Bildschirmausgabe
Zur Darstellung der ArbInt-Werte muß ArbInt als Instanz der Klasse Show installiert und die Funktion showsPrec definiert werden. showsPrec wird neben dem eigentlichen ArbInt-Parameter mit einem Int konfiguriert, der entscheidet, ob das Ergebnis geklammert wird. showsPrec übernimmt ferner einen String, der dem Ergebnis einfach angehängt wird. Die Funktion show ist auf der Grundlage von showsPrec vordefiniert (keine Klammern, keinen angehängten String) und mit deren Definierung funktionstüchtig. negative ist ein Prädikat und stellt fest, ob ein ArbInt eine negative Zahl repräsentiert. Das ist dann der Fall, wenn die Liste nicht leer (also != 0) und das erste Element der Liste negativ ist:
01 -- Vordefinierte show-Funktion auf Basis von showsPrec
02 show :: a -> String
03 show x = showsPrec 0 x []
04
05 -- Implementation von showsPrec für ArbInt
06 showsPrec :: Int -> a -> String -> String
07 instance Show ArbInt where
08 showsPrec k x
09 | isZero x = showChar ´0´
10 | negative x = showChar ´-´ . showDigits (digits (negate x))
11 | otherwise = showDigits (digits x)
12
13 -- Test auf negative Zahl
14 negative :: ArbInt -> Bool
15 negative (Norm xs) = not (null xs) && (head xs < 0)
|
2-10.txt |
Codebeispiel 23
showsPrec berücksichtigt drei Fälle: Im Normalfall werden einfach die Ziffern des ArbInt ausgegeben, ein negativer ArbInt wird negiert (also positiv gemacht) und unter Voranstellung eines Minuszeichens ausgegeben. Die leere Liste schließlich wird als Sonderfall für 0 behandelt, die Funktion terminiert in diesem Fall sofort mit der Ausgabe der Ziffer 0.
01 -- Eine Ziffernliste unter Anhängen eines anderen Strings in einen neuen String konvertieren, 1. Element ohne Alignment
02 showDigits :: [Digit] -> String -> String
03 showDigits (d:ds) = showString (show d) . showString (concat (map showDigit ds))
04
05 -- Eine einzelne Ziffer in einen String der Länge der Basis konvertieren, mit Nullen nach links auffüllen
06 showDigit :: Digit -> String
07 showDigit d = zeros ++ ds
08 where zeros = replicate (baseSize - length ds) ´0´
09 ds = show d
|
2-11.txt |
Codebeispiel 24
showDigits transformiert die erste Ziffer des ArbInt in einen String, die übrigen Ziffern werden jeweils mit showDigit in Strings transformiert, die anschließend zusammengesetzt werden. showDigit erweitert die String-Darstellung der Digits nach links um Nullen, bis die Länge der Basis b erreicht ist - eine Sonderbehandlung, die für die erste Ziffer natürlich nicht erforderlich ist.
Code generated with AusarbeitungGenerator Version 1.1, weblink