OCamlでリストを手動で減らす

Question

アソシエーションリストを作成する簡単なOCaml関数を書いています。入力は、stringと同じ順序でユニークでない単語のリストに変換された文字列であり、出力は（単語、[リストのインデックス]）の関連リストです。

例は

let f "a b c b a b" = ... 

expected output => [("a", [0,4]), ("b", [1,3,5]), ("c", [2])] # order not important 

これまでのところ、私はこの中間出力に

[("b", 5); ("a", 4); ("b", 3); ("c", 2); ("b", 1); ("a", 0)] 

を得るために管理しているが、私は最終的な結果にこれを削減する方法を理解しようとして立ち往生しています。

元の入力からHashtblを作成する方が適切でしょうか？次に、Hashtbl - >list ??

中間結果を減らすのは簡単ですか？私が働いている環境はList.reduceにアクセスできないので、手動でreduce関数を書く必要があります。

これを見てみると、Hashtblは単語の数が増えるにつれて効率が良いようです。

EDIT：Hashtblは確かに行く方法のようです。私はすでに、次のハッシュテーブルがあります。

"a" : [4,0], "b" : [5,3,1], "c" : [2] 

をしかし、私は今のリストに変換する方法を見つけ出すことはできません。 Hashtbl.iterはすべての個々のバインディングで動作します。たとえば、目的を破る("a", 4)と("a", 0)を別々に（私の理解で）繰り返します。提案？

Answer 1

ハッシュテーブルの説明がわかりません。ハッシュテーブルのタイプは(string, int) Hashtbl.tですか、それとも(string, int list) Hashtbl.tですか？後者の場合は、Hashtbl.iterまたは（おそらく良い）Hashtbl.foldを使用してください。

あなたのハッシュテーブルを使用すると、おそらく代わりに、個々のintのintのリストを保持するようにコードを書き換えることができ(string, int) Hashtbl.t型である場合。その後、タイプは(string, int list) Hashtbl.tになります。

更新

あなたのハッシュテーブルは、タイプ(string, int list) Hashtbl.tである場合、あなたは各キーに対して1つだけのエントリを持っていることを確認した場合、あなただけのiterまたはfoldを使用することができます。

文書は次のような現象記述されています。あなたは古いものを削除せずにハッシュテーブルに新しいエントリを追加するHashtbl.addを使用する場合は

# let h = Hashtbl.create 10;; 
val h : ('_a, '_b) Hashtbl.t = <abstr> 
# Hashtbl.add h "a" 3;; 
- : unit =() 
# Hashtbl.add h "a" 4;; 
- : unit =() 
# h;; 
- : (string, int) Hashtbl.t = <abstr> 
# Hashtbl.iter (fun s i -> Printf.printf "%s %d\n" s i) h;; 
a 4 
a 3 
- : unit =() 
# 

を、エントリが蓄積されます。あなたはHashtbl.replaceではなくHashtbl.addを使用する場合は

は、物事はより合理的に動作します。あなたは右のタイプのハッシュテーブルを持っており、自分のエントリを更新するためにHashtbl.replaceを使用する場合は

# let h = Hashtbl.create 10;; 
val h : ('_a, '_b) Hashtbl.t = <abstr> 
# Hashtbl.replace h "a" 3;; 
- : unit =() 
# Hashtbl.replace h "a" 4;; 
- : unit =() 
# h;; 
- : (string, int) Hashtbl.t = <abstr> 
# Hashtbl.iter (fun s i -> Printf.printf "%s %d\n" s i) h;; 
a 4 
- : unit =() 

あなたはOKになります。

Answer 2

Hashtbl

let my_hash = Hashtbl.create 12;; 
let l=[("b", 5); ("a", 4); ("b", 3); ("c", 2); ("b", 1); ("a", 0)] ;; 
List.iter (fun (k,v) -> 
    Hashtbl.add my_hash k v 
) l;; 

プログラムここで

let (opt_k',kacc,l)= 
    Hashtbl.fold (fun k v (opt_k',kacc,l) -> 
    match opt_k' with 
     | None -> (Some k,v::kacc,l) 
     | Some k' -> if k=k' then (opt_k',v::kacc,l) else (Some k,v::[],(k',kacc)::l) 
) my_hash (None,[],[]) 
in 
match opt_k' with 
    | Some k' -> List.rev ((k',kacc)::l) 
    | _  -> List.rev l 
;; 
- : (string * int list) list = [("a", [4; 0]); ("b", [5; 3; 1]); ("c", [2])] 

Answer 3

の作成はCoreライブラリと連想リストを使用して実施例です。

オープンCore.Std

let compute str = 
    let letters = String.split str ~on:' ' in 
    let i = ref (-1) in 
    List.fold letters ~init:[] ~f:(fun acc letter -> 
     incr i; 
     match List.Assoc.find acc letter with 
     | Some l -> List.Assoc.add acc letter (List.append l [!i]) 
     | None -> List.Assoc.add acc letter [!i] 
    ) 

にここでは一例です：

compute "a b c b a b";; 

- : (string, int list) List.Assoc.t = 
[("b", [1; 3; 5]); ("a", [0; 4]); ("c", [2])] 

ここのトリックは、分割文字列を反復し、連想リストを更新するためにList.foldを使用することです。

Answer 4

標準ライブラリ関数List.fold_leftは、reduceがLisp言語とコアで提供する機能をカバーしています。ハッシュテーブルまたはマップを使用して、結果を段階的に構築することができます。 Listモジュールの基本的な関連付けリストを使用することもできますが、O（n^2）のパフォーマンスが最悪の場合があります。したがって

：

module StringMap = Map.Make(String) 

(* Extract words from a string. *) 
let words = Str.split (Str.regexp "[ \t]+") 

(* Build a string to int list dictionary from a string of words. *) 
let dict ws = 
    let open StringMap in 
    let dict' = 
    (* Go through each word in turn; 'i' is a counter that is being 
    * incremented, 'mapping' accumulates the results. *) 
    List.fold_left (fun (mapping, i) word -> 
     try 
     let positions = find word mapping in 
     (* Add to existing entry *) 
     (add word (i :: positions) mapping, i+1) 
     with 
     (* New entry *) 
     Not_found -> (add word [i] mapping, i+1)) 
     (empty, 0) in 
    let (mapping, _) = dict' (words ws) in 
    (* Entries are in reverse order, sort them out, then return as list. *) 
    (* The bindings themselves are already sorted. *) 
    bindings (map List.rev mapping) 

let example = dict "a b c b a b" 

これはソート順にキーおよび位置を提供します。注文が問題でない場合は、dictの最後の行をbindings mappingに簡略化することができます。これはocamlc str.cma dict.ml：例えば、単語のリストに文字列を解析し、従ってstr.cmaは（ネイティブコードのコンパイルの場合）またはstr.cmxa（バイトコードのコンパイルのために）コンパイラに渡す必要があるためにStrモジュールを必要とすること

注意。 ocamlbuildを使用している場合は、-package strでビルドしてください。