为什么Map.make.fold更像List.fold_right (它是非尾递归的)？

Question

Ocaml's fold上的天真问题:注意这个列表，你能解释一下为什么Map.make.fold更像List.fold_right而不是List.fold_left吗？fold_right不是tail_recursive吗？应该有Map.make.fold_left和Map.make.fold_right吧？

type of Map.make.fold 
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

type of List.fold_left    
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

type of List.fold_right
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

Answer 1

如果您查看Map的fold所做的documentation：(f kN dN ... (f k1 d1 a)...)，您将看到它实际上执行了左折叠(其中left是最小的键，而right是最大的键)。

对于Map或Set，这是一个二进制搜索树，它很容易在两个方向上遍历它，而不像(单链接列表)只能在一个方向上遍历；因此在两个方向上进行尾递归折叠也同样容易。

至于参数的顺序，我想这只是一个设计决定。Haskell的列表折叠(foldl和foldr)以及Haskell's Map's fold始终在列表参数之前使用初始值参数。我认为一致性很好。OCaml从不同方向进行的列表折叠具有不同的参数顺序(我猜这可能是因为对于左侧折叠，您将初始参数放在左侧，并将其逐渐“折叠”到列表上的右侧；而对于右侧折叠，您将初始元素放在右侧，并逐渐将其折叠到列表左侧；因此，参数的位置在视觉上与操作一致。)显然，OCaml's Map的fold的参数顺序与它的right fold相同。我不认为这真的很重要。

至于有两个地图折叠，可能会有一些价值。Haskell's Map在GHC 6.12中引入了折叠的两个方向。以前，只有一个右折叠。然而，在Map上使用fold的大多数可能并不关心顺序。

Answer 2

你的问题暗示了函数中参数的顺序与它是否是尾递归有关，但事实并非如此。List.fold_right可以拥有与List.fold_right相同的签名，但这不会改变它的实现。