haskell - Haskell 中队列的使用(模块)

Question

我对这个 Haskell 代码有疑问:

module Queue (Queue, emptyQueue, queueEmpty, enqueue, dequeue, front) where

newtype Queue a = MakeQ([a])

emptyQueue :: Queue a
emptyQueue = MakeQ([])

queueEmpty :: Queue a -> Bool
queueEmpty (MakeQ(q)) = null q

enqueue :: a -> Queue a -> Queue a
enqueue x (MakeQ(q)) = MakeQ(q ++ [x])

dequeue :: Queue a -> Queue a
dequeue (MakeQ(x:q)) = MakeQ(q)

front :: Queue a -> a
front (MakeQ(x:q)) = x

我知道队列一般是如何工作的以及每个操作的主要作用。我的第一个问题是我不知道如何使用拥抱中的操作。如何创建一个空队列或在创建它后将元素放入其中？我尝试了几个命令，但所有命令都导致了错误消息，即 Make([])、emptyQueue [] ...我知道这些命令非常幼稚，但我对 Haskell 绝对不熟悉，只需要它 2 周左右。

第二个问题是关于“MakeQ”本身的。这只是我们操作名称的声明，对吗？或者它是静态 Haskell 命令？在我看来，它也可以是“QQQ”或其他什么。我无法真正测试这是否会使程序崩溃，因为我不知道如何使用这个模块。

即使我的问题看起来有点愚蠢，如果有人能给我解释或提示，我会非常高兴......

Answer 1

emptyQueue 本身是一个空队列；您不必向其传递任何参数。

MakeQ 只是一个任意名称，你是对的；它可以是任何东西(只要你改变了它的所有其他用途)。在本例中，它是 Queue 的构造函数:如果 xs 是 a 值的列表(即具有类型[a])，则 MakeQ xs 是一个 Queue a。但是，该模块不导出 MakeQ，因此您无法从外部使用它 - 它被用作实现的一部分，并被隐藏以维护抽象；它可以很容易地用另一种非列表结构重写，而不会破坏使用该模块的任何代码。

队列上的操作不是通过就地更新现有队列来完成的，而是通过将队列转换为新队列来完成的。例如，如果 a 是 Int，而 q 是 Queue Int，则 将 q 入队是另一个Queue Int，后面添加了a。类似地，如果q是一个Queue Int，那么dequeue q是另一个没有前面元素的Queue Int，并且front q 是前面的元素本身(一个 Int)。

另外，请注意 Hugs 不再被维护；您应该考虑安装Haskell Platform ，它是基于GHC编译器的。它包含一个像 Hugs 一样的“解释器”程序，因此它不仅仅是一个标准编译器。

以下是如何从交互式提示中使用此队列模块的示例:

GHCi> let q = emptyQueue :: Queue Int
GHCi> let q1 = enqueue 42 q
GHCi> front q1
42
GHCi> let q2 = enqueue 43 q1
GHCi> front q2
43
GHCi> front (dequeue q2)
42

如果您试图在程序执行的整个过程中维护一个队列，那么您可能需要使用状态单子(monad)，这比听起来要简单得多。 :) 我建议阅读 Learn You a Haskell ，这是一个优秀的 Haskell 教程，其中涵盖了状态 monad 等内容。