tree - 在 OCaml 中折叠树

Question

这是我为树实现fold(左)的尝试(它是非常简化的版本，但仔细地再现了真实的树结构):

type 'a tree = Leaf of 'a | Node of 'a * 'a tree list

let rec fold t acc f =
  match t with
  | Leaf x -> f acc x None
  | Node (x, lst) ->
    let deferred acc =
      List.fold_left (fun acc t' -> fold t' acc f) acc lst in
    f acc x (Some deferred)

这个想法是对子树使用延迟调用。它让我们:

• 如果需要则跳过子树遍历
• 初始化子树遍历并组合结果

一个玩具示例:

open Printf

let () =
  let tree = Node (3, [Leaf 5; Leaf 3; Node (11, [Leaf 1; Leaf 2]); Leaf 18]) in

  fold tree "" (fun str x nested ->
      let plus str = if String.length str = 0 then "" else "+" in
      let x = string_of_int x in
      match nested with
      | None -> str ^ (plus str) ^ x
      | Some f -> str ^ (plus str) ^ x ^ "*(" ^ (f "") ^ ")"
    )
  |> printf "%s=";

  fold tree 0 (fun acc x -> function
      | None -> acc + x
      | Some f -> x * (f 0) + acc
    )
  |> printf "%d\n";

我想这已经被发明了很多次了。这项技术有名字吗？有什么众所周知的规范形式吗？有什么想法可以让它变得更好吗？

Answer 1

更规范的方法是定义惰性数据结构。可能是这样的:

type 'a tree = unit -> 'a tr
and 'a tr = Stem of 'a * 'a tree list

或者，您可以尝试 OCaml 的惰性值。

尝试延迟遍历非延迟数据结构并不是很规范，IMO。