Re: ord_select ?

On 13/02/2014, at 4:07 AM, Michael Hendricks wrote:
> Since ordsets are implemented as lists, you should be able to use select/3
> directly.

In my reply I had been going to say that,
but it's not actually true.

select/3 can be used
 1. to remove a (single copy of a) known element from a known list
 2. to iterate over all the elements of a list, backtracking over
    all N removals in O(N) total time.
 3. to iterate over all the ways to add a known element to a known
    list, backtracking over all legal results in O(N) total time.

When the lists are supposed to be *ordered* lists without
duplicates, the (+,+,?) mode works and the (-,+,?) mode works
but the (+,-,+) mode doesn't:
	select(b, S, [a,c])
has solutions S = [b,a,c] ; S = [a,b,c] ; S = [a,c,b]
and only one of those is a sorted set.

> That seems reasonable to me.  For large ordsets, a specialized version of
> select/3 could get better performance by utilizing the sort order.

The specialisation is to require the first argument and either
of the sets to be ground.  This lets you reduce the constant
factors by unrolling -- the Quintus version of ord_selectchk/3,
like the Quintus version of ord_memberchk/2, powers ahead
checking only every 4th element.  But it's _still_ linear time,
and if you are doing a lot of elementwise operations, you should
probably be using some sort of tree.

By the way, the code in my previous message was written for that
message and may be used freely and in particular may be included,
if tested and found to be working, in SWI Prolog.