[m-dev.] Re: repost after modifications: additions to map/tree234

[Fergus Henderson]

On 30-Mar-1998, Lee Naish <lee at cs.mu.OZ.AU> wrote:
> Thomas Charles CONWAY <conway at cs.mu.OZ.AU> writes:
> 
> >library/map.m:
> >	added map__foldl/4 and map__map_values/3 which forward to the
> >	corresponding predicates in tree234.
> 
> I suggest using map__fold/4 rather than map__foldl/4.
> ... if the function map__foldl
> uses is not associative the result will depend on the order in which
> things are inserted into the tree and the insertion algorithm (something
> your average user doesn't want to think about).

At least with the current implementation in terms of 2-3-4 trees,
I don't think that is correct.  It is an invariant of the 2-3-4
tree representation that it is a sorted tree representation;
regardless of the insertion order or the shape of the tree,
so long as you traverse the nodes in the right order
(e.g. for a 2-node, traverse the left subtree, then the value
at the node, then the right subtree) then it will be guaranteed
to traverse the elements according to the order of their keys.

> Using the name
> map__foldl gives the impression that it would return the same result
> foldl would return if a (sorted?) list was used instead of a 234 tree.

Yes, indeed.  Well, almost.  The ordering is the same as it would be for
an association list sorted on the keys, but the things you are actually
folding are the data elements, not the keys.

I think the same would be true of almost any balanced tree implementation,
including ordinary binary search trees, red-black trees, AVL trees,
and BBB trees.  So I think it is reasonable to make this assumption
part of the interface to map.  I think that returning data in sorted order
would be a problem only for data structures like hash tables,
which have dramatically different performance characteristics,
and which are hence unlikely to ever replace map (although they
may well form the basis for a `uniq_map' type).

The documentation for map__foldl should say this, as should the
documentation for map__keys and map__values.

Note that if you just add a reverse mode to map__foldl, then you can
have map__foldr almost for free:

	map__foldr(Trans, Map0, Map, Acc0, Acc) :-
		RevTrans = (pred(Y::out, X::in, A::out, A0::in) :-
				Trans(X, Y, A0, A)),
		map__foldl(RevTrans, Map, Map0, Acc, Acc0).

The bad news is that this trick doesn't work if you want multiple
modes for map__foldr, due to Mercury only supporting higher-order
procedures, not higher-order predicates.  There's no way to make
the lambda expression RevTrans polymorphically moded.  :-(

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