OCaml: Funkcje drzewa

Question

Czy są jakieś moduły lub funkcje do obsługi drzew? Mam typ, który wygląda tak:

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

i jestem stara się zrobić wstawianie, usuwanie poddrzew itd

Użyłem gogli, ale nie mogę znaleźć nic.

Answer 1

Przeczytaj implementację modułu Ustaw w źródłach standardowej biblioteki OCaml. Są one zaimplementowane z drzewami binarnymi, tylko trochę bardziej wyszukanymi niż twoje.

(polecam zacząć drzewo binarne zamiast listę dzieci, jak wydaje się, że zdefiniowane)

Answer 2

Właściwie to zależy od sposobu chcesz drzewo do pracy, na przykład, jeśli istnieje porządek między elementami i takimi.

W przeciwnym razie można użyć znanych algorytmów na drzewach, jeśli masz pomysł jak to zrobić w innych językach C lub Java na przykład, mogę pomóc przetłumaczyć je na OCAML.

Answer 3

W przeszłości używałem ocamlgraph. To nie jest trywialne lib w użyciu, ale jeśli trzeba wstawić węzły i zmienić ścieżkę, które mogłyby trick, nigdy nie używany, że w kontekście b drzewa mimo ...

i wyodrębnionego z dokumentacja język:

Najczęstsze wykorzystanie typów wariantowych jest opisanie dane rekurencyjnych struktur. Rozważmy na przykład rodzaj drzew binarnych:

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

Ta definicja brzmi następująco: a drzewo binarne zawierające wartości typu „a (dowolny rodzaj) jest albo pusta lub jest węzeł zawierający jedną wartość typu "ai dwóch poddrzew zawierający również wartości typu" a, , czyli dwa "a btree.

Operacje na drzewach binarnych to naturalnie wyrażone jako funkcje rekursywne o tej samej strukturze, co jako sama definicja typu. Dla przykład, oto funkcje wykonujące wyszukiwanie i wstawianie w zamówionych drzewo binarne (elementy wzrost od lewej do prawej):

#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> 

Hope this helps

Answer 4

Jest Ptree typ danych przez Matt McDonnell, który robi to, co potrzebujesz, tak myślę.