Pop无法正常工作，堆栈总是空的

Question

我一直试图在Haskell中实现一个用于大学作业的Stack机器，但我遇到了困难。当我试图将一个值推入堆栈时，它总是只返回我刚刚推入的值。

module Stack(Stack, push, pop, top, stackEmpty, newStack) where
push :: t -> Stack t -> Stack t
pop :: Stack t -> Stack t
top :: Stack t -> t
stackEmpty :: Stack t -> Bool

newStack   :: Stack t
data Stack t = Stk [t]
newStack = Stk []
push x (Stk xs) = (Stk (x : xs))

pop (Stk [])      = error "retirada em pilha vazia"
pop (Stk (_ : xs)) = Stk xs
top (Stk [])     = error "topo de pilha vazia"
top (Stk (x : _)) = x
stackEmpty (Stk []) = True
stackEmpty _         = False

instance (Show t) => Show (Stack t) where
show (Stk []) = "#"
show (Stk (x : xs)) = (show x) ++ "|" ++ (show (Stk xs))

如果我每次尝试在同一堆栈中推送，就会发生这种情况，它会不断将值推送到空列表中。我想发生这种情况是因为我将pilha声明为newStack，而newStack是一个空列表，所以每次我推到它时，它都会推到一个空的列表，对吧？问题是我不知道如何保存堆栈的值。

ghci> let pilha = newStack 
ghci> push 5 pilha 
5|#
ghci> push 6 pilha
6|#
ghci>

这就是我为它在终端中工作所做的

ghci> let oldStack = push 5 newStack 
ghci> show oldStack
"5|#" 
ghci> let newerStack = push 6 oldStack
ghci> show newerStack
"6|5|#"
ghci> newerStack = push 7 newerStack 
ghci> show newerStack
" 

我知道这就是逻辑，每次我推送时，我都需要创建一个新的Stack，它将使用旧堆栈中的值，但我似乎不知道如何对其进行编码。

Answer 1

如果你写newerStack = push 7 newerStack，那么你就用newerStack本身来定义它，这意味着你将push 7 (push 7 (push 7 (…)))，从而进入一个无限循环。

因此，您应该将其实现为：

ghci> letstack1= push 5 newStack 
ghci> stack1
5|#
ghci> letstack2= push 6stack1
ghci> stack2
6|5|#
ghci> letstack3= push 7stack2
ghci> stack3
7|6|5|#

Answer 2

与您尝试做的事情最直接的等价物——可能是因为您了解其他语言的这种工作风格——是使用IORefs，这是在Haskell中拥有真正的可变变量的唯一方法。

*Stack> :m +Data.IORef
*Stack Data.IORef> s <- newIORef (newStack :: Stack Int)
*Stack Data.IORef> modifyIORef s $ push 5
*Stack Data.IORef> readIORef s
5|#
*Stack Data.IORef> modifyIORef s $ push 63
*Stack Data.IORef> readIORef s
63|5|#
*Stack Data.IORef> modifyIORef s pop
*Stack Data.IORef> readIORef s
5|#

但很少有充分的理由走这条路。命令式语言如此依赖突变的原因是，您一直使用循环作为控制结构，这需要处理变量状态，同时保持使用相同的变量。但在Haskell中，你根本不需要这样做——你使用递归，这会自动让你有机会通过传递不同的参数来"修改"值，而不需要发明新的变量名。

即使不考虑递归，您也可以在管道中链接多个更新。完全不需要变量：

*Stack> pop . push 9 . push 3 $ newStack 
3|#

如前所述，还有状态monad，它封装了伪可变状态。当你有一大堆不同的操作，都读取和/或变异同一个东西时，它最有用(通常是某种小型数据库(。

import Control.Monad.Trans.State
statefulExample :: State (Stack Char) ()
statefulExample = do
modify $ push 'h'
modify $ push 'e'
modify $ push 'k'
modify $ pop
mapM_ (modify . push) "llo, world"

*Stack>execState statefulExample newStack 
'd'|'l'|'r'|'o'|'w'|' '|','|'o'|'l'|'l'|'e'|'h'|#