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＃相交兩個列表

回答

相關問題