Ocaml: Tree functions

Question

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

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

I've used the googles but can't find anything.

Answer 1

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)

Answer 2

Actually it depends on the way you want your tree to work, for example if there is order between elements and such.

Otherwise you can use the known algorithms on trees, if you have an idea how to it in other languages C or Java for example, I can help translate it to OCAML.

Answer 3

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