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

[Brian H. <bri...@ql...>]

On Tue, 10 Jun 2003, Nicolas Cannasse wrote:

> > > 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 ?

"Classic" might have been a better word than Standard.

Basically,

type 'a tree_t = Void | Node of 'a tree_t * 'a * 'a tree_t
(* or whatever *)

val add : 'a tree_t -> 'a -> 'a tree_t

etc.

> 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 ?

I'd say no.  We should provide the "natural" or "usefull" version.  
Defining what I mean by natural or usefull gets tricky.

The only reason I can see for stacks to be mutable in the standard library
is because the applicative version is *so* trivial to implement.  I mean:

type 'a stack = 'a list

let push s e = e :: s

let top s = List.hd s

let pop s = List.tl s

Maps are applicative, and are based upon applicative trees.  Same with
sets- also based on applicative trees.  Hashtables I could see being
mutable because they are conceptually based upon arrays- which are also
mutable.  Strings are mutable, and buffers are as well as they're
conceptually based upon strings (which are conceptually based upon arrays
of chars).  Personally, I'd have preferred nonmutable strings, but neither
here nor there.  Queues are mutable because I don't know of any sane way
to implement them applicatively.

> 
> 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.

There is explicitly using applicative features, and implicitly using it.  
Consider:

let foo lst =
    (* pick out just those items I want *)
    let mylst = List.filter f3 lst in 
    (* a bunch of code that uses mylst and not lst *)

Now here, from the function's perspective, lst might as well go away after 
the call to filter.  But the code calling this function might be depending 
upon lst to not be modified by foo.  So I think the applicative/functional 
aspect of Ocaml is used a lot more often than it might look it.

All of which has nothing to do with wether the tree library should be
applicative or mutable.  If the library is created mutable, then in using
it you may have side-effects.  Just like several other libraries/data
structures.

Brian