fold_tree в OCaml

Question

Как вы знаете, есть высшие функции порядка в OCaml, такие как fold_left, fold_right, фильтр и т.п.

На моем курсе в функциональном программировании была введена функция с именем 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 работы? Не могли бы вы привести несколько примеров и объяснить человеческий язык?

Answer 1

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

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 возвращается a. Для любого Node он объединяет сохраненное значение и результат складывания левого и правого поддеревьев. В этом случае мы просто добавляем числа, в которых каждый лист считается одним. Результатом складывания этого дерева является 10.

Answer 2

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

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

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 

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

Answer 3

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

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

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

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 является очень общей трансформацией (технический термин morphism).

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

Answer 4

Давайте возьмем пример дерева.

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 это функция, которая строит что-то из левого того, элемента и правого того, так же, как 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 эквивалентен обратному + fold_right + обратный, хотя он более четкий и более эффективный).

Ваш собственный 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 

Answer 5

Вы можете наслаждаться чтением

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

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

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