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. ~~~typescript 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](https://en.wikipedia.org/wiki/Natural_number#Peano_axioms). `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`. ~~~typescript // 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. # 1. Aufgabenteil - Rekursion 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: ~~~typescript 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. # 2. Aufgabenteil - Induktion 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). ~~~typescript 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: ~~~typescript 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](https://stackblitz.com/edit/typescript-uzvxdx) 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.

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. ~~~typescript 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](https://en.wikipedia.org/wiki/Natural_number#Peano_axioms). `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`. ~~~typescript // Konvertiert eine natürliche Zahl zu `number` function from(n:Nat) : number { return (n instanceof Zero) ? 0 : 1 + (from(n.pred)) } // from(3) ≈ new Succ(new Succ(new Succ(new Zero()))) // Konvertiert eine `number` zu einer natürlichen Zahl. function to(n:number) : Nat { return (n === 0) ? new Zero() : new Succ(to(n-1)) } // to(new Succ(new Succ(new Succ(new Zero())))) ≈ 3 ~~~ 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. # 1. Aufgabenteil - Rekursion 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: ~~~typescript 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. # 2. Aufgabenteil - Induktion 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). ~~~typescript 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: ~~~typescript 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](https://stackblitz.com/edit/typescript-uzvxdx) 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.

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. ~~~typescript 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](https://en.wikipedia.org/wiki/Natural_number#Peano_axioms). `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`. ~~~typescript // Konvertiert eine natürliche Zahl zu `number` function from(n:Nat) : number { return (n instanceof Zero) ? 0 : 1 + (toNumber(n.pred)) } // from(3) ≈ new Succ(new Succ(new Succ(new Zero()))) // Konvertiert eine `number` zu einer natürlichen Zahl. function to(n:number) : Nat { return (n === 0) ? new Zero() : new Succ(fromNumber(n-1)) } // to(new Succ(new Succ(new Succ(new Zero())))) ≈ 3 ~~~ 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. # 1. Aufgabenteil - Rekursion 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: ~~~typescript 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. # 2. Aufgabenteil - Induktion 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). ~~~typescript 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: ~~~typescript 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](https://stackblitz.com/edit/typescript-uzvxdx) 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.