Haskell : Infinite list when integer is pushed to stack implementation

user_11191691 0
Viewed 190

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)
stack haskell
2 Answers

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.

user_84750540

There are (I guess, almost) no mutable (thanks to @amalloy for correcting my terminology) variables in haskell.

If you write something like this:

x = f x

It enters an infinite loop: f (f (f ...

So, there is no past value of a in which 3 may be pushed.

Therefore, you have to put push 3 a in some other value (or directly into the ghci for that matter).

Such a loop might come in handy sometimes though. Take a look at Data.Function.fix:

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

It can be used to do the same thing as you do:

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

Yet, the infinite loop is not always the case. Take a look:

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

This function might look like factorial, yet the recursive call in the non-terminating branch is replaced with a dummy (rec). We would like to have this dummy replaced with factFun over and over and over again to get the factorial. fix does this:

GHCi> fix factFun 4
24

Note: I will duplicate my comment here: if the reader does not know of fix yet, I want to invite them on a long and interesting trip. I suggest they start with this wikibook on denotational semantics.

user_111437630
Related