umklappen Bäume in OCaml

Question

Das ist mein Versuch ist fold die Umsetzung (links) für den Baum (es ist sehr vereinfachte Version, sondern reproduziert sorgfältig echte Baumstruktur):

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) 

Die Idee ist, latenten Aufruf zu verwenden, für Teilbäume. Es lässt uns:

• einen Teilbaum überspringen, wenn nötig durchlaufen
• einen Teilbaum Verfahrgeschwindigkeit initialisieren und komponieren Ergebnisse

Ein Spielzeug Beispiel:

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"; 

Ich denke, das viele Male erfunden wurde bereits. Gibt es einen Namen für diese Technik? Jede bekannte kanonische Form? Irgendwelche Ideen, wie man es besser macht?

Answer 1

Eine kanonische wird sein, eine faule Datenstruktur zu definieren. Möglicherweise wie folgt:

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

Oder Sie können OCaml's faule Werte versuchen.

Der Versuch, träge eine nicht-faule Datenstruktur zu durchlaufen, ist nicht sehr kanonisch, IMO.