Haskell: liste infinie lorsque l'entier est poussé vers l'implémentation de la pile

Question

J'essaie d'implémenter une pile simple mais je ne comprends pas pourquoi j'obtiens une liste infinie lorsque je pousse un entier dans la pile.

Toutes les autres fonctions fonctionnent comme je l'attends mais je ne comprends pas le problème avec push. Cela ne va pas lorsque j'essaie de s'attribuer une pile vide qui a poussé une variable comme celle-ci:

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

Answer 1

Haskell n'autorise pas la mutation. Dans un fichier source, si vous définissez une variable apuis tentez de la réaffecter, comme vous le faites ici a = push 3 a, vous obtiendrez une erreur de compilation. La seule raison pour laquelle vous ne le faites pas est que vous travaillez dans GHCi, ce qui vous permet de redéfinir des variables - c'est purement pratique, vous n'avez donc pas à continuer à penser à de nouveaux noms tout en expérimentant différentes définitions.

Et, surtout, a = push 3 aest pas de donner une nouvelle valeur à abase de la précédente, car il serait dans un langage impératif. Au lieu de cela, c'est une définition a en termes de lui-même .

C'est pourquoi vous obtenez une liste infinie - votre définition est traitée comme suit:

a = push 3 a
   = 3:a
   = 3:(push 3 a)
   = 3:(3:a)

etc. En raison de la paresse de Haskell, il n'y a aucun problème avec une définition comme celle-ci - GHCi, lorsque vous demandez la liste complète, comme ici, calculera simplement un élément à la fois, et continuera donc à imprimer 3s jusqu'à ce que vous lui disiez de s'arrêter.

Pour obtenir ce que vous voulez, vous devez simplement taper push 3 aou si vous devez lui attribuer un nom, choisissez simplement un autre nom a. b = push 3 asuivi de bse comportera comme prévu.

Answer 2

Il n'y a (je suppose, presque) aucune variable mutable (grâce à @amalloy pour avoir corrigé ma terminologie) dans haskell.

Si vous écrivez quelque chose comme ceci:

x = f x

Il entre dans une boucle infinie: f (f (f ...

Donc, il n'y a pas de valeur passée de adans laquelle 3peut être poussé.

Par conséquent, vous devez mettre push 3 aune autre valeur (ou directement dans le ghci d'ailleurs).

Une telle boucle peut parfois s'avérer utile. Jetez un œil à Data.Function.fix:

fix :: (a -> a) -> a
fix f = let x = f x in x

Il peut être utilisé pour faire la même chose que vous:

GHCi> fix (push 3)
[3,3,3,3,^CInterrupted.

Pourtant, la boucle infinie n'est pas toujours le cas. Regarde:

factFun rec n = if n == 0 then 1 else n * rec (n - 1)

Cette fonction peut ressembler à factorielle, mais l'appel récursif dans la branche non terminale est remplacé par un dummy ( rec). Nous aimerions que ce mannequin soit remplacé par factFunencore et encore et encore pour obtenir le factoriel. fixest ce que ca:

GHCi> fix factFun 4
24

---

Remarque: je vais dupliquer mon commentaire ici: si le lecteur ne le sait pas fixencore, je souhaite l'inviter à un long et intéressant voyage. Je suggère qu'ils commencent par ce wikibook sur la sémantique dénotationnelle .