nicht angemeldet
Camping_RIDER
Rolf B
Camping_RIDER
Rolf B
Rolf B
dedlfix
Camping_RIDER
Rolf B
Moin moin!
Ich arbeite derzeit an einer kleinen exotischen Programmiersprache. Die Sprache erlaubt nur induktive aber keine rekursiven Definitionen. In der Theorie ist das kein großes Problem, in der Praxis ist Rekursion aber häufig intuitiver zu verstehen. In diesem Informatik-Rätsel soll es darum gehen rekursiv definierte Funktionen in induktive Definitionen umzuwandeln, und zwar in JavaScript/TypeScript.
Gegeben sei der folgende Datentyp.
type Nat = Zero | Succ
class Zero {}
class Succ {
readonly pred;
constructor(pred: Nat) {
this.pred = pred;
}
}
Der Datentyp kodiert die natürliche Zahlen à la Giuseppe Peano. new Zero() repräsentiert die Null. Und wenn n eine natürliche Zahl ist, dann repräsentiert new Succ(n) ihren Nachfolger.
Diese Definition der natürlichen Zahlen ist schwierig zu debuggen, deshalb gibt es zwei Helfer-Funktionen zum Konvertieren von und zu number.
// Konvertiert eine natürliche Zahl zu `number`
function from(n:Nat) : number {
return (n instanceof Zero)
? 0
: 1 + (from(n.pred))
}
// from(new Succ(new Succ(new Succ(new Zero())))) ≈ 3
// Konvertiert eine `number` zu einer natürlichen Zahl.
function to(n:number) : Nat {
return (n === 0)
? new Zero()
: new Succ(to(n-1))
}
// to(3) ≈ new Succ(new Succ(new Succ(new Zero())))
Beide Funktionen dienen lediglich zum Debugging, und dürfen nur für diesen Zweck verwendet werden, aber nicht in der Implementierung der Operationen benutzt werden.
Der Datentyp soll die drei Operationen plus, mult und fac unterstützen. Zunächst sollen die Funktionen rekursiv definiert werden. Eine rekursive Funktion haben wir schon gesehen, und zwar from. Für plus sieht die rekursive Definition wie folgt aus:
function plus (n:Nat, m:Nat) : Nat {
return (n instanceof Zero)
? m
: new Succ(plus(n.pred, m))
}
Die erste Aufgabe soll es sein, die rekursiven Definitionen für mult und fac zu implementieren. Die Funktion mult darf dabei plus verwenden, und fac darf mult und plus verwenden. Zusätzlich dürft ihr natürlich beliebige Helfer-Funktionen implementieren.
Der zweite Aufgabenteil ist wesentlich anspruchsvoller. An den rekursiven Definitionen lässt sich ein Muster erkennen: Es gibt immer einen Basisfall und einen rekursiven Fall. Das Verhalten lässt sich zu einem Induktions-Schema verallgemeinern. Das gibt uns die folgende Funktion natE (kurz für Natural-Number-Elimination).
function natE<a>(base: a, step: ((x:a) => a), n:Nat) : a {
return (n instanceof Zero)
? base
: step(natE(base, step, n.pred))
}
Die Funktion nimmt einen Startwert base entgegen, der das Ergebnis im Basisfall zurückliefert. Der zweite Parameter ist eine step-Funktion für den Induktionsschritt. Die step-Funktion bekommt einen Zwischenwert übergeben und berechnet daraus einen Nachfolger-Wert. Der dritte Parameter ist die Induktions-Variable.
Damit lässt sich eine induktive Definition für plus wie folgt angeben:
function plusE(n:Nat, m:Nat) : Nat {
const base = m;
const step = (x:Nat) => new Succ(x)
return natE<Nat>(base, step, n);
}
Im zweiten Aufgabenteil sollen die induktiven Definitionen für mult und fac implementiert werden.
Wer Schwierigkeiten bei einer Aufgabe hat muss nicht gleich aufgeben. Tipps gibts per PN. Insbesondere für die induktive Definition der Fakultäts-Funktion muss man einen kleinen Trick anwenden.
Zur Bearbeitung der Aufgabe habe ich eine Vorlage bei Stackblitz erstellt. Auf diese Weise müsst ihr euch kein TypeScript installieren und könnt die Aufgaben einfach im Browser lösen. Wer kein TypeScript mag, darf natürlich die Typ-Annotation auch einfach löschen, aber ich würde empfehlen sie beizubehalten, das hilft dabei die Schritt-Funktion korrekt hinzufriemeln.
Aloha ;)
Fertig - siehe PN!
Interessant, dass Typescript mit dem induktiven Ansatz offenbar nicht so gut klarkommt - zumindest bei meiner Implementierung von facE ist der zur Verfügung stehende Stack offenbar schon bei facE(8) vollgelaufen.
Weiß jetzt nicht, ob ich selbst irgendwo zu ineffizient war, oder ob das tatsächlich so ist.
Grüße,
RIDER
Interessant, dass Typescript mit dem induktiven Ansatz offenbar nicht so gut klarkommt - zumindest bei meiner Implementierung von facE ist der zur Verfügung stehende Stack offenbar schon bei facE(8) vollgelaufen.
Weiß jetzt nicht, ob ich selbst irgendwo zu ineffizient war, oder ob das tatsächlich so ist.
Das liegt vermutlich an der schlechten Implementierung von natE - also mein Fehler. Ich hätte natE tail-rekursiv schreiben können, dann würde der Stack überhaupt nicht wachsen. Mal sehen, ob ich das noch hinbekomme.
Hallo 1unitedpower,
ist ja schön, dass wenigstens einer Dir nach Böhmen folgen konnte.
Die Grundidee habe ich ja - hoffe ich - verstanden. Man kennt das aus den Einführungen in Berechenbarkeitstheorie, wo alles auf plus 1, minus 1 und Test auf 0 zurückgeführt wird.
Aber ansonsten ist dein Rätsel für mich ein Konglomerat aus reinem Unsinn.
Es fängt schon damit an, dass ich einen Knoten in den Kopf bekomme wenn ich deine Debug-Helper sehe. Die Semantik von to und from ist genau vertauscht, ist das deine Art, ein Rätsel auf lustige Art noch rätselhafter zu machen? Aber das kann man immerhin noch schnell ändern.
Aber wenn an so einer einfachen Stelle schon unsere geistige Inkompatibilität beginnt, muss ich mich nicht wundern, wenn danach ganz Schluss ist.
Spätestens bei natE frage ich mich, was das überhaupt grundsätzlich soll. Eine rekursive Funktion, die dazu dient, Rekursion durch Induktion zu ersetzen - äh, wie? Ich fühle mich ver...gackeiert.
Rolf
Aloha ;)
Es fängt schon damit an, dass ich einen Knoten in den Kopf bekomme wenn ich deine Debug-Helper sehe. Die Semantik von to und from ist genau vertauscht, ist das deine Art, ein Rätsel auf lustige Art noch rätselhafter zu machen? Aber das kann man immerhin noch schnell ändern.
Ich halte sowas für verzeihbar und einfach kompensierbar. Wie soll eine Konvention da aussehen - je nachdem wie man die Sache dreht wird's entweder "richtig" oder "falsch".
Die hier zugrundegelegte Logik war wohl: from konvertiert vom Objekt-Datentyp zum primitiven Typ, und to konvertiert zum Objekt-Datentyp vom primitiven Typ. Ob das jetzt intuitiver ist als andersrum, oder ob das andersrum intuitiver ist, darüber lässt sich wahrlich streiten - denn es waren ja auch keine Objekt-Methoden, sondern einfache Funktionen.
Zum Tragen kommt das eh nur in der (Test-)Ausgabe.
Aber wenn an so einer einfachen Stelle schon unsere geistige Inkompatibilität beginnt, muss ich mich nicht wundern, wenn danach ganz Schluss ist.
Spätestens bei natE frage ich mich, was das überhaupt grundsätzlich soll. Eine rekursive Funktion, die dazu dient, Rekursion durch Induktion zu ersetzen - äh, wie? Ich fühle mich ver...gackeiert.
Der erste Aufgabenteil ist eine Standard-Aufgabe - kam bei mir genau so vor mit Haskell in den Übungen zur Standard-Vorlesung zur Einführung in funktionale Programmierung. Das ist weder ein Konglomerat aus Unsinn, noch Raketenwissenschaft, sondern Grundlagenwissen für Informatiker.
Der zweite Aufgabenteil ist eine Abstraktion und funktioniert mit Hirnschmalz gut, wenn man den ersten Aufgabenteil geknackt hat. multE ist mit einem nur kleinen Hindernis einfach zu finden. Für facE brauchts Hirnschmalz, vielleicht Zettel und Stift, und einen kreativen Umgang mit der relativ unspezifischen Definition von natE (das nur als kleiner Hinweis in die richtige Richtung).
Probiers doch einfach mal aus - einfach die verlinkte Vorlage forken und dann mal drauflosprobieren!
Grüße,
RIDER
Hallo Camping_RIDER,
Grundlagenwissen für Informatiker.
Ja. Das ist es wohl. Ich bin aber keiner. Ich bin Anwendungsentwickler, und habe das Informatikstudium vor dem Vordiplom beendet. Unter anderem deshalb, weil mir 2 Semester Theoretische Informatik klargemacht haben, dass Informatik und Softwareentwicklung zwei ganz verschiedene Dinge sind.
Probiers doch einfach mal aus
Darauf werde ich meine Zeit mit Sicherheit nicht verschwenden.
Rolf
Aloha ;)
Probiers doch einfach mal aus
Darauf werde ich meine Zeit mit Sicherheit nicht verschwenden.
Tja, so gehts mir meistens mit den Mathematik-Rätseln, und das obwohl ich studierter Mathematiker bin.
Schätze das hat einfach damit zu tun, ob man von einem Rätsel getriggert wird oder eben nicht.
Grüße,
RIDER
Aber ansonsten ist dein Rätsel für mich ein Konglomerat aus reinem Unsinn.
Es fängt schon damit an, dass ich einen Knoten in den Kopf bekomme wenn ich deine Debug-Helper sehe. Die Semantik von to und from ist genau vertauscht, ist das deine Art, ein Rätsel auf lustige Art noch rätselhafter zu machen? Aber das kann man immerhin noch schnell ändern.
Damit habe ich mich selber auch getrollt - guck nicht die in Bearbeitungs-Historie meines Beitrags.
Aber wenn an so einer einfachen Stelle schon unsere geistige Inkompatibilität beginnt, muss ich mich nicht wundern, wenn danach ganz Schluss ist.
Spätestens bei natE frage ich mich, was das überhaupt grundsätzlich soll. Eine rekursive Funktion, die dazu dient, Rekursion durch Induktion zu ersetzen - äh, wie? Ich fühle mich ver...gackeiert.
Es soll ja nur ein Puzzle sein. Ich wollte für die Aufgabe eine Programmiersprache wählen, mit der die meisten Selfler vertraut sind. Aber weder PHP noch JavaScript unterstützen induktive Definitionen von Haus aus. Deshalb musste ich es simulieren. natE mag ungewohnt erscheinen, aber ich gehe jede Wette ein, dass du schon mal Array.prototype.reduce benutzt hast. Das ist praktisch eine noch allgemeinere Version von natE für Listen, statt für natürliche Zahlen.
Das liegt vermutlich an der schlechten Implementierung von
natE- also mein Fehler. Ich hättenatEtail-rekursiv schreiben können, dann würde der Stack überhaupt nicht wachsen. Mal sehen, ob ich das noch hinbekomme.
Die tail-rekursive Variante muss noch warten, aber ich habe in der Zwischenzeit eine iterative Variante entwickelt, die das Problem umschifft.
function natE<a>(base: a, step: ((x:a) => a), n:Nat) : a {
let acc = base;
let i = n;
while (i instanceof Succ) {
acc = step(acc);
i = i.pred;
}
return acc;
}
Dabei hat sich dann herausgestellt, dass from mitverantwortlich für den Fehler ist.
function from (n:Nat) : number {
const base = 0;
const step = (x:number) => x+1;
return natE<number>(base, step, n);
}
Mit diesen beiden Definitionen wächst der Callstack jetzt nicht mehr an. In der Vorlage lasse ich aber die alten Definitionen stehen, ich glaube die sind etwas intuitiver. Und in der Aufgabe geht es schließlich auch im Rekursion.
Das liegt vermutlich an der schlechten Implementierung von
natE- also mein Fehler. Ich hättenatEtail-rekursiv schreiben können, dann würde der Stack überhaupt nicht wachsen. Mal sehen, ob ich das noch hinbekomme.Die tail-rekursive Variante muss noch warten, aber ich habe in der Zwischenzeit eine iterative Variante entwickelt, die das Problem umschifft.
Die tail-rekursive Variante habe ich jetzt auch.
function natE<a>(acc:a, step: ((x:a) => a), n:Nat) : a {
return (n instanceof Zero)
? acc
: natE(step(acc), step, n.pred);
}
Aber leider ist nur Safari in der Lage dazu die Tail-Calls zu optimieren. Das heißt in allen anderen Browser kommt es trotzdem zu einem Stackoverflow. Schade.
Hallo 1unitedpower,
mit der iterativen Version von natE komme ich auch weiter.
Es liegt vielleicht an meiner Implementation, aber bei mir ist das Timing von multE nicht symmetrisch. multE(3, 1000) läuft schneller als multE(1000, 3). Bei meinen Tests zur Fakultät hieß das:
| Rechnung | Gut | Schlecht |
|---|---|---|
| 4! | <2ms | <2ms |
| 5! | <2ms | <2ms |
| 6! | 3ms | 5ms |
| 7! | 6ms | 41ms |
| 8! | 24ms | 1853ms |
| 9! | 176ms | ♾️ |
| 10! | 2317ms | |
| 11! | 34000ms |
Die 12! mit dem besseren Zweig habe ich mir dann verkniffen.
Ich habe dann noch zum Testen die multE Funktion durch eine Integer-Multiplikation und to(wert) ersetzt. from(nat) hatte ich ja schon - wie anderswo geschrieben, durch das debugValue Property gepimpt. Die to-Implementierung habe ich iterativ gemacht, ohne Rekursion, ohne natE, also die Succ-Kette so schnell wie möglich aufgebaut. Damit sank 11! von 34 auf 7 Sekunden. Aber 12! Fakultät ließ sich nicht mehr berechnen, Chrome hat mir auf einmal das Script beendet und einen traurigen Smiley gezeigt 😂
Rolf
Tach!
Interessant, dass Typescript mit dem induktiven Ansatz offenbar nicht so gut klarkommt - zumindest bei meiner Implementierung von facE ist der zur Verfügung stehende Stack offenbar schon bei facE(8) vollgelaufen.
Typescript ist nur ein Transpiler nach Javascript. Der resultierende Code ist je nach Zielversion von Javascript oftmals derselbe Code mit entfernter Typisierung (je meoderner desto gleicher). Die Geschwindigkeit hängt also vom Algorithmus ab und nicht von Typescript an sich.
dedlfix.
Aloha ;)
Interessant, dass Typescript mit dem induktiven Ansatz offenbar nicht so gut klarkommt - zumindest bei meiner Implementierung von facE ist der zur Verfügung stehende Stack offenbar schon bei facE(8) vollgelaufen.
Typescript ist nur ein Transpiler nach Javascript. Der resultierende Code ist je nach Zielversion von Javascript oftmals derselbe Code mit entfernter Typisierung (je meoderner desto gleicher).
Das ist mir grundsätzlich klar.
Die Geschwindigkeit hängt also vom Algorithmus ab und nicht von Typescript an sich.
Es ging nicht um die Geschwindigkeit - sondern es ist so, dass sich das Skript tatsächlich mit Fehler verabschiedet, wenn ich meine facE-Methode mit einem Parameter >= 8 aufrufe, mit Fehlermeldung: Maximum call stack size exceeded. @1unitedpower vermutet den Fehler in einer ineffizienten Implementierung der (vorgegebenen) Funktion natE.
Ich will den Link zu meiner Lösung noch nicht teilen, bevor @1unitedpower das Rätsel auflöst, bzw. den Link zu meiner Lösung dann mit rausgibt.
Grüße,
RIDER
Hallo Camping_RIDER,
ok, ich fühlte mich herausgefordert 😀
Mich hat allerdings an der Aufgabe genervt, dass der Typ "Nat" Operatoren als externe Funktionen implementieren soll, was mit sich bringt, dass man ständig Typabfragen machen muss. Das ist nicht objektorientiert. Ich habe die Implementierung daher in Methoden statt Funktionen geändert, delegiere fleißig und kann so Polymorphie statt Typabfragen nutzen.
Allerdings zerstöre ich so wohl jeden Gedanken an eine Tailrekursion. Ob die mit einer function-Implementierung eher möglich ist? Vielleicht verstehe ich Tailrekursion ja auch nicht.
function sum1To(n) {
return n == 0 ? 0 : n + sum1To(n-1);
}
Das ist eine rekursive Version der "Summe von 1-n" Schleife, selbst da wüsste ich nicht wie man das tail-rekursiv machen soll weil ja das Ergebnis der vorigen Rekursion noch verarbeitet werden muss. Jedenfalls komme ich da bis n=11379 bevor der Stack überläuft.
Was ist hiermit:
function bar(sum: number, n: number) : number {
return n == 0 ? sum : bar(sum + n, n-1);
}
DAS sollte doch tail-rekursiv sein; aber von wegen - da bricht schon bei 10431 ab. Also noch anders:
function bar(sum: number, n: number) : number {
if (n == 0) return sum;
sum += n;
n--;
return bar(sum, n);
}
Nun komme ich bis 12517, bevor der Stack überläuft. Das war Chrome 81 - welche JS Engine kennt denn überhaupt Tailrekursion?!
Die Funktion from (oder to?), die den numerischen Wert eines Nat ausgibt, hielt ich - weil ja DEBUG - auch nicht für so toll und ich habe den Objekten daher ein Property debugValue gegeben. Und eine Minus-Operation habe ich auch eingebaut - aber die poste ich nicht.
Aufgabe für euch: Baut "Minus", aber bitte ohne Typtests, nur mit Polymorphie.
Dass ich hier eine mögliche rekursive Lösung für Aufgabe 1 poste, sollte wohl ok sein - der induktive Teil ist ja das Kernproblem.
class Zero {
readonly debugValue: number = 0;
plus(m: Nat) : Nat { return m; }
mult(m: Nat) : Nat { return new Zero(); }
fac() : Nat { return new Succ(new Zero()); }
}
class Succ {
readonly pred: Nat;
readonly debugValue: number;
constructor(pred: Nat) {
this.pred = pred;
this.debugValue = pred.debugValue + 1;
}
plus(m: Nat) : Nat { return this.pred.plus(new Succ(m)); }
mult (m: Nat) : Nat { return m.plus(this.pred.mult(m)); }
fac() : Nat { return this.mult(this.pred.fac()); }
}
Diese Lösung bricht bei to(9).fac() ebenfalls ab. Es ist egal, ob man this.mult(this.pred.fac()) oder this.pred.fac().mult(this) rechnet - die auf Addition zurückgeführte Multiplikation bringt beim Berechnen von 403209 oder 940320 einen Stackoverflow.
Die induktive Lösung muss ich noch anschauen. Ich muss vermutlich erstmal kapieren, was "induktiv" im Gegensatz zu "iterativ" überhaupt bedeuten soll...
Rolf
Korrekte Lösungen habe ich von @Camping_RIDER und @Rolf b erhalten. Camping_RIDERs Lösung entspricht ziemlich genau meiner Lösung, die ich unten vorstelle. Rolf hat dagegen eine objektorientierte Lösung abgegeben und noch eine Zusatzaufgabe gestellt.
Aber bevor ich die Lösungen vorstelle, möchte ich nochmal kurz auf die Motivation eingehen. Oftmals sind induktive Lösungen effizienter als rekursive Lösungen. Das sieht man gut an der Fibonacci-Reihe:
function fib(n:number) : number {
return (n <= 1) ? n : fib(n - 2) + fib(n - 1);
}
function fibE(number) : number{
const base:[number,number] = [0, 1];
const step = ([n,m]:[number,number]):[number,number] => [m, n + m];
return natE<[number,number]>(base, step, n)[0];
}
Die erste Funktion hat eine Laufzeit-Schranke von O(2^n) und einen Speicherbedarf von O(n) für den Stack. Die zweite Variatne dagegen braucht nur O(n) Operationen und hat einen Speicherverbrauch von O(1). Das ist noch nicht das Optimum zur Berechnung der Fibonacci-Reihe, aber schon deutlich besser.
Oft wird Induktion auch als guter Programmierstil empfunden: Induktion ist gewissermaßen eine eingeschränkte Variante von allgemeiner Rekursion. Das ist ein bißchen vergleichbar mit dem goto-Konstrukt von imperativen Programmiersprachen: Stukturierte Programmierung mit while und for wird als guter Stil betrachtet, obwohl sich die selbe Funktionalität auch mit dem goto-Statement relaisieren ließe.
In der Praxis wird Induktion benutzt, um allgemeine Rekursion in funktionalen Programmiersprachen zu implementieren. Ein Induktions-Schema wird hier häufig als Eliminator bezeichnet. In der Theorie spielt Induktion zudem eine Rolle, um die kategorische Semantik von Programmiersprachen zu beschreiben. Hier ist der Begriff catamorphism geläufiger. Manche Programmiersprachen sind sogar schon so weit entwickelt, dass sie es den Programmierer*innen erlauben Eigenschaften ihrer Programme innerhalb der Sprache zu beweisen. Induktion ist hier das bevorzugte Verfahren, um Eigenschaften über rekursive Definitionen zu beweisen.
Gefragt war nach rekursiven Implementierungen von mult und fac.
function mult (n:Nat, m:Nat) : Nat {
return (n instanceof Zero)
? new Zero
: plus(m, mult(n.pred, m))
}
function fac(n:Nat) : Nat {
return (n instanceof Zero)
? new Succ(new Zero())
: mult(n, fac(n.pred))
}
In diesem Aufgabenteil war nach induktiven Implementierungen der selben zwei Funktionen gefragt.
function multE(n:Nat, m:Nat) : Nat {
const base = new Zero();
const step = (x:Nat) => plusE(x, m);
return natE<Nat>(base, step, n);
}
function facE(n:Nat) : Nat {
const one = new Succ(new Zero());
const base:[Nat,Nat] = [one, one];
const step = ([i,m]:[Nat,Nat]) : [Nat,Nat] => [new Succ(i), mult(i, m)];
return natE<[Nat,Nat]>(base, step, n)[1];
}
Für facE brauchte man einen Trick. Um die nächste Zahl der Reihe zu berechnen, reicht es nicht aus nur die vorherige Zahl zu kennen. Wir müssen außerdem wissen, mit welcher Zahl wir die vorherige Zahl multuplizieren müssen. Das heißt wir müssen uns merken, die wievielte Zahl der Reihe wir gerade berechnen. Dazu braucht die step-Funktion einen zusätzlichen Zähl-Paramter, und im Ergebnis muss sie den neuen Zählerstand zusätzlich zum Ergebnis liefern.
@Rolf b hat uns herausgefordert die Subtraktion zu implementieren und zwar nicht funktional, sondern objektorientiert. Ich habe es trotzdem zuerst funktional gemacht und dann zu OOP konvertiert.
function minus(n:Nat, m:Nat) : Nat {
const r = (n instanceof Zero && m instanceof Succ)
? new Error('Cannot subtract a larger number from a smaller one.')
: (n instanceof Zero) ? new Zero()
: (m instanceof Zero) ? n
: minus(n.pred, m.pred);
if (r instanceof Error) {
throw r;
}
return r;
}
function minusOne(n:Nat) : Nat {
if (n instanceof Zero) {
throw new Error('Cannot subtract a larger number from a smaller one.')
}
return n.pred;
}
function minusE(n:Nat, m:Nat) : Nat {
const base = n;
const step = minusOne;
return natE<Nat>(base, step, m);
}
Interessant an der Subtraktion fand ich vor allem zwei Aspekte: 1) Subtraktion ist eine partielle Funktion auf den natürlichen Zahlen 2) Man rekursiert/induziert über den zweiten Operanden. Das war in der OOP-Variante für mich besonders tricky.
Meine OOP-Lösung in einem Stück:
type Nat = Zero | Succ;
class Zero {
readonly debugValue: number = 0;
// Recursion
assertZero(error) : void {
};
plus(m: Nat) : Nat {
return m;
}
minusI(m: Nat) : Nat {
return m;
}
minus(m: Nat) : Nat {
m.assertZero(new Error("Cannot subtract a larger number from a smaller one"));
return new Zero();
}
mult(m: Nat) : Nat {
return new Zero();
}
fac() : Nat {
return new Succ(new Zero());
}
// Induction
elim<a>(base: a, step: (x:a) => a) {
return base;
}
plusE(m: Nat) : Nat {
return m;
}
multE(m: Nat) : Nat {
return new Zero();
}
minusOne() : Nat {
throw new Error("Cannot subtract a larger number from a smaller one");
}
minusE(m: Nat) : Nat {
m.assertZero(new Error("Cannot subtract a larger number from a smaller one"));
return new Zero();
}
}
class Succ {
readonly pred: Nat;
readonly debugValue: number;
constructor(pred: Nat) {
this.pred = pred;
this.debugValue = pred.debugValue + 1;
}
// Recursion
assertZero(error) : void {
throw error;
}
plus(m: Nat) : Nat {
return this.pred.plus(new Succ(m));
}
minusI(m: Nat) : Nat {
return m.minusI(this.pred);
}
minus(m: Nat) : Nat {
return m.minusI(this);
}
mult (m: Nat) : Nat {
return m.plus(this.pred.mult(m));
}
fac() : Nat {
return this.mult(this.pred.fac());
}
// Induction
elim<a>(base: a, step: (x:a) => a) : a {
let acc = base;
let i:Nat = this;
while (i instanceof Succ) {
acc = step(acc);
i = i.pred;
}
return acc;
}
plusE(m: Nat) : Nat {
const base = (new Zero()).plusE(m);
return this.elim(base, (n:Nat) => new Succ(n));
}
multE(m: Nat) : Nat {
const base = (new Zero()).multE(m);
return this.elim(base, (n:Nat) => n.plus(m))
}
minusOne() : Nat {
return this.pred;
}
minusE(m: Nat) : Nat {
return m.elim(this, (n:Nat) => n.minusOne());
}
}
Im Vergleich von FP und OOP Lösungen fallen zwei Dinge auf: In der FP Lösungen stehen die Algorithmen zusammen, in der OOP Lösungen stehen dagegen die Basis-Fälle und die Induktiven-Fälle zusammen. Beides hat Vor- und Nachteile: Wenn eine neue Operation implementiert werden muss, muss im Falle von FP kein existierender Code angepasst werden. Bei OOP müsste man dafür nichts anpassen, wenn eine neue Klasse zum Datentype hinzugefügt werden würde.