Haskell编程中的数据类型

Question

这是一个用Haskell编写的代码，用于查找列表中第一个重复元素。如果你有两个像这样的列表：L1={1,2,3,4} L2={1,2,3,1}，则第一个列表的结果应该是“未找到重复项”，而第二个列表的结果应该是整数1。如果一个列表为L3={1,2,1,3,3}，答案仍然应该是1。

我尝试过了，但卡在了条件检查上： 我们将使用联合数据类型。

data Res a = DuplicateFound a | NoDuplicateFound 
              deriving (Show,Eq)

findDuplicate [] = NoDuplicateFound
findDuplicate (x:xs) = if (condition???)
      where 
      aux x [] = NoDuplicateFound
      aux x (y:ys) = if x == y then DuplicateFound x
                               else aux x ys
                     else NoDuplicateFound

我知道这是一个可悲的代码，请帮助我改进它。

- cuddle

---

这是一个关于Haskell编程的问题，请参考此链接。 - dbyrne

除此之外，我赞扬这位作者尝试解决问题并将其发布，而不是只是将他的作业转移到网站上。+1 - luqui

我不会写成列表L1 = {1, 2, 3, 4}，而是写成L1 = [1, 2, 3, 4]。这样做可以减少混淆，因为方括号通常表示列表，而花括号在Haskell中代表什么呢？例如，在Erlang中它们是元组。 - Magnus Kronqvist

Answer 1

关键在于，递归经常被使用。

一个列表如果包含重复元素，则满足以下条件之一： 1. 第一个元素在列表的其余部分中有重复；或 2. 列表的其余部分包含重复元素。

另外要注意，一个空列表不包含重复元素，这就是你的程序。

（我会让 hasElement 只返回一个 Bool 值，并使用 Maybe a 作为返回值。）

- Ketil

Answer 2

这段代码是一个良好的开端。你已经编写了aux函数来搜索元素是否在列表中。现在你只需要将第一个元素与列表中其余元素进行比较，如果失败，则将第二个元素与其后所有元素进行比较，以此类推。

我将把aux重命名为hasElement（不要低估一个好名称的澄清能力）：

hasElement x [] = NoDuplicateFound
hasElement x (y:ys) = if x == y then DuplicateFound x
                                else hasElement x ys

然后：

findDuplicate [] = NoDuplicateFound
findDuplicate (x:xs) = 
    case hasElement x xs of
        DuplicateFound dup -> ...
        NoDuplicateFound   -> ...

我会让你填写...。祝你好运，并感谢你在寻求帮助之前尝试解决问题。这使我更愿意付出努力来回答你的问题。

- luqui

---

谢谢，但我还是不清楚...当x==y时，将检查第一个元素是否等于其余元素的头部。但我不知道如何检查第二个元素。数据Res a = DuplicateFound a | NoDuplicateFound deriving (Show,Eq)aux x [] = NoDuplicateFound aux x (y:ys) = if x == y then DuplicateFound x else aux x ysfindDuplicate [] = Nothing findDuplicate (x:xs) = case aux x xs of DuplicateFound x` -> "第一个重复项：" ++ (show x) NoDuplicateFound -> "没有重复项" - cuddle

@cuddle，尝试让findDuplicate递归调用自身。我建议返回一个Res，这不应该是I/O代码。 - luqui

Answer 3

你可以使用nub和(\\)轻松（但不是非常高效地）获取所有重复项的列表。

我猜这是一道作业题：这个建议应该会给你一个很好的起点。

- lbolla