ocaml - 在 OCaml 中手动减少列表

Question

我正在编写一个创建关联列表的简单 OCaml 函数。输入是一个字符串，它被转换为一个非唯一单词列表，其顺序与字符串中的顺序相同，然后输出是一个关联列表(单词，[列表中的索引])。

例子

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 对每个单独的绑定(bind)进行操作，例如，它迭代 ("a", 4) 和 ("a", 0) 分开(我的理解)这违背了目的。有什么建议吗？

Answer 1

我不明白你对哈希表的描述。哈希表的类型是 (string, int) Hashtbl.t 还是 (string, int list) Hashtbl.t？如果是后者，您可以只使用 Hashtbl.iter 或(可能更好)Hashtbl.fold。

如果您的哈希表是 (string, int) Hashtbl.t 类型，您或许可以重写您的代码以保留一个整数列表而不是单个整数。然后它将是 (string, int list) Hashtbl.t 类型。

更新

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

文档描述了以下现象:

# 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 更新您的条目，您就可以了。