Ocaml - tree preorder/postorder/inorder

Question

我在OCaml中给出了树的定义

type 'a tree = Node of 'a * 'a tree list;;

let rec fold_tree f (Node (x,l)) =
f x (map (fold_tree f) l);;

有没有人可以帮助我，例如，我如何在使用fold_tree (没有额外的递归)的情况下编写预排序。我知道没有fold_tree我也能做到，但这给我带来了麻烦

到目前为止，我得到了这样的结论：

let preorder t =
  fold_tree (fun x l -> 
    (fold_left(fun acc h -> h@acc) x l ) ) t;;

但我会把它当做树形列表。

Answer 1

    OCaml version 4.02.3

# type 'a tree = Node of 'a * 'a tree list;;
type 'a tree = Node of 'a * 'a tree list
# let rec fold_tree f (Node (x,l)) =
  f x (List.map (fold_tree f) l);;
val fold_tree : ('a -> 'b list -> 'b) -> 'a tree -> 'b = <fun>
# let preorder t =
  fold_tree (fun x l -> 
    (List.fold_left(fun acc h -> h@acc) x l ) ) t;;
val preorder : 'a list tree -> 'a list = <fun>

您正在使用x作为List.fold_left的起始值，并向其追加值。这使得x是一个'a list，因此t必须是'a list tree。将x更改为[x]，您将得到：

# let preorder t =
  fold_tree (fun x l -> 
    (List.fold_left(fun acc h -> h@acc) [x] l ) ) t;;
val preorder : 'a tree -> 'a list = <fun>