在OCaml中手动缩减列表

Question

我正在编写一个简单的OCaml函数来创建关联列表。输入是一个字符串，它以与字符串相同的顺序转换为非唯一字列表，然后输出为（word，[indices in list]）的关联列表。

例

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会更有效，因为单词的数量增长。编辑：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。

如果你的散列表的类型是(string, int) Hashtbl.t你也许可以重写你的代码来保存一个int列表而不是单个int。然后它将是类型(string, int list) Hashtbl.t。

更新

如果你的哈希表是(string, int list) Hashtbl.t类型，那么你可以只使用iter或fold如果你要确保你有每个键只有一个条目。

该文件描述了如下现象：

# 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.add新条目添加到哈希表而不删除旧的条目积累。

如果您使用Hashtbl.replace而不是Hashtbl.add，事情会更合理。

# 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 =() 

如果你有合适类型的哈希表，并使用Hashtbl.replace更新您的项目，你会好起来的。

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语言和Core中提供的功能。您可以使用散列表或地图来逐步构建结果。虽然您也可以使用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。

请注意，这需要Str模块将字符串解析成一个单词列表，从而str.cma（对字节码编译）或str.cmxa（本地代码编译）需要被传递到编译器，例如：ocamlc str.cma dict.ml。如果您使用ocamlbuild，请使用-package str构建。