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)复杂性.