折叠树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"; 

我想这是发明了很多次已经。这种技术有什么名字吗？任何着名的canonic形式？任何想法如何使它变得更好？

Answer 1

更规范的是定义一个懒惰的数据结构。可能是这样的：

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

或者，你可以尝试OCaml的懒惰值。

试图懒洋洋地遍历一个非懒惰的数据结构是不是很正典，国际海事组织。