编写一个递归函数来构建一个集合

Question

我在我的作业中遇到了麻烦。

写一个递归函数，构建一个集合。 mkSet :: Eq a => [a] -> Set a

其中一个提示是我应该使用另一个名为isElement的函数来检查重复的值。下面是我对isElement的代码：

isElement :: Eq a => a -> [a] -> Bool
isElement x [] = False
isElement x (y:xs) = if x == y then True else isElement x xs

我经常遇到的一个主要错误是每次调用isElement时，mkSet返回的值都是一个布尔值（我不确定自己做错了什么）。

这是我目前为我的mkSet所写的代码（请记住我刚开始学习Haskell）。

mkSet :: Eq a => [a] -> Set a
mkSet x [] = isElement x (xs)

我应该做些什么呢？谢谢！

- Hotaru009

---

Set 是如何定义的？您是使用 Data.Set 中的那个（通过 import Data.Set）还是在代码中有一个 data Set a = ... 的定义？ - rampion

尝试定义一个类型为Eq a => a -> Set a -> Set a的insert函数；它将使用isElement来决定要执行什么操作。然后看看是否可以利用insert函数定义mkSet函数。 - GS - Apologise to Monica

我认为“Set a”只是列表“[a]”的同义词（即在文件中有“type Set = []”的声明；将其称为集合仅表示该列表不应包含重复项），但如果您明确这样的细节会更有帮助。 - leftaroundabout

请注意，if x == y then True else isElement x xs 可以更简洁地写成 x == y || isElement x xs。如果递归实现 isElement 不是问题要求的一部分，它可以被写成 isElement x xs = any (== x) xs，甚至可以写成 isElement = elem：这个函数已经存在于 Prelude 中了。 - amalloy

这不是一个错误，但是 x 'isElement' [] = ... 看起来更好一些。对于 mkSet - 你应该取一个列表并且只保留其中的唯一元素。 - viorior

Answer 1

首先，我认为你指的是 mkSet (x:xs) 而不是 mkSet x []，因为你使用了 xs。

你的函数 'mkSet x [] = isElement x (xs)' 调用了函数 isElement，该函数返回一个 Bool。因此，你所分配的 mkSet x [] 是一个 Bool 而不是 Set a。

所以你需要像这样做：

mkSet' :: [a] -> [a]
mkSet' [] = []
mkSet' (x:[]) = [x]
mkSet' (x:xs) = if (isElement x xs) then (mkSet' xs) else (x:(mkSet' xs))

这个函数可以给你一个包含唯一元素的列表。你需要做的是将其转换为一个集合。

- Kriptoniet