Определение дерева + указатель на его поддерево в ocaml - PullRequest
Новая
       29

Определение дерева + указатель на его поддерево в ocaml

4 голосов
/ 15 февраля 2012

Как определить дерево + указатель на его поддерево в OCaml, чтобы добавление листьев в это поддерево занимало постоянное время?

Ответы [ 2 ]

7 голосов
/ 15 февраля 2012

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

Если вы хотите найти решение, использующее мутацию на месте, вы можете использовать изменяемые данные через mutable поля записи или ссылки (ref), полученные из него. Например: 

type 'a tree_cell = {mutable node : 'a tree}
and 'a tree = Leaf of 'a | Branch of 'a tree_cell * 'a * 'a tree_cell

Если вы держите 'a tree_cell, вы можете изменить его (в постоянном времени). 

let head {node = (Leaf x | Branch(_, x, _))} = x

let duplicate cell =
  cell.node <- Branch (cell, head cell, {node = cell.node})

Редактировать: в комментариях к вашему вопросу вы, похоже, указываете на свою заинтересованность в решении для n-арных деревьев.

Общий n-арный случай можно представить как 

type 'a tree_cell = {mutable node: 'a tree}
and 'a tree = Branch of 'a * 'a tree_cell list

пока решение на молнии будет выглядеть (непроверенный код) 

type 'a tree = Branch of 'a * 'a forest
and 'a forest = 'a tree list

(* the data between the current cursor and the root of the tree *)
type 'a top_context = Top | Under of 'a * 'a tree * 'a top_context

(* a cursor on the 'data' element of a tree *)
type 'a data_cursor = top_context * 'a tree list

(* plug some data in the hole and get a tree back *)
val fill_data : 'a data_cursor -> 'a -> 'a tree

(* a cursor on one of the children of a tree *)
type 'a list_zipper = 'a list * 'a list
type 'a children_cursor = top_context * 'a * 'a tree list_zipper

(* plug some subtree in the hole and get a tree back *)
val fill_children : 'a children_cursor -> 'a tree -> 'a tree

(* carve a data hole at the root; also return what was in the hole *)
val top_data : 'a tree -> 'a data_cursor * 'a

(* fill a data hole and get a cursor for the first children in return
   -- if it exists *)
val move_down : 'a data_cursor -> 'a -> ('a children_cursor * 'a tree) option
(* fill the children hole and carve out the one on the left *)
val move_left : 'a data_cursor -> 'a tree -> ('a data_cursor * 'a tree) option
val move_right : 'a data_cursor -> 'a tree -> ('a data_cursor * 'a tree) option
(* fill the children hole and get a cursor on the data *)
val move_up : 'a children_cursor -> 'a tree -> 'a data_cursor * 'a
4 голосов
/ 15 февраля 2012

Другое (более простое и более общее) решение для двоичного дерева: 

type 'a t = {
  value : 'a;
  mutable left : 'a t option;
  mutable right : 'a t option;
}

С этим типом вы можете независимо устанавливать левое и правое поддерево по мере необходимости.

...