Haskell: lista infinita quando o inteiro é empurrado para empilhar a implementação

Question

Estou tentando implementar uma pilha simples, mas não sei por que recebo uma lista infinita quando coloco um inteiro na pilha.

Todas as outras funções funcionam como eu esperava, mas não entendo o problema com push. Dá errado quando tento atribuir a si mesma uma pilha vazia que enviou uma variável como a seguinte:

λ > 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ão permite mutação. Em um arquivo de origem, se você definir uma variável ae, em seguida, tentar reatribuí-la, como você faz aqui com a = push 3 a, obterá um erro de compilação. A única razão para não fazer isso é que você está trabalhando no GHCi, o que permite redefinir variáveis ​​- isso é puramente uma conveniência, então você não precisa ficar pensando em novos nomes enquanto faz experiências com diferentes definições.

E, fundamentalmente, nãoa = push 3 a é dar um novo valor a com base no anterior, como seria em uma linguagem imperativa. Em vez disso, é uma definição de em termos de si mesmo .aa

É por isso que você obtém uma lista infinita - sua definição é processada da seguinte maneira:

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

e assim por diante. Por causa da preguiça de Haskell, não há problema com uma definição como esta - GHCi irá, quando você pedir a lista completa, como aqui, simplesmente calcular um elemento de cada vez e, portanto, continuar imprimindo 3s até que você diga para parar.

Para obter o que deseja, basta digitar push 3 aou, se precisar atribuir um nome, basta escolher um nome diferente de a. b = push 3 aseguido por birá se comportar como você espera.

Answer 2

Não há (eu acho, quase ) variáveis mutáveis (graças a @amalloy por corrigir minha terminologia) em haskell.

Se você escrever algo assim:

x = f x

Ele entra em um loop infinito: f (f (f ...

Portanto, não há valor passado de aem que 3possa ser empurrado.

Portanto, você deve push 3 ainserir algum outro valor (ou diretamente no ghci).

No entanto, esse loop pode ser útil às vezes. Dê uma olhada em Data.Function.fix:

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

Ele pode ser usado para fazer a mesma coisa que você:

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

No entanto, o loop infinito nem sempre é o caso. Dê uma olhada:

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

Esta função pode parecer fatorial, mas a chamada recursiva no branch sem terminação é substituída por um dummy ( rec). Gostaríamos de ter esse manequim substituído factFunrepetidamente para obter o fatorial. fixfaz isso:

GHCi> fix factFun 4
24

---

Obs: duplicarei meu comentário aqui: se o leitor ainda não sabe fix, quero convidá-lo para uma viagem longa e interessante. Eu sugiro que eles comecem com este wikibook sobre semântica denotacional .