list - Haskell List Comprehension，其中 x 不能等于列表的元素

Question

我想从元组列表中生成一个元组列表，其中元组的左侧部分仅出现在列表的所有元素的左侧。

基本上我想要的是以下更通用的版本：

[ (x,y) | (x,y) <- [(1,5),(5,2)], x /= 5, x /=2 ]

如果 [(1,5),(5,2)] 是一个名为 list 的变量，那么 x 不能等于 (map snd list) 的任何值。如何将此条件置于列表理解中？（或者我应该使用其他东西吗？比如过滤器？）

Answer 1

那么 x 不能等于 (map snd list) 的任何值

的直接翻译是

x `notElem` map snd list

所以你会使用类似的东西

let xs = [(1,5),(5,2)] in [(x,y) | (x,y) <- xs, x `notElem` map snd xs]

如果列表很长，那效率不高，那么您可以 - 如果类型允许，即是一个实例Ord- 构建一个集合并检查集合中的成员资格

let xs = [(1,5),(5,2)]
    st = Data.Set.fromList (map snd xs)
in [(x,y) | (x,y) <- xs, not (Data.Set.member x st)]

将第一个复杂度降低O(n²)到一个O(n*log n)复杂度。

Answer 2

构造一个包含所有第二个元素的Set（我们称之为seconds），然后只过滤flip notMember seconds . fst. 如果你真的想要的话，你可以很容易地把它写成一个列表理解（但你最终会重写过滤器，那为什么要这样做呢？）。