F＃2つのリストを交差する

Question

したがって、intersect ([1;1;1;2;2], [1;1;2;4])が[1;1;2]を返すように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') 

しかし、私はここからどこに行くのかは分かりません。この関数は2つのリストを含むタプルを取ります。そして、各リストの頭が互いに等しいとき、私は新しいリストを構築し始めますが、私は決して分からないものを見逃していますヒントを得る。

編集：私は、私は簡単にこの問題を解決するためのライブラリ関数を使用することができます承知しているが、それは何の楽しい:)

Answer 1

は私が思いついたものです。

x::xs'は、空でないリストと一致するだけなので、ベースケースの一致を末尾に移動して_に簡略化できます。

名前を変更しました。私はそれが既存の値の次の反復を参照する名前でのみティックサフィックスを使用する方が良いことがわかります。この場合、リストはxs、テールはxs'です。

Answer 2

私はあなたが(x :: xs)に対してl1とl2と一致するように、引数の名前を変更示唆して(y :: ys)すなわち

ません

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

あなたが紛失している2つのケースは、2つのヘッドが異なる場合です。つまり、x < yまたはx > yです。 x < yの場合、リストがソートされているため、l2の前には、l1など存在しないため無視することができる1つ以上の要素があります。

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が対称的に扱われる場合。私はそれのための理由を見ていないとして、私は、引数のtuplingを削除

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' 
    | _ -> [] 

：ここ