2012-02-01 33 views
10

F#で2つのリストを純粋に機能的な方法でマージしようとしています。私は文法を理解するのに苦労しています。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) 

答えて

11

あなたの機能はほとんど権利です。 let f = functionlet 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] 
+1

おかげでなく、引数はありませんなぜ私はかなり理解していません。 >]どのように関数を呼び出すでしょうか? [< – user1072706

+1

>あなたは通常通りに関数を呼び出します。コードの最後の行は、使い方を示しています。 [このMSDNの記事](http://msdn.microsoft.com/en-us/library/dd233242.aspx)(ページの上部)を参照してください。これは、2つの形式の(同等の)関数宣言を示しています。 – Daniel

8

一つの重要な点は、関数が正しくないということです。パターンマッチングで(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 
+3

+1テール再帰的な解答を与えるために、私は個人的にはシーケンス表現ではなく、連続またはアキュムレータ+ 'List.reverse'を使用していました。 – ildjarn

+1

@ildjarn:あなたは[この回答](http://stackoverflow.com/a/7199989/162396)の発見に興味があるかもしれません(彼らはalgoに関係なく一貫している傾向があります)。要するに、アキュムレータ+ 'List.rev'を使うと、一般的に連続よりもはるかに良い結果が得られます。 – Daniel

+0

@Danielのリンクに感謝します。継続とアキュムレータ+ 'List.rev'は興味深い可能性がありますが、私はこのバージョンを' Seq'を使って非末尾再帰的なものに近づけるよう書いています。 – pad

2

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

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.map2zipWithを持っています。次のようにだから、interleaveを書き換えることができます。

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

'List.map2'はHaskellの' zipWith'と同じことをします。そして、F#listは怠惰ではないので、あなたのソリューションの中で 'zipWith'を使うと、一時的なリストが作成されます。 – pad

+0

@pad、ああ、ありがとう。前に 'List.map2'を見たことがありましたが、何とかそれを忘れました。中間コレクションの作成に関して、私はそれを認識していますが、これは 'List'のほぼすべての高次関数に当てはまるものです。 :-) – missingfaktor

0

それはリストの長さが異なる場合にどうするかは明らかではないのですが、ここでは完全に両方のリストを消費し、一般的な、末尾再帰の実装です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] 
関連する問題