fold_tree в OCaml

Вот совет по стилю: поставьте полоски в начале строки. Это проясняет, где начинается дело. Для единообразия первая полоска не обязательна, но рекомендуется.

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

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

Что касается того, как это работает, рассмотрим следующее дерево:

let t = Node(Leaf, 5, Node(Leaf, 2, Leaf));;

С типом int tree.

Визуально t выглядит так:

   5
  / \
 ()  2
    / \
   () ()

И вызывая fold_tree, нам понадобится функция для объединения значений. Основываясь на использовании в случае Node, f принимает 3 аргумента, все того же типа, что и дерево, и возвращает то же самое. Мы сделаем это:

let f x l r = x + l + r;; (* add all together *)
fold_tree f 1 t;;

Это помогло бы понять, что происходит в каждом конкретном случае. Для любого Leaf возвращается. Для любого Node он объединяет сохраненное значение и результат сворачивания левого и правого поддеревьев. В этом случае мы просто складываем числа, в которых каждый лист считается за единицу. Результат сворачивания этого дерева 10.

Возьмем пример дерева.

let t = Node (Node (Leaf, 10, Leaf), 1, Node (Node (Leaf, 20, Leaf), 11, Leaf))

Общее определение операции fold заключается в том, что вы заменяете конструкторы функциями, везде в дереве.

general_fold_tree node leaf t =
    node (node leaf 10 leaf) 1 (node (node leaf 20 leaf) 11 leaf)

node - это функция, которая конструирует something из левого something, элемента и правого something, точно так же, как Node - конструктор, который конструирует дерево из левого поддерева, содержимого узла и правого поддерева. leaf - константа, соответствующая конструктору константы Leaf.

let rec general_fold_tree (node : 'b -> 'a -> 'b -> 'b) (leaf : 'a) (t : 'a tree) : 'b =
  let recurse t = general_fold_tree node leaf t in
  match t with
  | Node (l, x, r) -> node (recurse l) x (recurse r)
  | Leaf -> leaf

Обратите внимание, что типы функций соответствуют типам определения типа, за исключением того, что там, где определение типа описывает построение 'a tree, функция сгиба описывает построение любого 'b.

Операции, которые очень похожи на обычную свертку, по-прежнему называются сверткой. Например, в списках List.fold_right - это общая складка в соответствии с приведенным выше определением; List.fold_left - это вариант, который применяет функцию наоборот (fold_left эквивалентно reverse + fold_right + reverse, хотя он более понятен и эффективен).

Ваш собственный fold_tree - это простой вариант этой общей свертки, где функция узла принимает свои аргументы в порядке, отличном от порядка конструктора:

let equrts_fold_tree f a t =
  let node l x r = f x l r in
  general_fold_tree node a t

Вот способ подумать о fold_right в списках: например, список

(1 :: (2 :: (3 :: [])))

и вы повторно интерпретируете список с новой бинарной операцией вместо :: (и новой константой вместо []).

fold_right (+) l 0 = (1 + (2 + (3 + 0)))

Если вы не хотите ничего делать со своим списком, вы можете передать функцию cons в качестве функции и пустой список в качестве нейтрального элемента. В некотором смысле fold_right носит очень общий характер: он даже позволяет вам вообще не терять никакой информации.

fold_tree в вашем вопросе - это та же идея для типа данных деревьев. Если вы хотите повторно интерпретировать свое дерево, вы передаете ему новую функцию для узлов, которая будет применяться вместо конструктора Node. Если вы хотите получить идентичное дерево, вы можете применить его с Leaf как нейтральным и (fun x l r -> Node (l, x, r)) как функцией. Подобно fold_left для списков, этот пример приложения не очень интересен, но он означает, что fold_left является очень общим преобразованием (технический термин - морфизм).

Вы также можете суммировать элементы дерева, например, с помощью функции (fun x l r -> x + l + r).

Вам может понравиться читать

http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/

http://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/

которые находятся в F #, но F # очень похож на OCaml.

Кажется, что f - это трехпараметрическая функция сокращения, a - нейтральный элемент нашего сокращения, а t - корень, поэтому:

учитывая двоичный пример (я не очень хорошо помню синтаксис вариантных типов, поэтому, пожалуйста, будьте снисходительны здесь)

let r = Node(Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf)),1,Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf)))

если вы хотите просуммировать все узлы, функция будет вызываться так:

let add x y z = x + y + z
fold_tree add 0 r

и мы получим t, совпадающий с узлом, так что у нас есть:

(add 1 (fold_tree add 0 Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf))) (fold_tree add 0 Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf))))

если мы его еще немного расширим, то получим:

(add 1 (add 2 (fold_tree add 0 Node(Leaf,3,Leaf)) (fold_tree add 0 Node(Leaf,4,Leaf))) (add 5 (fold_tree add 0 Node(Leaf,6,Leaf)) (fold_tree add 0 Node(Leaf,7,Leaf))))

и еще раз сопоставляем листья:

(add 1 (add 2 (add 3 0 0) (add 4 0 0)) (add 5 (add 6 0 0) (add 7 0 0))
(add 1 (add 2 3 4) (add 5 6 7))
(add 1 9 18)

чтобы наконец получить:

28

Надеюсь, поможет.