2次元リスト（OCaml）の同じ頭のリストを結合する

Question

私はOCamlのリストのリストを使っていますが、同じヘッドを共有するすべてのリストを結合する関数を作成しようとしています。これは私がこれまで持っているものである、と私はList.hd組み込み関数の使用することが、驚くことではないが、私は失敗し、「HD」エラーを取得しています：

let rec combineSameHead list nlist = match list with 
| [] -> []@nlist 
| h::t -> if List.hd h = List.hd (List.hd t) 
    then combineSameHead t nlist@uniq(h@(List.hd t)) 
    else combineSameHead t nlist@h;; 

ですから、例えば、I場合このリストを持っている：

[[Sentence; Quiet]; [Sentence; Grunt]; [Sentence; Shout]] 

私はにそれを結合したい：

[[Sentence; Quiet; Grunt; Shout]] 

私が書いた関数uniqのは、ちょうど、リスト内のすべての重複を削除します。私はこれをどうやって完了するか教えてください。前もって感謝します！

Answer 1

パターンマシニングが通常より明確で、エラーを起こしにくいため、私は一般的にList.hdのような機能を避けます。この場合、ifはガードパターン（パターンの後にwhen句）に置き換えることができます。私はあなたのエラーを引き起こす何が起きていると思いますtが[]であるときあなたのコードが失敗することです。ガードされたパターンは、ケースをより明示的にすることによってこれを避けるのに役立ちます。したがって、match式の中で句として(x::xs)::(y::ys)::t when x = yを実行して、リストの最初の2つの要素の頭が同じであることを確認できます。 OCamlでは、ガードを除いて同一のいくつかの連続したパターンを持つことは珍しいことではありません。

その他のもの：[]@nlistは必要ありません。nlistと同じです。

また、あなたのnlist@hのように見え、同様の表現が再帰呼び出しにそれらを渡す前にリストを連結しようとしています。しかし、OCamlでは、関数アプリケーションはどの演算子よりも緊密に結びついているので、実際には再帰呼び出しの結果をhに追加します。

私は、機能の正しいバージョンを持っていません。しかし、私はそれを守ったパターンで書いて始め、それであなたがそれをどのように働かせるかを見ていきます。

Answer 2

Mapまたはハッシュテーブルを使用して、各ヘッドで見つかったヘッドと要素を追跡することを検討してください。

# combineSameHead [["A"; "a0"; "a1"]; ["B"; "b0"]; ["A"; "a2"]] 
- : list (list string) = [["A"; "a0"; "a1"; "a2"]; ["B"; "b0"]] 

Answer 3

あなたの意図した操作が簡単な再帰的な説明があります：再帰的に、その後、あなたのリストの尾を処理し、同じヘッドとのリストは、この例のように、隣接していない場合nlist補助リストは非常に有用ではありません同じヘッドで始まり、見つかった場合はヘッド以外のすべての要素を挿入し、それ以外の場合は最後に追加するリストを探すヘッドで「挿入」操作を実行します。その結果を元に戻して、目的のリストを取得することができます。

OCamlでは、このアルゴリズムは次のようになります。私はおそらく提案antonakos何の線に沿って何かをやっているだろう

let process list = 
    let rec insert (head,tail) = function 
    | [] -> head :: tail 
    | h :: t -> 
     match h with 
     | hh :: tt when hh = head -> (hh :: (tail @ t)) :: t 
     | _ -> h :: insert (head,tail) t 
    in 
    let rec aux = function 
    | [] -> [] 
    | [] :: t -> aux t 
    | (head :: tail) :: t -> insert (head,tail) (aux t) 
    in 
    List.rev (aux list) 

Answer 4

。それは、リスト内の検索のO（n）コストを完全に避けるでしょう。また、StringSet.t StringMap.tを使用すると、さらに処理しやすくなります。もちろん、読みやすさが最も重要であり、私はまだその基準の下でこの保持を見つける。

あなただけの標準ライブラリを使用して多くのことを行うことができます

module OrderedString = 
    struct 
     type t = string 
     let compare = Pervasives.compare 
    end 

module StringMap = Map.Make (OrderedString) 
module StringSet = Set.Make (OrderedString) 

let merge_same_heads lsts = 
    let add_single map = function 
     | hd::tl when StringMap.mem hd map -> 
      let set = StringMap.find hd map in 
      let set = List.fold_right StringSet.add tl set in 
      StringMap.add hd set map 
     | hd::tl -> 
      let set = List.fold_right StringSet.add tl StringSet.empty in 
      StringMap.add hd set map 
     | []  -> 
      map 
    in 
    let map = List.fold_left add_single StringMap.empty lsts in 
    StringMap.fold (fun k v acc-> (k::(StringSet.elements v))::acc) map [] 

Answer 5

：

(* compares the head of a list to a supplied value. Used to partition a lists of lists *) 
let partPred x = function h::_ -> h = x 
    | _ -> false 

let rec combineHeads = function [] -> [] 
    | []::t -> combineHeads t (* skip empty lists *) 
    | (hh::_ as h)::t -> let r, l = List.partition (partPred hh) t in (* split into lists with the same head as the first, and lists with different heads *) 
    (List.fold_left (fun x y -> x @ (List.tl y)) h r)::(combineHeads l) (* combine all the lists with the same head, then recurse on the remaining lists *) 

combineHeads [[1;2;3];[1;4;5;];[2;3;4];[1];[1;5;7];[2;5];[3;4;6]];; 
- : int list list = [[1; 2; 3; 4; 5; 5; 7]; [2; 3; 4; 5]; [3; 4; 6]] 

しかし、これは（パーティション、fold_left及び連結はすべてO（n）とされている）は、高速ではありません。