如何在Haskell中实现Set作为抽象数据类型?

Question

我必须在Haskell中实现一个抽象数据类型的集合。任务如下:

set为一组元素建模。一个集合要么是空集合，要么是递归地由一个元素和集合的其余元素组成。函数isEmpty、contains、add、remove将被定义。

• 函数isEmpty检查集合是否为空。
• contains接受一个集合和一个元素，并指示该集合是否包含该元素。
• add接受一个集合和一个元素，如果该元素不在集合中，则将该元素添加到集合中。
中没有包含
• remove函数接受一个集合和一个元素，如果元素已经在集合中，则从集合中删除该元素。如果元素不在集合中，函数返回一个错误。

我正在努力完成任务的递归部分，我不知道。如何实现"包含"呢?特别吗?

module Set (Set(EmptySet, MkSet), isEmpty, contains, add, remove)
where

data Set a = EmptySet | MkSet a (Set a)
deriving (Show, Eq, Enum, Ord, Read)
isEmpty :: Set a -> Bool
isEmpty EmptySet = True
isEmpty (MkSet a as) = False
contains :: Set a -> a -> Bool
contains EmptySet = error "no element in set."
contains (MkSet a as) a = True
contains (MkSet a as) b = False
add :: a -> Set a -> Set a
add a as = (MkSet a as)
remove :: Set a -> Set a
remove EmptySet = error "No remove operation on empty set allowed."
remove (MkSet a as) = as

(https://i.stack.imgur.com/W8kSj.png)

Answer 1

两次使用模式变量a的模式contains (MkSet a as) a在文献中称为非线性模式。Haskell中不允许使用非线性模式。相反，您必须像这样显式地检查相等性:

contains (MkSet a as) b
| a == b = ...
| otherwise = ...

这还需要在类型签名中添加contains :: Eq a => Set a -> a -> Bool。

注意，a和b是不同的变量并不一定意味着在匹配时必须为它们分配不同的值。

其次，contains (MkSet a as) b = False没有考虑到元素可能包含在as中(提示:使用递归)。

第三，询问元素是否在空集合中不是错误(感谢chepner)。在这种情况下，它应该只返回False。