fold_tree в OCaml

Question

Как вы, возможно, знаете, в 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? Не могли бы вы привести несколько примеров и объяснить на человеческом языке?

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

Answer 2

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

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 3

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

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

Answer 4

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

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

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

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

Answer 5

Кажется, что 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

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