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

Question

我试图从列表中选择这样的独特元素:

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

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

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

Answer 1

我没有太大的哈斯克尔儿的,但是这好像你刚刚编写了东西有点像¹ 罗素悖论.你不是要求一个列表,s其元素是那些x,但不是s？

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

所以,考虑当你试图要求第一个元素时会发生什么s.好吧,第一个元素e是1,所以1将是s if 的第一个元素not (1 `elem` s).好吧,是(1 `elem` s)吗？我们可以通过迭代元素s和查看是否1出现来检查.那么,让我们从s...... 的第一个元素开始吧

一般来说,假设有些n是元素s.那一定是真的吗？ n必须是x(易于检查)的元素,也不是元素s.但我们认为它是一个元素s.这是一个矛盾.因此,no n可以是一个元素s,所以s必须是空列表.不幸的是,Haskell编译器没有做我们刚刚做的证明,它试图以编程方式计算它的元素s.

要从列表中删除重复项,您需要Neil Brown在评论中推荐的函数,nub来自Data.List:

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

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

1. 这实际上并不是拉塞尔的悖论; 拉塞尔的悖论是关于一个只包含那些不包含自己的集合的集合. 该集合不可能存在,因为如果它包含自身,那么它不能包含它自己,如果它不包含它自己,那么它必须包含它自己.

Answer 2

请注意,虽然Russel的Paradox有助于暗示这可能是不可计算的,但即使您将其更改为,它仍然会失败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和内联a 替换它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在下面的评论,以获得一个恶魔般的解决方法).

如果我们没有那里,它只是切换分支的顺序if,我们从来没有达到过.