为Haskell堆栈编写pop和push函数

Question

嗨,我正在尝试为这样定义的Haskell堆栈创建pop和push函数:

data mystack = Empty | Elem Char mystack deriving Show

如果我没有这个定义限制,我会像这样推

push x mystack = (x:mystack)

像这样弹出

pop mystack = head mystack

但是由于这个限制,我不知道如何实现这些功能.你能给我一些提示怎么做吗？我甚至不能自己编写带有该描述的Stack类型.

Answer 1

提示:以下是使用内置列表实现堆栈操作的方法:

push :: a -> [a] -> ((),[a])  -- return a tuple containing a 'nothing' and a new stack
push elem stack = ((), (:) elem stack)

pop :: [a] -> (a, [a])  -- return a tuple containing the popped element and the new stack
pop [] = error "Can't pop from an empty stack!"
pop ((:) x stack) = (x, stack)

(:) x xs是另一种写作方式x:xs.

要在您自己的MyStack类型上执行此操作,请注意您的Empty实际工作就像[],并且Elem相当于(:).我不会给你完全做到这一点的代码,因为为自己搞清楚是一半的乐趣!