2つのリストをマージする

Question

F＃で2つのリストを純粋に機能的な方法でマージしようとしています。私は文法を理解するのに苦労しています。

レッツは、それは私は確信して間違っている、私がこれまで持っている理由[5;2;3;9;8;4]ここ

がある返す必要があり、私は関数を呼び出すときに、私はタプル([5;3;8],[2;9;4])

を持っていると言います。誰かがそれを簡単な方法で説明できるなら、私は感謝します。

let rec interleave (xs,ys) = function 
|([], ys) -> ys 
|(x::xs, y::ys) -> x :: y:: interleave (xs,ys) 

Answer 1

あなたの機能はほとんど権利です。 let f = functionはlet f x = match x withの省略形ですので、明示的な引数は必要ありません。また、あなたのアルゴリズムはいくつかの微調整が必​​要です。

let rec interleave = function //same as: let rec interleave (xs, ys) = match xs, ys with 
    |([], ys) -> ys 
    |(xs, []) -> xs 
    |(x::xs, y::ys) -> x :: y :: interleave (xs,ys) 

interleave ([5;3;8],[2;9;4]) //output: [5; 2; 3; 9; 8; 4] 

Answer 2

一つの重要な点は、関数が正しくないということです。パターンマッチングで(xs, [])という大文字と小文字を区別しなかったので、入力([1;2;3], [])で失敗します。さらに、部分的なアプリケーションで使用する方が簡単になるように、引数はカレー化された形式で優れています。

let rec interleave xs ys = 
    match xs, ys with 
    | [], ys -> ys 
    | xs, [] -> xs 
    | x::xs', y::ys' -> x::y::interleave xs' ys' 

あなたは再帰呼び出しが返された後、それは二回短所に(::)コンストラクタを適用するため、機能がない末尾再帰的であることがわかります。ここでは修正版です。 zipWithし、それを使用してinterleaveを実装する - あなたは、より一般的な高階関数を定義するには、この機会を利用することができます

let interleave xs ys = 
    let rec loop xs ys = 
     seq { 
      match xs, ys with 
      | [], ys -> yield! ys 
      | xs, [] -> yield! xs 
      | x::xs', y::ys' -> 
        yield x 
        yield y 
        yield! loop xs' ys' 
      } 
    loop xs ys |> List.ofSeq 

Answer 3

：それは末尾再帰にする一つの興味深い方法は、シーケンス式を使用しています。

let rec zipWith f xlist ylist = 
    match f, xlist, ylist with 
    | f, (x :: xs), (y :: ys) -> f x y :: zipWith f xs ys 
    | _, _, _ -> [] 

let interleave xs ys = zipWith (fun a b -> [a; b]) xs ys |> List.concat 

編集：

@padは以下の言ったように、F＃はすでに名前List.map2下zipWithを持っています。次のようにだから、interleaveを書き換えることができます。

let interleave xs ys = List.map2 (fun a b -> [a; b]) xs ys |> List.concat 

Answer 4

それはリストの長さが異なる場合にどうするかは明らかではないのですが、ここでは完全に両方のリストを消費し、一般的な、末尾再帰の実装ですOPから：

// 'a list -> 'a list -> 'a list 
let interleave xs ys = 
    let rec imp xs ys acc = 
     match xs, ys with 
     | [], [] -> acc 
     | x::xs, [] -> imp xs [] (x::acc) 
     | [], y::ys -> imp [] ys (y::acc) 
     | x::xs, y::ys -> imp xs ys (y::x::acc) 
    imp xs ys [] |> List.rev 

を

例：迅速な応答のための

> interleave [5;3;8] [2;9;4];; 
val it : int list = [5; 2; 3; 9; 8; 4] 
> interleave [] [1..3];; 
val it : int list = [1; 2; 3] 
> interleave [1..3] [42];; 
val it : int list = [1; 42; 2; 3] 
> interleave [1..3] [42;1337];; 
val it : int list = [1; 42; 2; 1337; 3] 
> interleave [42; 1337] [1..3];; 
val it : int list = [42; 1; 1337; 2; 3]