haskell - 在haskell中创建堆栈作为抽象数据类型

Question

我需要在 haskell 中创建堆栈数据类型才能这样编写：

let a = emptyStack

push 10 a
//[10]

pop a 
[]

我想推看起来像

push :: a -> Stack a -> Stack a
push a b = a:b

但我有语法问题，究竟如何声明这个新数据类型，所以

let a = emptyStack 
:t a

会显示堆栈

有关语法的任何提示

Answer 1

让我们看看你的实现push。它使用运算符:. 您可以像这样找出该运算符的类型：

ghci> :t (:)
(:) :: a -> [a] -> [a]

所以这个运算符接受一个a（表示任意类型）和一个as 序列，并返回更新后的序列。所以你的类型Stack需要是一个序列。

type Stack a = [a]

如果你然后像这样定义emptyStack：

emptyStack :: Stack a
emptyStack = []

你会得到你正在寻找的结果。

ghci> :t a
a :: Stack a

有了这些帮助，我想您将能够弄清楚如何编写pop.

Answer 2

你可以写

import Data.Maybe

data Stack a = Stack [a] deriving Show

empty :: Stack a
empty = Stack []

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

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

例子

*Main> push 4 $ push 3 empty
Stack [4,3]
*Main> pop $ push 4 $ push 3 empty
(Just 4,Stack [3])

这种方法严格检查类型参数（与@mhwombat 解决方案相反）。一种或其他方法是有效的（在某些情况下，一种方法会比另一种更好，反之亦然）。