Haskell 如何检查一个 Int 列表是否完整

Question

这个并不容易解释，但我会尝试。我想我可能把我的方法和一些C语言混淆了，但是我会试着解释一下：

我想要检查一个列表是否完整，就像这样：

main> check 1 [1,3,4,5]
False

main> check 1 [1,2,3,4]
True

这是一个有限的列表，列表不必有序。但在列表内部必须有一个缺失的数字为True。在第一种情况下，这个数字是2。

这是我的版本，但它甚至无法编译。

check :: Eq a => a -> [a] -> Bool
check n [] = False
check n x | n/=(maximum x) = elem n x && check (n+1) x
          | otherwise = False

- PablodeAcero

Answer 1

如果我理解正确的话，您想要检查在排序时列表中的所有元素是否形成一个没有间隙的序列。以下是一种方法：

noGaps :: (Enum a, Ord a) => [a] -> Bool
noGaps xs = all (`elem` xs) [minimum xs .. maximum xs]

[minimum xs .. maximum xs] 创建一个包含从最小值到最大值的所有值的连续列表。然后您只需要检查它们是不是原始列表的所有元素即可。

- Gabriella Gonzalez

---

感谢您为“check”函数提供了正确的签名，我自己无法想出来（我刚学会如何将类型限定为属于两个不同的类型类！）。 - didierc

Answer 2

您的函数无法编译，因为类型约束超出了您声明的范围。您说a只需要是Eq的一个实例——但是您添加了一些内容，这要求它是Num的一个实例。与您声明的签名不符的是，您使用该函数的方式也没有意义。在您的示例中，check [1,2,3,4]是一个Bool，但是在您给出的代码中，它将是Eq a => [[a]] -> Bool（如果首先编译通过）。

您是否只需要它与整数配合使用？如果不是，请给出一些关于在这种情况下“完整”的示例。如果是，那么它们总是以1开始吗？

- Cubic

---

是的，非常抱歉，我没有解释清楚。列表必须始终包含元素“1”。主要应该实际为：main> check 1 [1,3,4,5] main> False - PablodeAcero

Answer 3

这里提供另一种解决问题的方法，它使用一个适用于排序列表的函数，并将其与已排序的输入一起使用。

以下代码将检查提供的包含n个整数的列表是否包含从1到n的所有值：

  check :: (Num a, Ord a) => [a] -> Bool

  import List

  check l = check_ 1 (sort l)
     where check_ n [] = True
                 check_ n [x] = n == x
                 check_ n (x:y:xs) = (x+1)==y && check_ (n+1) (y:xs)

请注意在check_函数中实现真实检查之前，使用List.sort对列表进行了排序。

- didierc