如何定义一个可以像堆栈一样推送和弹出的LIST？

Question

我的代码中定义了以下TYPE:

type Pos = (Int, Int)      -- position in 2 dimensions

我想创建一个包含Pos元素的列表(或堆栈或其他).

我需要能够将一个Pos元素添加(推送)到列表的头部(当在该位置进行更改时),并在需要时从列表的头部拉出(弹出)一个Pos(以重放最后一个)更改).

我对Haskell真的很陌生,那么最好的方法是什么？我应该只使用一个列表并与HEAD一起玩吗？但是如何从头部"弹出"中"移除",或者是否有我可以使用的堆栈(对我来说听起来像堆栈类型的东西) - 如果是这样的话我该如何使用"Pos"类型的元素创建它？

Answer 1

听起来你想在列表上执行"有状态"操作,将其视为堆栈.Haskell有几种方法可以做到这一点,最基本的是简单地定义带有堆栈的函数并为每个"修改"返回一个新函数,因为Haskell具有不可变变量(从技术上讲,它根本没有变量,只有名称绑定到不可变的值).你可以这样做

newtype Stack a = Stack [a] deriving (Eq, Show)

这简单地定义了一个[a]被调用的包装器,Stack a因此我们的类型签名更加严格和信息丰富.然后,我们可以定义push并pop很容易:

pop :: Stack a -> (a, Stack a)
pop (Stack (x:xs)) = (x, Stack xs)
pop (Stack []) = error "Empty stack"

push :: a -> Stack a -> Stack a
push x (Stack xs) = Stack (x:xs)

这将有效,但我真的不喜欢pop有能力提出error,这可能会导致我们的程序崩溃.我们最好使用可以表示失败的数据类型,在这种情况下,这Maybe将是一个很好的选择:

pop :: Stack a -> (Maybe a, Stack a)
pop (Stack (x:xs)) = (Just x, Stack xs)
pop (Stack []) = (Nothing, Stack [])

我们可以使用它

main :: IO ()
main = do
    let start = Stack [] :: Stack Int
        step1 = push 1 start        -- Stack [1]
        step2 = push 2 step1        -- Stack [2, 1]
        (_, step3) = pop step2      -- Stack [1]
        step4 = push 10 step3       -- Stack [10, 1]
    print step4

但这真的太烦人了,编写得不好,需要我们编写大量的中间语句.当然,我们可以将其中的一些组合push在一起,但它不会让我们受益匪浅.如果Haskell可以为我们处理那些中间值,那就更好了,事实上它可以.我们可以使用Statemonad使这更简单.该State单子表示一系列计算用于修改一个纯数据结构.从本质上讲,它只是处理我们的所有组合和中间值,以便我们可以专注于算法,而不是细节.如果我们重命名pop为to pop_和pushto push_,我们可以编写以下代码:

type StackState a b = State (Stack a) b

pop :: StackState a (Maybe a)
pop = state push_
-- The `state` function has the type (s -> (a, s)) -> State s a,
-- so applying it to `push_ :: Stack a -> (Maybe a, Stack a)` gives
-- us `State (Stack a) (Maybe a)`. (It actually has a bit more general
-- type, but it simplifies to this)

push :: a -> StackState a ()
push x = modify (push_ x)
-- The `modify` function has the type (s -> s) -> State s ()

现在我们可以更轻松地构建计算:

stackTransform :: StackState Int ()
stackTransform = do
    push 1
    push 2
    pop
    push 10

我们甚至可以编写更复杂的操作

test :: StackState Int Int
test = do
    mapM_ push [1..10]
    Just x <- pop
    push $ x * 10
    return x

然后这些可以从mainas 运行

main :: IO ()
main = do
    let start = Stack [] :: Stack Int
    print $ execState stackTransform start

虽然这个解决方案有点复杂并且需要一些monad知识,但它确实让我们更清晰地编写堆栈操作,而不必担心中间步骤,这是使用monad的一个好处.实现细节State有点棘手,所以我现在不会讨论它们,但是在某些方面它们非常好学习.

我认为还值得一提的是,还有另一个选项允许你拥有"可变变量",但是你的所有动作都必须存在于IOmonad中,并且它的实现效率将低于上述任何一个.您可以使用IORefs作为可变指针来实现此行为:

import Data.IORef

newtype Stack a = Stack [a] deriving (Eq, Show)

type IOStack a = IORef (Stack a)

popIO :: IOStack a -> IO (Maybe a)
popIO iostack = do
    -- Read the current stack
    stack <- readIORef iostack
    case stack of
        Stack []     -> return Nothing
        Stack (x:xs) -> do
            -- Put the new stack back into the IORef
            writeIORef iostack (Stack xs)
            -- Return the top value in the stack
            return (Just x)

pushIO :: a -> IOStack a -> IO ()
pushIO x iostack = do
    -- Read the current stack
    (Stack xs) <- readIORef iostack
    -- Write the new stack back into the IORef
    writeIORef (Stack (x:xs))

然后你可以从使用它main作为

main :: IO ()
main = do
    iostart <- newIORef (Stack [] :: Stack Int)
    pushIO 1 iostart
    pushIO 2 iostart
    popIO iostart
    pushIO 10 iostart
    final <- readIORef iostart
    print final

但是这仍然会比State版本更多的代码,并且它肯定更容易出错并且会更慢.