Haskell集合数据类型

Question

大家好，我正在尝试在Haskell中创建一个集合数据类型，但是我无法弄清楚如何实现。以下是我目前的代码，我有些困惑：

data Set a = Node a | List {
    list :: [a]
}deriving(Eq,Show,Ord)

insert :: Set Integer -> Set Integer -> Bool
insert (Node itemToInsert) (List list)
    |contains (List list) (Node itemToInsert) == False = List(list:(Node itemToInsert))


contains :: Set Integer -> Set Integer -> Bool
contains (List []) (Node numberToFind) = False
contains (List (x:xs)) (Node numberToFind)
    |x == (Node numberToFind) = True
    |otherwise = contains (List (xs)) (Node numberToFind)

感谢您的帮助！

- functionalCode

---

我想要一个节点列表，但是我无法弄清楚如何定义数据类型来实现这个。 - undefined

你不能指定“这是一个特定构造函数的列表”：对于这样的情况，使用智能构造函数或者使用另一种数据类型。但是为什么你要定义一个新的Set数据类型，当我们已经有Data.Set了呢？如果你想表示一个图（通过“Node”暗示），那么要么明确说明，要么使用现有的图库！ - undefined

为什么这个被投票否决了？看起来像是一个诚实的问题。 - undefined

Answer 1

从您的代码看，似乎您已经理解，集合可以被视为一个没有重复项的列表。因此，让我们用一个简单的类型定义来表示它：

data Set a = Set [a]

为了确保没有重复，可以引入“智能构造函数”，它们是不严格意义上的构造函数，但可用作构造函数。

empty :: Set a
empty = Set []

我们需要另一个函数来创建非空集合。让我们看一下你的“insert”函数。为什么它返回一个“Bool”？它不应该返回一个集合吗？为什么“insert”需要两个集合作为参数？因此，要将整数插入到整数集合中，可以使用以下类型签名：

insert :: Integer -> Set Integer -> Set Integer

实现分为两种情况：1. 给定的整数不在给定的集合中，2. 给定的整数在给定的集合中。

insert x (Set xs)
    | not (x `elem` xs) = Set (x:xs)
    | otherwise         = Set xs

由于这个问题似乎是作业的一部分，我建议你尝试自己想出如何实现elem。

- jmg