[m-dev.] new library module

Fergus Henderson fjh at cs.mu.OZ.AU
Sun Mar 28 18:10:20 AEST 1999


On 26-Mar-1999, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> 
> I have just implemented a 23 tree module.
...
> Anyone want to review it?

I had a brief look.
Some more comments about the implementation would help
(the reference to map.m for the interface documentation is fine),
but apart from that it looked fine to me.
I didn't really try to verify the code's correctness, though.

In particular, some of the explanatory stuff in your mail
about efficiency and the rationale for the module

 | A conversation with Mike Codish reminded me that our top-down 234 tree
 | implementation does not have much use for four-nodes, since they are
 | split on the way down in insertions (to guarantee that the parent has
 | room for a key-value pair to be lifted up into it). He suggested that
 | 23 trees may be more efficient.
 | 
 | I have just implemented a 23 tree module. Most of it is copied from
 | tree234.m, with the code handling four-nodes left out. The insertion
 | code is substantially different, as it allows a subtree to be split,
 | and then handles such splits on the way up.

should go in the documentation.

> :- inst uniq_tree23_gg =
> 	unique((
> 		empty
> 	;	two(ground, ground, uniq_tree23_gg, uniq_tree23_gg)
> 	;	three(ground, ground, ground, ground,
> 			uniq_tree23_gg, uniq_tree23_gg, uniq_tree23_gg)
> 	)).

That's unreferenced; you should just delete it.

> :- type tree23_res(K, V)	--->
> 		no_split(tree23(K, V))
> 	;	split(K, V, tree23(K, V), tree23(K, V)).

A comment explaining the purpose of this type and the
convert_from_res predicate would be helpful.

> :- pred tree23__insert_ext(tree23(K, V), K, V, tree23_res(K, V)).
> :- mode tree23__insert_ext(di, di, di, uo) is semidet.
> :- mode tree23__insert_ext(in, in, in, top_uo_tree23_res) is semidet.

Comments explaining what these two functions do would be helpful.

Cheers,
	Fergus.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.



More information about the developers mailing list