在 OCaml 的 List 模块中,val assoc : 'a -> ('a * 'b) list -> 'b
是如何实现的,(因此)它的复杂度是多少手术 ?幕后是否隐藏了 hashtbl?
最佳答案
可在此处在线获取代码:https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml#L180-L182
let rec assoc x = function
[] -> raise Not_found
| (a,b)::l -> if compare a x = 0 then b else assoc x l
如您所见,它是作为对列表的线性搜索实现的。
关于List.assoc 的 OCaml 复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48171560/