Haskell: lista infinita cuando se envía un entero a la implementación de la pila

Question

Estoy tratando de implementar una pila simple, pero no sé por qué obtengo una lista infinita cuando envío un número entero a la pila.

Todas las demás funciones funcionan como las espero, pero no entiendo el problema con push. Sale mal cuando trato de asignar una pila vacía a sí mismo que ha empujado una variable como la siguiente:

λ > 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 no permite la mutación. En un archivo fuente, si define una variable ay luego intenta reasignarla, como hace aquí a = push 3 a, obtendrá un error de compilación. La única razón por la que no lo hace es porque está trabajando en GHCi, lo que le permite redefinir variables; esto es simplemente una conveniencia para que no tenga que seguir pensando en nuevos nombres mientras experimenta con diferentes definiciones.

Y, fundamentalmente, noa = push 3 a está dando un nuevo valor a basado en el anterior, como sería en un lenguaje imperativo. En cambio, es una definición de en términos de sí mismo .aa

Es por eso que obtiene una lista infinita: su definición se procesa de la siguiente manera:

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

y así. Debido a la pereza de Haskell, no hay problema con una definición como esta: GHCi, cuando solicite la lista completa, como aquí, simplemente calculará un elemento a la vez y, por lo tanto, seguirá imprimiendo 3 hasta que le diga que se detenga.

Para obtener lo que desea, solo debe escribir push 3 a, o si necesita asignarle un nombre, simplemente elija un nombre diferente de a. b = push 3 aseguido de bse comportará como espera.

Answer 2

No hay (supongo, casi ) variables mutables (gracias a @amalloy por corregir mi terminología) en haskell.

Si escribe algo como esto:

x = f x

Entra en un bucle infinito: f (f (f ...

Entonces, no hay un valor pasado de ain al que 3se pueda presionar.

Por lo tanto, debe push 3 aingresar algún otro valor (o directamente en el ghci para el caso).

Sin embargo, tal bucle puede ser útil a veces. Eche un vistazo a Data.Function.fix:

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

Puede usarse para hacer lo mismo que usted:

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

Sin embargo, el bucle infinito no siempre es así. Echar un vistazo:

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

Esta función puede parecer factorial, sin embargo, la llamada recursiva en la rama no terminante se reemplaza con un dummy ( rec). Nos gustaría que este muñeco se reemplazara factFununa y otra y otra vez para obtener el factorial. fixHaz esto:

GHCi> fix factFun 4
24

---

Nota: duplicaré mi comentario aquí: si el lector aún no lo sabe fix, quiero invitarlo a un viaje largo e interesante. Sugiero que comiencen con este wikilibro sobre semántica denotacional .