这是我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";
我猜这已经被发明了很多次了。这种技术有什么名字吗?任何著名的规范形式?有什么想法可以使它变得更好吗?
更为规范的是定义惰性数据结构。可能是这样的:
type 'a tree = unit -> 'a tr
and 'a tr = Stem of 'a * 'a tree list
或者,您可以尝试OCaml的惰性值。
IMO试图懒惰地遍历非懒惰的数据结构不是很规范。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句