Re: [Ocaml-lib-devel] Proposal : BinTree

[Nicolas C. <war...@fr...>]

> > Here's a module proposal for adding to the ExtLib.
> > This is a binary search tree ( module BinTree ).
> > Operations  add, remove, find are done in Log(n) when the tree is
optimized.
> > This is a mutable version of the data structure.
> >
>
> Is there a reason you did this as a mutable tree and not the "standard"
> applicative version?

That's a good question. Actually is there a standard ?
List are of course applicative, Array are of course mutables, but if Sets
are applicative , Hashtables and Stack are mutable...
Should we provide both mutable and applicative version of every data
structure ?

Actually it's good sometimes to have applicative structures, it fits well
with the functional style where you can write :
    let l = List.map f l in
    let l = List.filter f2 l in
    last_call  (List.filter f3 l)

The main advandage here is being able to pass a modified data structure as
argument to another, without actually modifiying it.
But most of the time, the thing you want to really do is :

let l = last_call (List.filter f3 l)

Please note that here I took "filter" as sample function, because map is
always applicative since it can change the type (BTW, we could add in-place
map to MList) , same for fold.

IMHO, there is only few cases when people are actually using the "immutable"
feature of a data structure, and then if you're providing a "copy" operation
(Enum can do it for you :-) you have the same expression power, with shorter
syntax since you don't have to rebind the same variable ever and ever.

Nicolas Cannasse