logo标签列表

无限列表的交集

listhaskellinfinite
9

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

传统方法会在第二个列表是无限的情况下失败，因为你会花费所有时间在第一个列表中检查非匹配元素。

例子：

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

这段代码永远不会返回1，因为它永远不会停止检查ones中的元素0。

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

可能的实现方式是通过遍历两个列表，并花费大约相等的时间将每个列表中之前访问过的元素相互比较。

如果可能的话，我希望还能够忽略列表中的重复项，尽管这不是必需的。

2
什么结果告诉你可以取两个无限列表的交集？我很确定这样并不正确。 - leftaroundabout
@leftaroundabout：你可以使用递增边界。 - Willem Van Onsem
1
@leftaroundabout，如果你想要一个相似且可能更简单的例子，请搜索“有理数的可数性”或者点击这个链接：https://www.google.com/search?q=countability+of+the+rational+numbers 或者 http://www.homeschoolmath.net/teaching/rational-numbers-countable.php。 - Zoey Hewll
@ZoeyHewll 可能是可以的，但不是用这个算法。 - AJF
@AJFarmar，您说的“这个算法”是什么意思？我没有提供任何一个。 - Zoey Hewll
2
问题应该包含“问题”，而不是解决方案。如果您认为自己想出了一个不同和/或更好的答案，请回答您自己的问题（这很好！）。如果问题包含答案，用户无法分别为两个投票（例如，有人可能希望为“不太好的问题”投票一个好答案，而不是同时为问题本身或反之亦然）。 - Bakuriu
6个回答
12
使用 universe包中的笛卡尔积运算符，我们可以编写以下一行代码：
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之前或之后添加你喜欢的去重器。例如，使用nub，你可以这样写：

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

然后让您的计算机加热，因为它不能确定第二个列表中是否深入查看时可能有一个 0。

这种方法比David Fletcher的方法快得多，产生的重复项要少得多，比Willem Van Onsem的方法更快地生成新值，并且不像freestyle的方法那样假设列表已排序（但在这样的列表上速度比freestyle的方法慢得多）。

6

一个解决方法可能是使用递增边界。我们先稍微放宽一下问题：允许输出重复的值。在这种情况下，可以使用以下方法：

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 = A1∩B1 ∪ A2∩B2 ∪ ... ∪ ...

其中A1是一个包含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

现在，由于两个列表都是有限的，该程序将终止，但仍会产生许多重复项。肯定有更好的方法来解决这个问题。

2
更正：列表要么是无限的，要么是空的。如果存在任何交集，它将是无限的；但如果没有共同元素，则为空（当然，如果它是空的，它只会挂起，但这对于任何方法都是保证的）。 - Zoey Hewll
1
@ZoeyHewll：是的，谢谢。我觉得我解决了这个问题，但解决方案仍然可以改进。 - Willem Van Onsem
1
@ZoeyHewll，将这样的列表称为“空”并不完全正确。[]是空列表。一个永远运行，并在永久运行后产生一个值（任何值 - 在这里恰好是空列表）的程序并不代表该值，而代表底部。 - user2407038
@ZoeyHewll 但是 Haskell 列表实际上可以是无限的... 将它们视为无限列表并不仅仅是一种“方便”的推断。任何惰性递归数据结构都可以包含无限值，这几乎是惰性的全部意义所在。从数学角度来看，需要永远“返回”值的计算是底部（undefined），因为绝对没有办法区分这样的计算（在你已经形式化“计算”的理论中）和一个永远无限循环什么也不做的计算（这通常被称为“停机问题”）。 - user2407038
@user2407038 我知道停机问题。当我说“数学角度”时，我的意思是像集合论一样，而不是像计算理论一样。虽然在有限时间内无法计算两个无限列表的交集，但从数学上讲，如果你知道它们必然是互斥的，你可以陈述它们的集合交集是否为空。 - Zoey Hewll
显示剩余2条评论
5
这是一种方法。对于每个 x，我们制作一个可能性列表，其中仅包含在 ys 中出现的 x 的 Just x。然后，我们交错所有这些列表。
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]
啊，所以你仍然遍历一个列表并检查另一个列表是否匹配，但你已经交错了结果... - Zoey Hewll
我还无法弄清楚如何改进交错，主要是因为我无法弄清楚当前的处理方式。我可以追踪代码，但我无法弄清楚foldr对元素顺序的影响结果会是什么。 - Zoey Hewll
1
它更喜欢早期的列表，比下一个列表快两倍，就像在 interleave ["a1", "a2", "a3", "a4", "a5", a6"] (interleave ["b1", "b2", "b3"] ["c1", "c2", "c3"]) 中每隔一个元素是一个 a。 - David Fletcher
2
您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Daniel Wagner
@DanielWagner 你的代码在哪里？此外，在这个例子中，我只是用 diagonal 替换了 foldr interleave []，以产生一个易于（对我来说）阅读和表达的函数。虽然你的代码更简洁，但我发现它需要更多的工作来解释。 - Zoey Hewll
显示剩余6条评论
4
如果列表中的元素是有序的，那么你很容易做到这一点。
intersectOrd :: Ord a => [a] -> [a] -> [a]
intersectOrd [] _ = []
intersectOrd _ [] = []
intersectOrd (x:xs) (y:ys) = case x `compare` y of
    EQ -> x : intersectOrd xs ys
    LT -> intersectOrd xs (y:ys)
    GT -> intersectOrd (x:xs) ys
另请参阅 data-ordlist 包中的 isect；该包还提供了许多其他方便的操作，可用于处理有序（和潜在无限）列表。 - Daniel Wagner
2

这里是另一种选择，利用 Control.Monad.WeightedSearch 技术。

import Control.Monad (guard)
import Control.Applicative
import qualified Control.Monad.WeightedSearch as W

我们首先定义挖掘列表内部的成本。访问尾部将额外增加1个单位的成本。这将确保在两个无限列表中进行公平调度。

eachW :: [a] -> W.T Int a
eachW = foldr (\x w -> pure x <|> W.weight 1 w) empty

然后，我们只需忽略无限列表。

intersection :: [Int] -> [Int] -> [Int]
intersection xs ys = W.toList $ do
   x <- eachW xs
   y <- eachW ys
   guard (x==y)
   return y

使用MonadComprehensions可以更好地实现以下内容:

intersection2 :: [Int] -> [Int] -> [Int]
intersection2 xs ys = W.toList [ y | x <- eachW xs, y <- eachW ys, x==y ]
0

解决方案

最终我采用了以下实现方式，这是对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) ys 计算出一个比较列表，其中包含 xs 和 ys 元素之间的比较结果。列表索引分别指定了 ys 和 xs 中的索引位置。例如，(map matches) ys !! 3 !! 0 表示 ys !! 3 与 xs !! 0 的比较结果，如果这些值不同，则为 Nothing。如果这些值相同，则为该值的 Just。

diagonals 接受一个列表的列表，并返回一个列表的列表，其中第n个输出列表包含来自前n个列表中的每个元素。另一种概念化方法是 (diagonals . map matches) ys !! n 包含在 xs 和 ys 中索引之和为 n 的元素之间的比较。
diagonal 简单地是 diagonals 的扁平版本 (diagonal = concat diagonals)

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

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

注意
(diagonal . map (catMaybes . matches)) ys 不起作用：catMaybes . matches 仅在找到匹配项时才产生结果，而不是在没有匹配项时也产生Nothing，因此交错无法分配工作。

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

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接