Ocaml の折り方に関する素朴な質問: Map.make.fold が List.fold_left ではなく List.fold_right のように設計されている理由を説明してください。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
Map の折り方のドキュメント:を見ると、実際には左折りを実行していることがわかります (左が最小のキーで、右が最大のキーです)。(f kN dN ... (f k1 d1 a)...)
二分探索木であるマップまたはセットの場合、一方向にしかトラバースできない (単一リンクの) リストとは異なり、両方向にトラバースするのは非常に簡単です。そのため、両方向で末尾再帰的な折り畳みを同様に簡単に行うことができます。
引数の順序については、単なる設計上の決定だと思います。Haskell のリスト フォールド (foldlおよびfoldr) とHaskell の Mapfoldは、一貫してリスト引数の前に初期値引数を持ちます。一貫性は良いと思います。OCaml の異なる方向からのリストの折り畳みは、引数の順序が異なります (おそらく、左の折り畳みでは最初の引数を左側に配置し、プログレッシブな「折り畳み」をリストの右側に配置し、右の折り畳みでは、最初の要素を右側に置き、それを徐々にリストの左側に折りたたむ; したがって、引数の配置はアクションと視覚的に一致します.) どうやら OCaml の Map の折りたたみの引数の順序は、右側の折りたたみと同じです。私はそれが本当に重要だとは思わない。
2 つのマップ フォールドがあることに関しては、それには何らかの価値があるかもしれません。Haskell の Map は、GHC 6.12 で両方向の折り畳みを導入しました。以前は、右の折り目しかありませんでした。ただし、マップでの折り畳みのほとんどの使用では、おそらく順序は気にしません。
あなたの質問は、関数内の引数の順序が末尾再帰であるかどうかに関連していることを意味しますが、それは真実ではありません。List.fold_rightは と同じ署名を持つこともできますが、List.fold_rightその実装は変更されません。