OCaml Tree Tutorial

Question

Hello,

I'm searching for an good OCaml Tree tutorial...

...I need a few examples of how to remove elements, add elements, remove subtrees...

Br, Wolfy

Answer 1

Read the implementations of Set and Map in the standard library: ocaml-3.12.0/stdlib/set.ml and ocaml-3.12.0/stdlib/map.ml

For set.ml, for instance, skip until:

type elt = Ord.t

This will be the type of elements.

type t = Empty | Node of t * elt * t * int

This is the type of balanced binary trees representing sets. in Node(l,e,r,h), e is the element carried by the current node. l is the left subtree, r is the right subtree, and h is the height of the tree, stored on each node so that it doesn't need to be computed expensively each time.

(* Sets are represented by balanced binary trees (the heights of the
   children differ by at most 2 *)

let height = function
    Empty -> 0
  | Node(_, _, _, h) -> h

Answer 2

Okasaki "Purely Functional Data Structures". It is in SML, but the code is easy to understand/translate.