摺疊樹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的懶惰值。

試圖懶洋洋地遍歷一個非懶惰的數據結構是不是很正典，國際海事組織。