fold_tree в OCaml

Как Вы, возможно, знаете, в OCaml есть функции более высокого порядка, такие как fold_left, fold_right, filter и т.д.

На моем Конечно, в функциональное программирование была введена функция с именем fold_tree, что-то вроде fold_left / right, но не для списков, а для (бинарных) деревьев. Это выглядит так:

 let rec fold_tree f a t = 
  match t with
    Leaf -> a |
    Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

Где дерево определено как:

type 'a tree = 
  Node of 'a tree * 'a * 'a tree | 
  Leaf;;

ОК, вот мой вопрос: как работает функция fold_tree? Не могли бы вы привести мне несколько примеров и объяснить их на человеческом языке?

8
задан equrts 15 November 2010 в 22:32
поделиться