Lösung

[1unitedpower]

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.

1. Aufgabenteil: Rekursion

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

2. Aufgabenteil: Induktion

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.

3. Zusatzaufgabe von Rolf. Subtraktion

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