F# 交叉两个列表

Question

我想要对两个已排序的列表进行交集操作，使得 intersect ([1;1;1;2;2], [1;1;2;4]) 返回 [1;1;2]。到目前为止，我做出了如下尝试：

let rec intersect (xs, xs') =
    match xs, xs' with
    | ([], [])             -> []
    | (x::tail, [])        -> []
    | ([], x'::tail')      -> []
    | (x::tail, x'::tail') -> if x = x' then x::intersect(tail, tail')
                              else intersect(tail, xs') 

但我不太确定接下来该怎么做。这个函数接受一个包含两个列表的元组，我假设当每个列表的头相等时，开始构建一个新列表，但是我缺少一些我无法完全理解的东西，并希望得到一些提示。

编辑：我知道我可以使用库函数轻松解决这个问题，但那没什么乐趣 ：）

- Khaine775

---

输入列表是否已排序？ - Lee

是的，它们是。我会添加那个信息。 - Khaine775

我有一个解决方案，但我不会发布它...在模式匹配中有更多要处理的情况：如果其中一个列表为空怎么办？在“if”表达式中还有另一种情况需要处理：如果 x<x' 怎么办？使用 else 处理。最后，在模式匹配中不要重复使用名称 xs，因为某些情况下需要原始的 xs。xs' 同理。 - TheQuickBrownFox

if是一个表达式，而不是语句。最后一个分支应该只写else，而不是else if。你在第三次编辑中更接近正确了。 - TheQuickBrownFox

你已经接近成功了，但是如果你交换参数，你的函数就不起作用了。我会把我的答案贴出来。 - TheQuickBrownFox

Answer 1

这是我想到的内容：

以下是我的建议：

let rec intersect xs ys =
    match xs, ys with
    | x::xs', y::ys' ->
        if   x = y then x :: intersect xs' ys'
        elif x < y then intersect xs' ys
        else            intersect xs  ys'
    | _ -> []

我撤销了参数的元组化，因为我认为没有理由这样做。

x::xs' 只会匹配非空列表，因此基本情况匹配可以移动到结尾并简化为 _。

我还改变了名称。我发现最好只在名称中使用下划线后缀，指的是已经存在值的下一个迭代。在这种情况下，您有一个列表 xs，它的尾部是 xs'。

- TheQuickBrownFox

---

如果重新排列匹配案例，您可以将最后一个案例简化为： _ -> [] - Lars

Answer 2

我建议您将参数重命名为l1和l2，并匹配(x :: xs)和(y :: ys)，即：

let rec intersect (l1, l2) =
    match l1,l2 with
    ...
    | (x :: xs), (y :: ys) when x < y -> 

您所缺少的两种情况是，当两个元素不同时，即x < y或x > y。如果x < y，则由于列表已排序，在l2的前面有一个或多个元素可以忽略，因为它们不能存在于l1中，例如：

x = 5且l2 = [1;2;4;5]，则可以丢弃[1;2;4]以找到下一个匹配项。

我建议您编写一个实用程序函数，该函数会丢弃无法找到的列表前面的元素，例如：

//removes items from the front of l which cannot occur in a sorted list with head e
let rec skipUntil e l = ...

一旦您删除了这些元素，就可以继续搜索。

当x > y时，处理方式是对称的。

- Lee