Haskell:将整数压入堆栈实现时的无限列表 [英] Haskell : Infinite list when integer is pushed to stack implementation

问题描述

我正在尝试实现一个简单的Stack，但是对于为什么在将整数压入堆栈时为什么得到一个无限列表感到困惑.

所有其他功能均按我预期的方式工作，但我不理解push的问题.当我尝试为其分配一个已推送如下变量的空堆栈时，它会出错:

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

解决方案

Haskell不允许进行突变.在源文件中，如果您定义变量a，然后尝试重新分配它，就像在此处使用a = push 3 a那样，则会出现编译错误.唯一不这样做的原因是您正在GHCi中工作，它确实允许您重新定义变量-这纯粹是一种方便，因此您在尝试不同的定义时不必继续思考新的名称.

而且，至关重要的是，a = push 3 a不是 ，它以命令式语言为基础，根据前一个为a提供新值.相反，它是a 本身的定义.

这就是为什么您获得无限列表的原因-您的定义按以下方式处理:

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

，依此类推.由于Haskell的懒惰，这样的定义没有问题-GHCi会在您要求完整列表时(如此处)仅一次计算一个元素，因此继续打印3s直到告诉它停止.

要获得所需的内容，只需键入push 3 a，或者如果需要为其指定名称，只需从a中选择一个不同的名称即可. b = push 3 a后跟b的行为将符合您的预期.

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)

解决方案

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.

这篇关于Haskell:将整数压入堆栈实现时的无限列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！