Ocaml - предзаказ дерева / почтовый заказ / заказ

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

но ocaml считает 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>