Gibt es eine Möglichkeit, Ergebnisse in Haskell zu "konservieren"?

Question

Ich bin neu bei Haskell und verstehe, dass es (im Grunde) eine reine funktionale Sprache ist, was den Vorteil hat, dass sich die Ergebnisse der Funktionen über mehrere Auswertungen hinweg nicht ändern. Angesichts dessen frage ich mich, warum ich eine Funktion nicht einfach so markieren kann, dass sie sich die Ergebnisse ihrer ersten Auswertung merkt und nicht jedes Mal, wenn ihr Wert benötigt wird, erneut ausgewertet werden muss.

In Mathematica zum Beispiel gibt es eine simple idiom um dies zu erreichen:

f[x_]:=f[x]= ... 

aber in Haskell, die nächsten Dinge, die ich gefunden habe, ist something like

f' = (map f [0 ..] !!) 
    where f 0 = ... 
     f n = f' ... 

die zusätzlich zu der viel weniger klar (und scheinbar auf Int Argumente beschränkt?) nicht Ergebnisse in einer interaktiven Sitzung (scheint) zu bewahren.

Zugegeben (und klar), ich verstehe nicht genau, was hier vor sich geht; aber naiv, wie es scheint, Haskel sollte eine gewisse Art und Weise haben, bei der Definition der Funktion Ebene von

• Vorteil der Tatsache, dass seine Funktionen sind Funktionen und das Überspringen Neuberechnung ihrer Ergebnisse, sobald sie berechnet wurden und
• , was den Wunsch anzeigt, dies auf Ebene der Funktionsdefinition mit einem einfachen und sauberen Idiom zu tun.

Gibt es eine Möglichkeit, dies in Haskell zu erreichen, die ich vermisse? Ich verstehe (so), dass Haskell die Bewertungen nicht als "Zustand" speichern kann, aber warum kann er ausgewertete Funktionen nicht einfach (in Wirklichkeit) als ihren berechneten Wert definieren?

---

Dies erwächst aus this question, bei dem Fehlen dieser Funktion führt zu schrecklichen Leistung.

Answer 1

Verwenden Sie eine geeignete Bibliothek, z. B. MemoTrie.

import Data.MemoTrie 

f' = memo f 
where f 0 = ... 
     f n = f' ... 

Das ist kaum weniger schön als die Mathematica-Version, oder?

---

In Bezug auf

“ warum kann es nicht einfach (in der Tat) ausgewertet Funktionen neu zu definieren ihr berechneter Wert sein? ”

Nun, es ist nicht so einfach im Allgemeinen. Diese Werte müssen irgendwo gespeichert werden. Selbst für eine Int -bewertete Funktion können Sie nicht einfach ein Array mit allen möglichen Werten zuweisen – es würde nicht in den Speicher passen. Die Listenlösung funktioniert nur, weil Haskell träge ist und daher unendliche Listen erlaubt, aber das ist nicht besonders befriedigend, da die Suche O (n) ist. Für andere Typen ist es einfach hoffnungslos – Sie müssten irgendwie eine überzählbar unendliche Domäne diagonalisieren.

Sie brauchen eine klügere Organisation. Ich weiß nicht, wie Mathematica das tut, aber es verwendet wahrscheinlich eine Menge von “ proprietären Magie ”. Ich wäre nicht so sicher, dass es wirklich so funktioniert, wie Sie es möchten, für irgendwelche Eingaben.

Haskell hat zum Glück Typklassen, mit denen Sie genau ausdrücken können, was ein Typ braucht, um schnell memotierbar zu sein. HasTrie ist so eine Klasse.