[m-dev.] for review: new predicates in map.m

[Peter Schachte]

On Tue, Oct 20, 1998 at 10:32:23PM +1000, Andrew Bromage wrote:
> > How inefficient is sorting a sorted list?
> 
> O(N log N) using list__sort/2 (the "standard" merge sort variation, which
> is par for the course in declarative languages).
> 
> It would be interesting to try different variations to see if any of them
> improved the average case.

You should check out Richard O'Keefe's SAMsort (Smooth Applicative
Merge) algorithm.  It's a mergesort variation that makes use of
existing order (and inverse order) in the list.  Richard did some
benchmarking of several sorting algorithms for Prolog, and this was
the best.  It doesn't seem to be in /The Craft of Prolog/.  It's in
the Quintus library, but that version is copyrighted.  I'll write to
Richard and see if there's a version I could give you.

> > > No, there'd just be one typeclass-polymorphic method map__key_set/2
> > > which would work for any kind of set.
> > 
> > If you push it to "any kind of collection," and replace map__keys with
> > that predicate, then that sounds really good to me.
> 
> Any kind of collection... including lists?  map__keys/2 would be
> redundant. :-)

That was my point.  One predicate which returns any sort of
collection would subsume map__keys/2, and so map__keys/2 would be a
perfectly good name for it.


-- 
Peter Schachte                | The only thing that makes life possible is
mailto:pets at cs.mu.OZ.AU       | permanent, intolerable uncertainty; not
http://www.cs.mu.oz.au/~pets/ | knowing what comes next.
PGP: finger pets at 128.250.37.3 |     -- Ursula K. Le Guin