From: Nicolas C. <war...@fr...> - 2003-06-06 07:06:03
Attachments:
binTree.ml
binTree.mli
|
Hi list, 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. Nicolas Cannasse |
From: Nicolas C. <war...@fr...> - 2003-06-06 09:30:01
|
> Tree node here takes 3 (for Tree+tuple, and two refs) allocations where > it can take 2 (or 1?) with: > > | Tree of ('a, 'b) tree_rec > > and type ('a, 'b) tree_rec = > { > a : 'a; > b : 'b; > mutable left : ('a, 'b) tree; > mutable right : ('a, 'b) tree; > } > > and this is more readable IMHO. True, thanks. That piece of code is pretty old, I just added the enum features without thinking about the internal representation. I'll update it this way when I have some time. Nicolas Cannasse |
From: Amit D. <adubey@CoLi.Uni-SB.DE> - 2003-06-06 09:35:20
|
Just a quick question, is there any advantage of > type ('a,'b) t = { > cmp : ('a -> 'a -> int); > t : ('a ,'b) tree ref; > } over: type ('a,'b) t = { cmp : ('a -> 'a -> int); mutable t : ('a, 'b) tree; } Doesn't the first version require a little bit more memory? I don't think it's a big deal, but... Also, what are the relative advantages of having this vs. putting a mutable wrapper around Map? Map, if I'm not mistaken, makes some guarantees of the trees being balanced (both add and remove in Map call the balancing function). -Amit > > This is a multi-part message in MIME format. > > ------=_NextPart_000_0015_01C32C45.52938130 > Content-Type: text/plain; > charset="iso-8859-1" > Content-Transfer-Encoding: 7bit > > Hi list, > > 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. > > Nicolas Cannasse > > ------=_NextPart_000_0015_01C32C45.52938130 > Content-Type: application/octet-stream; > name="binTree.ml" > Content-Transfer-Encoding: 7bit > Content-Disposition: attachment; > filename="binTree.ml" > > > type ('a,'b) tree = > | Empty > | Tree of ('a * 'b * ('a,'b) tree ref * ('a,'b) tree ref) > > type ('a,'b) t = { > cmp : ('a -> 'a -> int); > t : ('a ,'b) tree ref; > } > > let empty() = > { > cmp = compare; > t = ref Empty; > } > > let make cmp = > { > cmp = cmp; > t = ref Empty; > } > > let rec add t key item = > let rec loop r = > match !r with > | Empty -> r := Tree(key,item,ref Empty,ref Empty) > | Tree(k,i,tl,tr) -> > let n = t.cmp k key in > if n = 0 then r := Tree(key,item,tl,ref (Tree(k,i,ref Empty,tr))) > else if n > 0 then loop tl > else loop tr > in > loop t.t > > let rec length t = > let rec loop r = > match !r with > | Empty -> 0 > | Tree(_,_,tl,tr) -> 1+(loop tl)+(loop tr) > in > loop t.t > > let rec depth t = > let rec loop r = > match !r with > | Empty -> 0 > | Tree(_,_,tl,tr) -> 1+(max (loop tl) (loop tr)) > in > loop t.t > > let rec find t key = > let rec loop r = > match !r with > | Empty -> raise Not_found > | Tree(k,i,tl,tr) -> > let n = t.cmp k key in > if n = 0 then i > else if n > 0 then loop tl > else loop tr > in > loop t.t > > let iter f t = > let rec loop r = > match !r with > | Empty -> () > | Tree(k,i,tl,tr) -> > loop tl; > f k i; > loop tr > in > loop t.t > > let copy t = > let rec loop r = > match !r with > | Empty -> ref Empty > | Tree (k,i,tl,tr) -> > ref (Tree(k,i,loop tl,loop tr)) > in > { > cmp = t.cmp; > t = loop t.t; > } > > let clear t = t.t := Empty > > let rec remove t key = > let p = ref Empty in > let rec remove_aux r = > match !r with > | Empty -> raise Not_found > | Tree(k,i,tleft,tright) -> > let n = t.cmp k key in > if n = 0 then r else begin > p := !r; > if n > 0 then remove_aux tleft else remove_aux tright > end > in > let found = remove_aux t.t in > match !found with > | Empty -> assert false > | Tree(k,i,fleft,fright) -> > let attach subtree = > match !p with > | Empty -> t.t := subtree > | Tree(_,_,pleft,pright) -> > if found == pleft then > pleft := subtree > else > pright := subtree > in > if !fright = Empty then attach !fleft > else begin > let lp = ref Empty in > let rec mostleft_aux t = > match !t with > | Empty -> assert false > | Tree(_,_,left,_) -> > if !left = Empty then t else begin > lp := !t; > mostleft_aux left; > end > in > let mostleft = mostleft_aux fright in > let mkey,mitem,mleft,mright = > (match !mostleft with > | Empty -> assert false > | Tree infos -> infos) in > match !lp with > | Empty -> > attach (Tree(mkey,mitem,fleft,mright)) > | Tree(_,_,lpleft,lpright) -> > attach (Tree(mkey,mitem,fleft,fright)); > lpleft := !mright; > end > > type ('a,'b) istack = > | SItem of ('a * 'b) > | STree of ('a , 'b) tree ref > > let rec make_enum f s = > let rec next () = > match !s with > | [] -> raise Enum.No_more_elements > | (SItem x) :: h -> > s := h; > f x > | (STree t) :: h -> > let rec loop t = > match !t with > | Empty -> > s := h; > next() > | Tree (k,i,left,right) -> > s := (SItem (k,i)) :: (STree right) :: !s; > loop left > in > loop t > in > let rec tcount t = > match !t with > | Empty -> 0 > | Tree(_,_,tl,tr) -> 1 + tcount tl + tcount tr > in > let count() = > List.fold_left (fun acc c -> > match c with > | SItem _ -> acc + 1 > | STree t -> acc + tcount t > ) 0 !s > in > let clone() = > make_enum f (ref !s) > in > Enum.make ~next ~count ~clone > > let pairs t = > make_enum (fun x -> x) (ref [STree t.t]) > > let enum t = > make_enum snd (ref [STree t.t]) > > let keys t = > make_enum fst (ref [STree t.t]) > > let optimize t = assert false > > let to_list t = > let rec loop dst r = > match !r with > | Empty -> dst > | Tree(k,i,tl,tr) -> > let dst = loop dst tl in > let r = [ (k,i) ] in > Obj.set_field (Obj.repr dst) 1 (Obj.repr r); > loop r tr > in > let x = [Obj.magic()] in > ignore(loop x t.t); > List.tl x > > let optimize t = > let l = ref (to_list t) in > let len = List.length !l in > let rec opt_list len = > if len = 0 then > Empty > else if len = 1 then begin > match !l with > | [] -> assert false > | (k,i) :: q -> > l := q; > Tree(k,i,ref Empty,ref Empty) > end else begin > let left = opt_list (len/2) in > let k, i = (match !l with > | [] -> assert false > | x :: q -> > l := q; > x) in > let right = opt_list ((len-1)/2) in > Tree(k,i,ref left,ref right) > end > in > t.t := opt_list len > ------=_NextPart_000_0015_01C32C45.52938130 > Content-Type: application/octet-stream; > name="binTree.mli" > Content-Transfer-Encoding: 7bit > Content-Disposition: attachment; > filename="binTree.mli" > > > type ('a,'b) t > > val empty : unit -> ('a,'b) t > val make : ('a -> 'a -> int) -> ('a,'b) t > > (* O(N) *) > val length : ('a,'b) t -> int > val depth : ('a,'b) t -> int > val copy : ('a,'b) t -> ('a,'b) t > val optimize : ('a,'b) t -> unit > > (* log N *) > val add : ('a,'b) t -> 'a -> 'b -> unit > val find : ('a,'b) t -> 'a -> 'b (* raise Not_found *) > val remove : ('a,'b) t -> 'a -> unit (* raise Not_found *) > > val enum : ('a,'b) t -> 'b Enum.t > val keys : ('a,'b) t -> 'a Enum.t > val pairs : ('a,'b) t -> ('a * 'b) Enum.t > val to_list : ('a,'b) t -> ('a * 'b) list > > val iter : ('a -> 'b -> unit) -> ('a,'b) t -> unit > > val clear : ('a,'b) t -> unit > ------=_NextPart_000_0015_01C32C45.52938130-- > > > > ------------------------------------------------------- > This SF.net email is sponsored by: Etnus, makers of TotalView, The best > thread debugger on the planet. Designed with thread debugging features > you've never dreamed of, try TotalView 6 free at www.etnus.com. > _______________________________________________ > ocaml-lib-devel mailing list > oca...@li... > https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel > |
From: Nicolas C. <war...@fr...> - 2003-06-06 10:26:10
|
> is there any advantage of > > > type ('a,'b) t = { > > cmp : ('a -> 'a -> int); > > t : ('a ,'b) tree ref; > > } > > over: > > type ('a,'b) t = { > cmp : ('a -> 'a -> int); > mutable t : ('a, 'b) tree; > } > > Doesn't the first version require a little bit more memory? > I don't think it's a big deal, but... It's for recursion, since are left and right trees are both ('a , 'b ) tree ref. The problem is that you cannot pass a mutable field to a function like a ref. > Also, what are the relative advantages of having this vs. > putting a mutable wrapper around Map? Map, if I'm not mistaken, > makes some guarantees of the trees being balanced (both add > and remove in Map call the balancing function). Map does not allow to have several items with the same key in it. Calling add is replacing the current binded item if any. I think it's more convenient to have a structure that can "shadow" items just like Hashtbl do. Nicolas Cannasse |
From: Amit D. <adubey@CoLi.Uni-SB.DE> - 2003-06-06 11:22:46
|
> > is there any advantage of > > > > > t : ('a ,'b) tree ref; > > over: > > > > mutable t : ('a, 'b) tree; > It's for recursion, since are left and right trees are both ('a , 'b ) tree > ref. The problem is that you cannot pass a mutable field to a function > like a ref. I'm a bit confused... unless you want to make a change to a subtree from two places, this shouldn't be necessary. Taking a quick peek at the code, it doesn't seem like this happens (but maybe I missed something). If this isn't the case, you could just as easily pass around the unmutable structure, and assign it where you need. > > > Also, what are the relative advantages of having this vs. > > putting a mutable wrapper around Map? Map, if I'm not mistaken, > > makes some guarantees of the trees being balanced (both add > > and remove in Map call the balancing function). > > Map does not allow to have several items with the same key in it. > Calling add is replacing the current binded item if any. > I think it's more convenient to have a structure that can "shadow" items > just like Hashtbl do. Ok, makes sense! However, the main thrust behind my suggestion was more about the worst-case performance of insertion and removal... Map already has the balancing code written, even if a wrapper isn't appropriate, perhaps you could steal'n'hack the bal, add and remove functions from there? -Amit |
From: Nicolas C. <war...@fr...> - 2003-06-06 10:27:06
|
> is there any advantage of > > > type ('a,'b) t = { > > cmp : ('a -> 'a -> int); > > t : ('a ,'b) tree ref; > > } > > over: > > type ('a,'b) t = { > cmp : ('a -> 'a -> int); > mutable t : ('a, 'b) tree; > } > > Doesn't the first version require a little bit more memory? > I don't think it's a big deal, but... It's for recursion, since are left and right trees are both ('a , 'b ) tree ref. The problem is that you cannot pass a mutable field to a function like a ref. > Also, what are the relative advantages of having this vs. > putting a mutable wrapper around Map? Map, if I'm not mistaken, > makes some guarantees of the trees being balanced (both add > and remove in Map call the balancing function). Map does not allow to have several items with the same key in it. Calling add is replacing the current binded item if any. I think it's more convenient to have a structure that can "shadow" items just like Hashtbl do. Nicolas Cannasse |
From: Brian H. <bh...@sp...> - 2003-06-06 18:12:43
|
On Fri, 6 Jun 2003, Nicolas Cannasse wrote: > Hi list, > > 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? Brian |
From: Nicolas C. <war...@fr...> - 2003-06-10 08:14:04
|
> > 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 |
From: Brian H. <bri...@ql...> - 2003-06-10 18:50:06
|
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 |