1unitedpower: Informatik zum Donnerstag

Beitrag lesen

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.

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:

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).

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.