2009-09-25 40 views
5

¿Hay algún módulo o función para trabajar con árboles? Tengo un tipo que se parece a esto:OCaml: Funciones de árbol

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

y estoy luchando para hacer la inserción, eliminación de sub-estructuras, etc.

He utilizado las gafas, pero no puedo encontrar nada.

Respuesta

3

Lea la implementación del módulo Establezca en las fuentes de la biblioteca estándar OCaml. Se implementan con árboles binarios, solo un poco más sofisticados que los tuyos.

(recomiendo que comience con árboles binarios en lugar de tener una lista de los niños como usted parece haber definido)

+0

Sí, pero estoy usando estos árboles para hacer sintaxis de oraciones, así que no puedo simplemente arrojar valores allí. necesitan mantener el orden, y yo esperaba establecer este orden simplemente creando el árbol correctamente, aunque supongo que podría usar un tipo de envoltorio con un número y la palabra misma ... –

+1

Usted * puede * establecer el orden por creando el árbol apropiadamente En realidad, el conjunto de módulos mantiene los elementos del árbol en orden (el elemento más bajo en el descendiente más a la izquierda), así que todavía creo que es una buena fuente de inspiración. –

0

En realidad depende de la forma en que quiere que su árbol de trabajar, por ejemplo si hay orden entre elementos y tal.

De lo contrario, puede utilizar los algoritmos conocidos en los árboles, si tiene una idea de cómo hacerlo en otros lenguajes C o Java, por ejemplo, puedo ayudar a traducirlo a OCAML.

3

En el pasado, he usado ocamlgraph. Esto no es una libra trivial para usar, pero si necesita insertar nodos y cambiar la ruta, ese podría ser el truco, nunca lo he usado en un contexto de árbol b ...

Y extraído del documentación idioma:

El uso más común de los tipos de variantes es describir los datos recursivas estructuras. Consideremos por ejemplo el tipo de árboles binarios:

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

Esta definición se lee como sigue: un árbol binario que contiene valores de tipo 'un (un tipo arbitrario) es o bien vacío, o es un nodo que contiene un valor de de tipo 'a y dos subárboles que también contiene valores de tipo' a, es decir, dos 'a btree.

Operaciones en los árboles binarios se expresan naturalmente como recursivas funciones siguientes la misma estructura como la definición de tipo en sí. Para ejemplo, aquí son funciones realizar la búsqueda e inserción en árboles binarios ordenados (elementos aumento de izquierda a derecha):

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

espero que esto ayude

+0

¿Hay que definir el nodo en alguna parte? Veo que está utilizando algún tipo de constructor para Insertar nodo, ¿cómo funciona eso y dónde se implementa? ¿O es el nodo (x, izquierda, derecha) coincidencia de patrones? Si es así, ¿puedes explicar la sintaxis un poco más? Gracias, tu publicación es muy útil. –

+0

Además de la respuesta de @ LB40 aquí, elimine: http://geck1.blogspot.com/2014/02/ocaml-review-day-4-binary-tree-ops.html – BRS

0

Hay un tipo de datos Ptree por Matt Creo que McDonnell hace lo que necesita.