Ich wollte meinen anderen Beitrag bearbeiten, aber dieser ist groß genug für einen eigenen Beitrag.
Hier ist eine Möglichkeit, dies mit "Typmagie" zu tun, aber ich habe das Gefühl, dass es etwas suboptimal ist, da es eine Hebefunktion erfordert, die spezifisch für Funktionen mit einer bestimmten Anzahl von Argumenten ist (mehr dazu unten).
Beginnen wir mit der Definition eines rekursiven Datentyps
data RecT a = RecR a
| RecC (a -> RecT a)
Variablen vom Typ RecT können also entweder nur ein umschlossenes Ergebnis (RecR) oder eine fortgesetzte Rekursion (RecC) sein.
Wie können wir nun etwas in den Typ RecT a umwandeln?
Werte sind einfach:
valRecT x = RecR x
RecR x ist offensichtlich vom Typ RecT a.
Was ist mit einer Funktion, die nur ein Argument benötigt, wie id?
idRecT x = RecC $ \x -> RecR x
RecC umhüllt eine Funktion, die eine Variable annimmt und den Typ RecT a zurückgibt. Der Ausdruck
\x -> RecR x
ist eine solche Funktion, denn wie wir bereits festgestellt haben, ist RecR x vom Typ RecT a.
Allgemeiner ausgedrückt, kann jede Funktion mit einem Argument aufgehoben werden:
lift1RecT :: (a -> a) -> RecT a
lift1RecT fn = RecC $ \a -> RecR $ fn a
Wir können dies verallgemeinern, indem wir immer wieder tiefer verschachtelte Funktionsaufrufe in RecC einbinden:
lift2RecT :: (a -> a -> a) -> RecT a
lift2RecT fn = RecC $ \b -> RecC $ \a -> RecR $ fn b a
lift3RecT :: (a -> a -> a -> a) -> RecT a
lift3RecT fn = RecC $ \c -> RecC $ \b -> RecC $ \a -> RecR $ fn c b a
OK, wir haben also all diese Arbeit geleistet, um eine Funktion mit einer beliebigen Anzahl von Argumenten in einen einzigen Typ zu verwandeln, RecT a. Wie verwenden wir das?
Wir können eine Ebene der Funktionsanwendung leicht aufschreiben:
reduceRecT :: RecT a -> a -> RecT a
reduceRecT (RecC fn) = fn
reduceRecT _ = undefined
Mit anderen Worten: reduceRecT nimmt ein Argument vom Typ RecT a und ein weiteres vom Typ a und gibt ein neues RecT a zurück, das um eine Stufe reduziert wurde.
Wir können auch eine abgeschlossene Berechnung innerhalb einer RecT zum Ergebnis abrollen:
unrollRecT :: RecT a -> a
unrollRecT (RecR fn) = fn
unrollRecT _ = undefined
Jetzt sind wir bereit, eine Liste von Argumenten auf eine Funktion anzuwenden!
lApply :: [a] -> RecT a -> a
lApply [] fn = unrollRecT fn
lApply (l:ls) fn = lApply ls $ (reduceRecT fn) l
Betrachten wir zunächst den Basisfall: Wenn wir mit der Berechnung fertig sind, packen wir einfach das Ergebnis aus und geben es zurück. Im rekursiven Fall reduzieren wir die Argumentliste um eins und transformieren dann den fn, indem wir den Kopf der Liste auf den reduzierten fn anwenden, was zu einem neuen RecT a führt.
Versuchen wir es mal damit:
lApply [2,5] $ lift2RecT (**)
> 32.0
Was sind also die Vor- und Nachteile dieses Ansatzes? Nun, die Template-Haskell-Version kann partielle Listenanwendungen durchführen; das trifft auf die hier vorgestellte isorekursive Typenlösung nicht zu (obwohl wir das im Prinzip mit etwas Hässlichkeit beheben könnten). Die Typlösung hat auch den Nachteil, dass sie viel mehr Boilerplate-Code mit sich bringt: wir brauchen eine listNRecT für alle N, die wir verwenden wollen. Und schließlich ist es viel schwieriger, dies auf die analoge Tupellösung zu verallgemeinern, wenn wir lApply auf Funktionen mit gemischten Variablentypen anwenden wollen.
Natürlich gibt es auch eine andere interessante Möglichkeit, die Kürze zu erhöhen, indem man Template Haskell verwendet, um die listNRecT-Funktionen zu generieren; dies eliminiert zwar etwas Boilerplate, erkauft sich aber in gewisser Weise die Nachteile beider Implementierungen.
