CODEWITHSUNDEEP
moduleocamltree
Nick Heiner
Nick Heiner

Reputation: 122432

OCaml: Tree functions

Are there any modules or functions for dealing with trees? I have a type that looks like this:

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

I'm struggling to do insertion, removal of subtrees, etc.

I've used Google but can't find anything.

Upvotes: 4

Views: 7832

Answers (2)

LB40
LB40

Reputation: 12331

In the past, I've used ocamlgraph. This is not a trivial lib to use, but if you need to insert nodes and change path, that could the trick, I've never used that in a b-tree context though...

And extracted from the language documentation:

The most common usage of variant types is to describe recursive data structures. Consider for example the type of binary trees:

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

This definition reads as follow: a binary tree containing values of type 'a (an arbitrary type) is either empty, or is a node containing one value of type 'a and two subtrees containing also values of type 'a, that is, two 'a btree.

Operations on binary trees are naturally expressed as recursive functions following the same structure as the type definition itself. For instance, here are functions performing lookup and insertion in ordered binary trees (elements increase from left to right):

#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

Upvotes: 3

Pascal Cuoq
Pascal Cuoq

Reputation: 80276

Read the implementation of module Set in the sources of the OCaml standard library. They are implemented with binary trees, only a little more sophisticated than yours.

(I would recommend you start with binary trees instead of having a list of children as you seem to have defined)

Upvotes: 3

Related Questions