haskell - 为什么这个列表理解失败？

Question

我正在尝试从这样的列表中选择独特的元素：

x = [1,1,2,3,4]
s = [e | e <- x, not (e `elem` s)]

它不会产生错误，但是当我尝试从中读取时，s程序似乎挂起。为什么？

另外，这样做的正确方法是什么？

Answer 1

我不是一个 Haskell-er，但这似乎你刚刚编写了类似于¹ Russell 悖论的东西。您不是要一个列表s，其元素是 inx而不是 ins吗？

s = [e | e <- [1,1,2,3,4], not (e `elem` s)]

因此，请考虑当您尝试请求s. 嗯，eis的第一个元素1，所以if1的第一个元素。嗯，是吗？我们可以通过遍历元素并查看是否出现来检查。好吧，让我们从……的第一个元素开始吧。</p> s not (1 `elem` s)(1 `elem` s)s1s

一般假设 somen是 的一个元素s。那么什么必须是真的？ n必须是x（易于检查）的元素，也不是s. 但我们认为它是的一个元素s。这是一个矛盾。因此， non​​可以是 的元素s，所以s必须是空列表。不幸的是，Haskell 编译器并没有像我们刚才那样做证明，它试图以编程方式计算s.

要从列表中删除重复项，您需要 Neil Brown 在评论中推荐的功能，nub来自Data.List：

nub::Eqa => [a] -> [a] 资源

O(n^2)。nub 函数从列表中删除重复的元素。特别是，它只保留每个元素的第一次出现。（名称nub的意思是“本质”。）它是nubBy的一个特例，它允许程序员提供他们自己的相等性测试。

---

1. 这实际上不是罗素悖论。罗素悖论是关于一个只包含那些不包含自己的集合的集合。 那个集合不能存在，因为如果它包含自己，那么它一定不包含自己，如果它不包含自己，那么它必须包含自己。

Answer 2

请注意，虽然罗素悖论有助于表明这可能是不可计算的，但即使您将其更改为s = [e | e <- x, elem e s].

这是一个指导性的手动扩展。对于任何非空列表，x

s = [e | e <- x, not (e `elem` s)]

简化为

s = do e <- x
       guard (not (e `elem` s))
       return e

s = x >>= \e -> if (not (e `elem` s)) then return e else mzero

s = concatMap (\e -> if (not (e `elem` s)) then [e] else []) x

s = foldr ((++) . (\e -> if (not (e `elem` s)) then [e] else [])) [] x

s = foldr (\e xs -> if (not (e `elem` s)) then (e:xs) else xs) [] x

s = foldr (\e ys -> if (e `elem` s) then ys else (e:ys)) [] x

然后我们可以开始评估。由于x是非空的，我们可以将其替换为x:xs并内联foldr

let f = (\e ys -> if (e `elem` s) then ys else (e:ys))

s = f x (foldr f [] xs)

s = (\ys -> if (x `elem` s) then ys else (x:ys)) (foldr f [] xs)

s = (\ys -> if (x `elem` f x (foldr f [] xs)) then ys else (x:ys)) (foldr f [] xs)

这就是我们无限循环的地方——为了评估f x (foldr f [] xs)，我们必须评估f x (foldr f [] xs). 您可能会说 的定义s“不够高效”，不足以启动它的自递归。将此与技巧fibs定义进行比较

fibs = 1:1:zipWith (+) fibs (tail fibs)

这是1:1:...为了“足够高效”而开始的。但是，在 的情况下s，没有（简单的）方法可以提高生产力（请参阅下面 Will Ness 的评论，了解一个可怕的解决方法）。

---

如果我们没有 not ，它只会切换 上的分支顺序，if无论如何我们都无法到达。

Answer 3

s = [e | (e:t) <- tails x, not (e `elem` t)]

以上并不是最有效的解决方案，而是展示了如何推断解决方案：为了只包含 x 的元素一次，我们需要确保它是 x 中的最后一个这样的元素。这意味着我们可以在列表的尾部搜索元素的出现。Data.List.tails 生成列表的所有子列表，因此我们可以包含子列表的头部，如果它没有出现在子列表的其余部分中 - 这是子列表的头部是最后一个这样的元素的条件在原始列表中。

---

如果使用该值的函数是严格的（渴望），则引用您正在定义的值可能会导致计算终止。该函数是严格的，如果它总是需要参数的完整值才能产生结果。

例如，长度在列表元素的数量上是严格的——但不一定是列表的实际元素。所以length [[i..] | i <- [1..10]]终止而不计算列表中元素的值（无限列表。然而，length [[i..] | i <- [1..]]不会终止，因为为了返回结果，它需要计算所有元素的存在，这些元素永远不会在开放范围内结束。

然而，

gtlength :: Int -> [a] -> Ordering
gtlength n [] = n `compare` 0
gtlength 0 xs = GT
gtlength n xs = gtlength (n-1) $ tail xs

即使对于无限列表也可以终止，因为它不需要评估整个列表。

您的函数挂起，因为 elem 是严格的。为了测试一个元素是否不存在，它需要评估整个列表，这是不可用的。