list - 无限列表的交集

Question

我从可计算性理论中知道可以取两个无限列表的交集，但是我找不到在 Haskell 中表达它的方法。

一旦第二个列表是无限的，传统方法就会失败，因为您花费所有时间检查它是否存在第一个列表中的不匹配元素。

例子:

let ones = 1 : ones -- an unending list of 1s
intersect [0,1] ones

这永远不会产生 1 ，因为它永远不会停止检查 ones对于元素 0 .

一个成功的方法需要确保每个列表的每个元素都将在有限时间内被访问。

这可能是通过遍历两个列表，并花费大约相等的时间检查每个列表中所有先前访问过的元素。

如果可能的话，我还想有一种方法来忽略列表中的重复项，因为有时这是必要的，但这不是必需的。

Answer 1

使用 universe package's Cartesian product operator我们可以这样写:

import Data.Universe.Helpers

isect :: Eq a => [a] -> [a] -> [a]
xs `isect` ys = [x | (x, y) <- xs +*+ ys, x == y]
-- or this, which may do marginally less allocation
xs `isect` ys = foldr ($) [] $ cartesianProduct 
    (\x y -> if x == y then (x:) else id)
    xs ys

在 ghci 中尝试:

> take 10 $ [0,2..] `isect` [0,3..]
[0,6,12,18,24,30,36,42,48,54]

如果输入列表没有任何重复项，则此实现不会产生任何重复项；但如果他们这样做了，您可以在调用 isect 之前或之后添加您最喜欢的 dup-remover。 .例如，使用 nub ，你可以写

> nub ([0,1] `isect` repeat 1)
[1

然后很好地加热您的计算机，因为它永远无法确定可能没有 0如果它看起来足够深，则在第二个列表中的某个地方。
这种方法比 David Fletcher 的方法快得多，产生的重复次数更少，产生新值的速度也比 Willem Van Onsem 的快得多，并且不假设列表像自由式那样排序(但因此在这种列表上比自由式慢得多)。