Haskell: Unendliche Liste, wenn die Ganzzahl zur Stapelimplementierung verschoben wird
Ich versuche, einen einfachen Stapel zu implementieren, bin aber verwirrt darüber, warum ich eine unendliche Liste erhalte, wenn ich eine Ganzzahl in den Stapel schiebe.
Alle anderen Funktionen funktionieren wie erwartet, aber ich verstehe das Problem mit nicht push. Es geht schief, wenn ich versuche, sich selbst einen leeren Stapel zuzuweisen, der eine Variable wie die folgende verschoben hat:
λ > a = makeStack
λ > push 3 a
[3]
λ > a
[]
λ > a = push 3 a
λ > a
[3,3,3,3,3,3,3,3,3,3^CInterrupted.
type Stack a = [a]
makeStack :: Stack a
makeStack = []
push :: a -> Stack a -> Stack a
push a as = (a:as)
Antworten
Haskell erlaubt keine Mutation. Wenn Sie in einer Quelldatei eine Variable definieren aund dann versuchen, sie wie hier neu a = push 3 azuzuweisen, wird ein Kompilierungsfehler angezeigt. Der einzige Grund, warum Sie dies nicht tun, ist, dass Sie in GHCi arbeiten, wodurch Sie Variablen neu definieren können. Dies ist nur eine Annehmlichkeit, sodass Sie sich beim Experimentieren mit verschiedenen Definitionen nicht ständig neue Namen ausdenken müssen.
Und entscheidend ist, dass a = push 3 aes keinen neuen Wert gibt, ader auf dem vorherigen basiert, wie es in einer zwingenden Sprache der Fall wäre. Stattdessen ist es eine Definition a von sich selbst .
Deshalb erhalten Sie eine unendliche Liste - Ihre Definition wird wie folgt verarbeitet:
a = push 3 a
= 3:a
= 3:(push 3 a)
= 3:(3:a)
und so weiter. Aufgrund der Faulheit von Haskell gibt es kein Problem mit einer Definition wie dieser - GHCi berechnet, wenn Sie wie hier nach der vollständigen Liste fragen, einfach jeweils ein Element und druckt daher 3s weiter, bis Sie ihm sagen, dass er aufhören soll.
Um das zu erhalten, was Sie möchten, müssen Sie entweder nur eingeben push 3 aoder, wenn Sie ihm einen Namen zuweisen müssen, einfach einen anderen Namen auswählen a. b = push 3 agefolgt von bwird sich wie erwartet verhalten.
Es gibt (ich denke, fast) keine veränderlichen Variablen (dank @amalloy für die Korrektur meiner Terminologie) in haskell.
Wenn Sie so etwas schreiben:
x = f x
Es tritt in eine Endlosschleife ein: f (f (f ...
Es gibt also keinen Wert in der Vergangenheit , ain den 3gedrückt werden kann.
Daher müssen Sie einen push 3 aanderen Wert eingeben (oder direkt in das ghci).
Eine solche Schleife kann jedoch manchmal nützlich sein. Schauen Sie sich an Data.Function.fix:
fix :: (a -> a) -> a
fix f = let x = f x in x
Es kann verwendet werden, um dasselbe zu tun wie Sie:
GHCi> fix (push 3)
[3,3,3,3,^CInterrupted.
Die Endlosschleife ist jedoch nicht immer der Fall. Schau mal:
factFun rec n = if n == 0 then 1 else n * rec (n - 1)
Diese Funktion sieht möglicherweise faktoriell aus, der rekursive Aufruf im nicht terminierenden Zweig wird jedoch durch einen Dummy ( rec) ersetzt. Wir möchten, dass dieser Dummy factFunimmer und immer wieder ersetzt wird, um die Fakultät zu erhalten. fixmacht dies:
GHCi> fix factFun 4
24
Hinweis: Ich werde meinen Kommentar hier duplizieren: Wenn der Leser noch nichts davon weiß fix, möchte ich ihn zu einer langen und interessanten Reise einladen. Ich schlage vor, sie beginnen mit diesem Wikibook über die Denotationssemantik .