Fタプルのリストをマップされたタプルのリストにシャープに変換する

Question

ペアのリストをリレーションに変換する関数を宣言します。このフォームで

[(2,["c";"b"]);(1,["a"])] 

：このに

[(2,"c");(1,"a");(2,"b")] 

：

toRel:(’a*’b) list -> Rel<’a,’b> 

任意のアイデアを

type Relation<'a,'b> = ('a * 'b list) list 

基本的に、これを回しますか？これは宿題ではなく、単なる自己学習です。このフォームは、フォームが蓄積を許さないと考えると、私はちょっと困ります。

Answer 1

[(2,"c");(1,"a");(2,"b")] 
|> List.groupBy fst 
|> List.map (fun (x,y)->x,List.map snd y) 

結果：

[(2, ["c"; "b"]); (1, ["a"])] 

型推論がtoRelビットに便利です：

let toRel xs = 
    xs 
    |> List.groupBy fst 
    |> List.map (fun (x,y)->x,List.map snd y) 

使用法：

toRel [(2,"c");(1,"a");(2,"b")] 

Answer 2

さまざまな組み込み関数を使用することができますし、動作を再構築するための変換特別な関数を最初から構築するための再帰に関する基本的な知識を持つことも良いことです。

また、より大きな問題を解決する方法を学ぶために、問題をより小さな問題に分割することを学ぶために、再帰でこれを行うことをお勧めします。

あなたは再帰的な方法で考えるならば、あなたはTODOが必要なもの：

1. あなたは一つの要素を取得するために、リストの先頭を削除します。
2. 次に、キーと指定したキーのすべての値を含むタプルを作成します。
3. 処理した現在のキーですべての要素を削除し、このリストで繰り返します。
4. 入力リストが空の場合、出力も空です。

だから、で始まる：

let rec group list = 
    if List.isEmpty list then [] 
    else 
     ??? 

あなたはList.headと、リストの最初の要素を削除します。しかし、我々はまた、 の2つのコンポーネントにタプルを抽出したい。これを達成する

let k,v = List.head list 

私たちが作成したいのは、同じキーを持つ新しいタプルですが、入力リストのすべての値です。まだ関数はありませんが、キーとリストを渡すことができる関数valuesOfがあると仮定し、定義されたキーのすべての値を返します。あなたは私たちがkとして2を持っているでしょうし、私たちはvaluesOf 2 list戻り["b";"c"]を想定して定義された入力リストの最初の繰り返しで

(k, (valuesOf k list)) 

。

したがって、上記のコードは値として(2, ["b";"c"])を返します。今再帰呼び出し。キーとリストを渡すことができる関数removeKeyがあると仮定し、指定されたキーのすべての要素が削除された新しいリストを返します。唯一

(group (removeKey k list)) 

あなたは：例として

(removeKey k list) 

removeKey 2 [(1,"a");(2,"a");(2,"b");(3,"a")] 

はremoveKeyリターンはあなたが上で再発する必要がある1つであることを

[(1,"a");(3,"a")] 

この新しいリストを返す必要がありますボットを入れなければならないh個まとめて。戻りたいものは、再帰的な結果を持つ新しいタプルです。

(k, (valuesOf k list)) :: (group (removeKey k list)) 

と1つの機能として。

let rec group list = 
    if List.isEmpty list then [] 
    else 
     let k,v = List.head list 
     (k, (valuesOf k list)) :: group (removeKey k list) 

我々はまだ行われていない、我々はまだvaluesOfとremoveKeyを作成する必要があります。

let rec valuesOf key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then v :: (valuesOf key list) 
     else (valuesOf key list) 

valuesOf代わりList.headまたはList.tailを使用しての、リストを分解するためにパターンマッチングを使用しています。要素が指定されたキーを持っているかどうかを確認するだけです。それが残っている場合は、残りのリストと連結した現在の値を返します。それ以外の場合は、再帰呼び出しの結果を返し、現在の値を削除します。

removeKeyも同様です。タプルのキーが一致しているかどうかをチェックし、そうであれば要素全体を削除し、再帰呼び出しを返します。それ以外の場合は、再帰呼び出しで現在の要素を返します。

let rec removeKey key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then (removeKey key list) 
     else x :: (removeKey key list) 

となっています。一気にすべて

let rec valuesOf key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then v :: (valuesOf key list) 
     else (valuesOf key list) 

let rec removeKey key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then (removeKey key list) 
     else x :: (removeKey key list) 

let rec group list = 
    if List.isEmpty list then [] 
    else 
     let k,v = List.head list 
     (k, (valuesOf k list)) :: group (removeKey k list) 

group [(2,"c");(1,"a");(2,"b");(2,"d");(3,"a");(1,"b")] 
// returns: [(2, ["c"; "b"; "d"]); (1, ["a"; "b"]); (3, ["a"])] 

上記の関数はtail-recursiveではありません。しかしvaluesOfとremoveKeyをList.foldまたはList.foldBackで簡単に書き直すことができます。ここでは、要素の順序が変わるかどうかは問題ではないと仮定して、List.foldを使用します。我々は全体のリストにアクセスする必要があるため

let valuesOf key list = 
    List.fold (fun acc (k,v) -> 
     if k = key 
     then v :: acc 
     else acc 
    ) [] list 

let removeKey key list = 
    List.fold (fun acc (k,v) -> 
     if k = key 
     then acc 
     else (k,v) :: acc 
    ) [] list 

groupは簡単List.foldまたはList.foldBackで書き換えができません。しかし、テール再帰を達成することはまだ難しいことではありません。

let group list = 
    let rec loop result list = 
     if List.isEmpty list then result 
     else 
      let k,v = List.head list 
      loop 
       ((k, (valuesOf k list)) :: result) 
       (removeKey k list) 
    loop [] list 

何千ものキーと値のペアを持つリストがない場合は、非テール再帰関数を保持することもできます。それはあなた自身再帰関数のような種類を作成することができるはずList.groupByとList.mapのように、既に提供された機能を持つ小さなコードを作成するために、良い感じている場合でも

。どうして？

不変リンクリストは再帰的に定義されたデータ構造であり、再帰的関数を扱うのは当然のことです。このような関数を自分で作成する方法がわからない場合は、独自の再帰的なデータ構造を作成する瞬間に問題が発生します。既に使用できるgroupByとmapのような事前定義済み関数はゼロです。これらの機能を自分で構築する必要があります。

Listモジュールに定義されている機能を再構築しようとしたり、ここに記載されているようなことは、実際に自分で行うべき訓練の良い方法です。