无限列表的交集

Question

我从可计算性理论中知道可以采用两个无限列表的交集,但我找不到在Haskell中表达它的方法.

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

例:

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

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

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

也许,这将通过迭代两个列表,并花费大致相等的时间来检查每个列表中的所有先前访问的元素彼此.

如果可能的话,我还想有办法忽略列表中的重复项,因为它偶尔是必要的,但这不是必需的.

Answer 1

使用Universe软件包的笛卡尔积运算符,我们可以编写这个单行程序:

import Data.Universe.Helpers

isect :: Eq a => [a] -> [a] -> [a]
xs `isect` ys = [x | (x, y) <- xs +*+ ys, x == y]

在ghci中尝试:

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

如果输入列表没有任何副本,则此实现不会产生任何重复; 但是如果他们这样做,你可以在打电话之前或之后使用你最喜欢的复印机isect.例如,nub你可以写

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

然后加热你的计算机非常好,因为0如果它看起来足够深,它永远不能确定某个地方的第二个列表中可能没有.

这种方法明显快于David Fletcher,比Willem Van Onsem更快地产生更少的重复数据并产生新的值,并且不假设列表像自由式一样被排序(但因此在这些列表上比自由式更慢).

Answer 2

一个想法可能是使用递增边界.让我们首先放松一下这个问题:允许产生重复的值.在这种情况下,您可以使用:

import Data.List (intersect)

intersectInfinite :: Eq a => [a] -> [a] -> [a]
intersectInfinite = intersectInfinite' 1
    where intersectInfinite' n = intersect (take n xs) (take n ys) ++ intersectInfinite' (n+1)

换句话说,我们声称:

A∩B= A ₁ ∩B ₁ ∪阿₂ ∩B ₂ ∪...∪...

以A ₁是含有一组第i个元素甲(是有一组没有秩序,但让我们说有某种方式的顺序).如果集合包含较少的元素,则返回完整集.

如果c在A(在索引i处)和在B中(在索引j处),则c将在段(非索引)max(i,j)中发出.

因此,无论给定列表是否有限,这将始终生成无限列表(具有无限量的重复).唯一的例外是当你给它一个空列表时,在这种情况下它将需要永远.尽管如此,我们确保交叉点中的每个元素至少发射一次.

使结果有限(如果给定列表是有限的)

现在我们可以更好地定义我们的定义 首先我们制作一个更高级的版本take,takeFinite(让我们首先给出一个直接但不是非常有效的定义):

takeFinite :: Int -> [a] -> (Bool,[a])
takeFinite _ [] = (True,[])
takeFinite 0 _  = (False,[])
takeFinite n (x:xs) = let (b,t) = takeFinite (n-1) xs in (b,x:t)

现在我们可以迭代加深,直到两个列表都到达结尾:

intersectInfinite :: Eq a => [a] -> [a] -> [a]
intersectInfinite = intersectInfinite' 1

intersectInfinite' :: Eq a => Int -> [a] -> [a] -> [a]
intersectInfinite' n xs ys | fa && fb = intersect xs ys
                           | fa = intersect ys xs
                           | fb = intersect xs ys
                           | otherwise = intersect xfa xfb ++ intersectInfinite' (n+1) xs ys
    where (fa,xfa) = takeFinite n xs
          (fb,xfb) = takeFinite n ys

现在这将终止,因为两个列表都是有限的,但仍会产生大量重复.肯定有更多方法可以解决这个问题(如果我有更多时间,将会更新).

Answer 3

这是一种方式.对于每一个x我们制作一个Just x只有在哪里x出现的maybes列表 ys.然后我们交错所有这些列表.

isect :: Eq a => [a] -> [a] -> [a]
isect xs ys = (catMaybes . foldr interleave [] . map matches) xs
  where
    matches x = [if x == y then Just x else Nothing | y <- ys]

interleave :: [a] -> [a] -> [a]
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs

也许它可以使用某种更公平的交错来改进 - 在下面的例子中它已经很慢了,因为(我认为)它正在进行指数级的工作.

> take 10 (isect [0..] [0,2..])
[0,2,4,6,8,10,12,14,16,18]

Answer 4

解决方案

我最终使用了以下实现；对 David Fletcher 的答案稍作修改：

isect :: Eq a => [a] -> [a] -> [a]
isect [] = const [] -- don't bother testing against an empty list
isect xs = catMaybes . diagonal . map matches
    where matches y = [if x == y then Just x else Nothing | x <- xs]

可以用 nub 来增强它以过滤掉重复项：

isectUniq :: Eq a => [a] -> [a] -> [a]
isectUniq xs = nub . isect xs

解释

行的isect xs = catMaybes . diagonal . map matches

(map matches) ysxs计算和的元素之间的比较列表ys，其中列表索引分别指定ys和中的索引xs： ie将表示与 的(map matches) ys !! 3 !! 0比较，如果这些值不同，则为 。如果这些值相同，那就是那个值。ys !! 3xs !! 0NothingJust

diagonals接受一个列表列表并返回一个列表列表，其中第 n 个输出列表包含前 n 个列表中的每个元素。另一种概念化方法是包含索引为且总和为(diagonals . map matches) ys !! n的元素之间的比较。只是( )的平面版本xsysn
diagonaldiagonalsdiagonal = concat diagonals

因此是和(diagonal . map matches) ys的元素之间的比较列表，其中元素大致按和的元素索引之和排序；这意味着早期元素与后期元素的比较与中间元素相互比较的优先级相同。xsysysxs

(catMaybes . diagonal . map matches) ys是仅包含两个列表中的元素的列表，其中元素大致按所比较的两个元素的索引之和排序。

Note
(diagonal . map (catMaybes . matches)) ys不起作用：仅在找到匹配项时才产生，而不是在不匹配时产生，因此交错不会分配工作。 catMaybes . matchesNothing

相比之下，在所选择的解决方案中，Nothing和Just值的交错diagonal意味着程序将注意力分散在“搜索”多个不同元素之间，而不是等待一个元素成功；而如果Nothing在交错之前删除这些值，则程序可能会花费太多时间等待对给定元素的无结果“搜索”成功。

因此，我们会遇到与原始问题相同的问题：当一个元素与另一个列表中的任何元素都不匹配时，程序将挂起；而所选的解决方案仅在任一列表中都找不到任何匹配项时才会挂起。