Haskell : Infinite list when integer is pushed to stack implementation

Question

I'm trying to implement a simple Stack but I'm confused as to why I get an infinite list when I push an integer to the stack.

All of the other functions work as I expect them but I don't understand the problem with push. It goes wrong when I try to assign an empty stack to itself that has pushed a variable like the following:

λ > 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 does not allow mutation. In a source file, if you define a variable a and then attempt to reassign it, as you do here with a = push 3 a, you would get a compilation error. The only reason you don't is that you are working in GHCi, which does allow you to redefine variables - this is purely a convenience so you don't have to keep on thinking up new names while experimenting with different definitions.

And, crucially, a = push 3 a is not giving a new value to a based on the previous one, as it would be in an imperative language. Instead, it is a definition of a in terms of itself.

That's why you get an infinite list - your definition is processed as follows:

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

and so on. Because of Haskell's laziness, there's no problem with a definition like this - GHCi will, when you ask for the full list, as here, simply calculate one element at a time, and therefore keep printing 3s until you tell it to stop.

To get what you want, you need to either just type push 3 a, or if you need to assign it a name, simply choose a different name from a. b = push 3 a followed by b will behave as you expect.