OCaml: Функции дерева

Question

Существуют ли какие-либо модули или функции для работы с деревьями? У меня есть тип, который выглядит следующим образом:

type t = 
     Leaf of string (* todo: replace with 'a *) 
     | Node of string * t list 

и я изо всех сил, чтобы сделать вставку, удаление поддерева и т.д.

Я использовал Googles, но не может найти что-нибудь.

Answer 1

Прочитать реализацию модуля Установить в источниках стандартной библиотеки OCaml. Они реализованы с бинарными деревьями, только немного более сложными, чем ваши.

(я бы рекомендовал начать с бинарными деревьями вместо того, чтобы иметь список детей, как вы, кажется, определили)

Answer 2

На самом деле это зависит от того, как вы хотите, чтобы ваше дерево работать, например, если есть заказ между элементами и таковыми.

В противном случае вы можете использовать известные алгоритмы для деревьев, если у вас есть идея, как это сделать на других языках C или Java, например, я могу помочь перевести его в OCAML.

Answer 3

В прошлом я использовал ocamlgraph. Это не тривиальная библиотека для использования, но если вам нужно вставлять узлы и менять путь, это может быть трюк, я никогда не использовал это в контексте b-дерева, хотя ...

И извлечен из язык документация:

наиболее распространенное использование типов вариантов является описание рекурсивных ДАННЫХ структуры. Рассмотрим, например, тип бинарных деревьев:

#type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;; 
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree 

Это определение гласит следующим образом: а бинарное дерево, содержащее значения типа «а (произвольный тип) либо пусто, либо является узел, содержащий одно значение типа 'a и два поддерева , содержащее также значения типа' a, , то есть два 'a btree.

Операции на бинарных деревьев , естественно, выражается как рекурсивных функций следующих ту же структуру, как самого определения типа. Для Например, вот функции выполняя поиск и вставку в упорядоченных бинарных деревах (элементы увеличение слева направо):

#let rec member x btree = 
    match btree with 
    Empty -> false 
    | Node(y, left, right) -> 
     if x = y then true else 
     if x < y then member x left else member x right;; 
val member : 'a -> 'a btree -> bool = <fun> 

#let rec insert x btree = 
    match btree with 
    Empty -> Node(x, Empty, Empty) 
    | Node(y, left, right) -> 
     if x <= y then Node(y, insert x left, right) 
       else Node(y, left, insert x right);; 
val insert : 'a -> 'a btree -> 'a btree = <fun> 

Надеется, что это помогает

Answer 4

Существует Ptree типа данных Матового Думаю, Макдоннелл делает то, что вам нужно.