反转 Module.Map

Question

我看了一下Module.Map，不知道有没有定义反向映射的函数

val rev : 'a t -> 'a t

我尝试构建一个

val fold_left_map:(key -> 'a -> 'b -> 'a) -> 'a -> 'b map -> 'a

let rec fold_left_map f value map =
    match map with
    | Empty_map -> value
    | Node_map (left, key, data, right, _) ->
       fold_left_map f (f key (fold_left_map f value right) data) left

当我尝试使用此功能构建时卡住了 rev。

let rev map = fold_left_map (function key a x -> ...)

Answer 1

我不确定你在哪里找到的 Module.Map，也许它是你作业的一部分？所以，我假设你在谈论 OCaml 标准模块 Map.

一般信息

OCaml 中的映射是使用平衡二叉树实现的。树本身没有秩序，因为根据定义，它们的结构不是线性的。虽然，它们可以按指定的顺序遍历。但是可以根据键比较功能指定排序。这不能是任意排序。

你的例子

综上所述，你应该已经知道，树的倒转是不可能的。您只能以相反的方向遍历它。这意味着，如果你想按升序访问所有节点，你需要先访问左边的节点，如果你想按降序遍历，你的迭代函数应该先访问右边的节点。