> The deletion operation described in these papers will rebuild a tree. Therefore,
> it does not seem to be comparably efficient with those implementations in
> imperative languages.

Don't forget that there is (almost) no restriction on side-effects in
Caml: if this is crucial for your program, you can implement lists as
an imperative data type of your own, and then use destructive update
to perform the deletion operation in the required complexity. Just be
aware that list sharing will be difficult as for any other imperative
implementation of lists.

Best regards,

-- 
Pierre Weis

INRIA, Projet Cristal, http://pauillac.inria.fr/~weis