Undendliche rekursive Strukturen und Haskell

Hallo zusammen,

folgender Code gegeben:

data Tree a = Sentinel | Node a (Tree a) (Tree a)
infTree = Node 10 infTree Sentinel

Wenn ich jetzt in ghci eine Tiefensuche nach einem Element ungleich 10 durchführe, gerate ich nachvollziehbarerweise in eine Endlosrekursion.
Gibt es einen technischen Grund dafür, dass Haskell nicht feststellt, dass sich auf der rechten Seite der rekursiven Definition nichts ändern kann und deswegen nicht nach dem ersten Rekursionsschritt abrricht?

knivil

Ja. Die Frage ist aber nicht auf Haskell beschraenkt: Wie kann festgestellt werden, ob ein Programm in einen identischen Zustand gelangt? Lohnt der Aufwand?

Nunja, was heißt schon "in einen identischen Zustand gelangen", wenn Zustandsänderungen von der Sprache nicht vorgesehen sind (bzw. expliziert werden müssen).
infTree ist eine Konstante. Da kann sich nichts ändern. Das zu erkennen erfordert (aus meiner naiven Sicht) nur das Wissen darüber, dass infTree nullstellig ist und keine Seiteneffekte hat.
Ob sich der Aufwand lohnt weiß ich nicht. Das war mehr oder weniger ja auch meine Frage

Bashar

ntrnt schrieb:

Nunja, was heißt schon "in einen identischen Zustand gelangen", wenn Zustandsänderungen von der Sprache nicht vorgesehen sind (bzw. expliziert werden müssen).

Das Halteproblem existiert für jedes turingäquivalente Berechnungsmodell, ob es nun Zustände hat oder nicht. Außerdem werden natürlich bei der Ausführung des Programms intern schon Zustände benutzt, das geht ja gar nicht anders, und deine Frage zielt ja darauf ab, ob der Interpreter das erkennen kann oder können sollte.

Das Halteproblem existiert für jedes turingäquivalente Berechnungsmodell, ob es nun Zustände hat oder nicht.

Ich will ja nicht für jedes gegebene Programm entscheiden ob es terminiert oder nicht, sondern nur in speziellen Fällen, in denen so eine Voraussage machbar ist. Im simpelsten Fall eben dann, wenn die gesamte linke Seite einer Definition unverändert Teil der rechten Seite ist.

Außerdem werden natürlich bei der Ausführung des Programms intern schon Zustände benutzt

Die Entscheidung über Terminierungsverhalten sollte vor der Ausführung stattfinden, insofern wären diese Zustände nicht von Relevanz.

Im Endeffekt läuft es also darauf hinaus, dass es sich nicht lohnt, für den Bruchteil an entscheidbaren Spezialfällen einen riesen Aufwand zu betreiben und den Interpreter entsprechend reagieren zu lassen, sehe ich das richtig?