haskell - 如何指定类型类的具体实现？

Question

我有以下简单的 Haskell 模块，它定义了一个类型类 Queue，在该类型类上进行 push、pop 和 top 操作必须定义 code>，以及空队列的构造函数和检查队列是否为空的函数。然后它提供了两种实现:先进先出队列和堆栈。

代码有效。然而，我似乎不必要地重复自己的话。特别是，队列和堆栈之间唯一不同的操作是推送操作(我们是将新对象推送到列表的前面还是后面？)。似乎应该有某种方法来定义类型类定义中的常见操作。事实上，这可能吗？

module Queue (
    Queue,
    FifoQueue(FifoQueue),
    Stack(Stack),
    empty,
    isEmpty,
    push,
    pop,
    top
) where

class Queue q where
    empty :: q a
    isEmpty :: q a -> Bool
    push :: a -> q a -> q a
    pop :: q a -> (a, q a)
    top :: q a -> a

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

instance Queue Stack where
    empty = Stack []
    isEmpty (Stack xs) = null xs
    push x (Stack xs) = Stack (x:xs)
    pop (Stack xs) = (head xs, Stack (tail xs))
    top (Stack xs) = head xs

data FifoQueue a = FifoQueue [a] deriving (Show, Eq)

instance Queue FifoQueue where
    empty = FifoQueue []
    isEmpty (FifoQueue xs) = null xs
    push x (FifoQueue xs) = FifoQueue (xs ++ [x])
    pop (FifoQueue xs) = (head xs, FifoQueue (tail xs))
    top (FifoQueue xs) = head xs

Answer 1

好吧，只有少量重复，但让我们去掉它。

关键是我们可以为 Queue 提供默认值，因为我们知道如何将其转换为列表，此外，提供了一个队列，我们​​可以创建一个列表。因此，我们只需在您的定义中添加两个函数，toList 和 fromList，并确保给出 toList 和 fromList >，或者给出其他函数，做一个完整的定义。

import Control.Arrow

class Queue q where
    empty :: q a
    empty = fromList []
    isEmpty :: q a -> Bool
    isEmpty = null . toList
    push :: a -> q a -> q a
    push a b = fromList (a : toList b)
    pop :: q a -> (a, q a)
    pop qs = (head . toList $ qs,fromList . tail . toList $ qs)
    top :: q a -> a
    top = head . toList
    toList :: q a -> [a]
    toList queue = if isEmpty queue then [] 
                   else uncurry (:) . second toList . pop $ queue
    fromList :: [a] -> q a
    fromList = foldr push empty

如您所见，队列的任何实现都必须提供 toList 和 fromList 或其他函数，因此两个队列的实现如下:

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

instance Queue Stack where
    toList (Stack a) = a
    fromList a = Stack a

data FifoQueue a = FifoQueue [a] deriving (Show, Eq)

instance Queue FifoQueue where
    toList (FifoQueue a) = a
    fromList a = FifoQueue a
    push x (FifoQueue xs) = FifoQueue (xs ++ [x])