F＃相交两个列表

所以我想交叉两个排序列表，这样intersect ([1;1;1;2;2], [1;1;2;4])将返回[1;1;2]。我来了这么远：F＃相交两个列表

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')

但我不太确定该从哪里出发。该函数需要一个包含两个列表的元组，并且我假设当每个列表的头部彼此相等时，我开始建立一个新列表，但是我错过了一些我无法想象并期望的东西得到一个提示。

编辑：我知道我可以使用库函数来轻松解决这个，但是这没有乐趣:)

来源

2017-10-12 Khaine775

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

是的，他们是。我会添加这些信息。 – Khaine775

我有一个解决方案，但我不会发布它...在模式匹配中处理更多的情况：如果只有一个列表是空的，该怎么办？在'if'表达式中还有另外一种情况需要处理：如果'x TheQuickBrownFox

这就是我想出了：

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'只会匹配一个非空列表，所以基本大小写匹配可以移动到最后并简化为_。

我也改了名字。我发现最好只在引用已有值的下一次迭代的名称中使用tick后缀。在这种情况下，您有一个清单xs，其尾部是xs'。

来源

2017-10-12 13:53:19 TheQuickBrownFox

如果您重新排列您的匹配案例，您可以简化最后一种情况： _ - > [] – Lars

@Lars好点。更新。 – TheQuickBrownFox

我建议你重命名你的论点来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的情况。

来源

2017-10-12 13:25:59 Lee

F＃相交两个列表

回答

相关问题