🚀 go-pugleaf

From article <10208@goanna.cs.rmit.oz.au>, by ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe):
[about the trick of representing subsets of 1..N as 0, N-1 variables, 1]

> In the Quintus library, library(vsets) contains the text:
>     Richard A. O'Keefe got this trick from
>     Fernando C. N. Pereira who figured it out after
>     Alain Colmerauer told him it could be done.

Whoops.  I've used the QP library since 1.5, but didn't notice this sneak
in circa 2.5 (now on 3.1.1).  I shall look again to see what else is new.

> Lists are not the important point.  library(vsets), for example, uses
> compound terms (which makes fast "X ~= i" statements possible).

Here's my code using lists.  I convert an ordset (ordered list) of positive
integers to a unterminated list of variables (shared as appropriate), e.g.

    | ?- nat_ordset_to_uset( [1,3,4], A), write_nv( A).

    [A,B,B,C,1|D]

Each list is ~only as long as the largest element of the set (I think
this bit's original).  There's no limit to the size of sets.  Richard's
library(vsets) is limited to 254 elements, but when he generalises it,
it will be better all round for large sets, and faster if irrelevantly
less compact for small ones IMHO.  I wrote this code in July 1991.

demo :-
	Ns1 = [1,4,5],
	nat_ordset_to_uset( Ns1, Us1),
	write( Ns1), write( '	--> '), write( Us1), nl,
	Ns2 = [4,7,8],
	nat_ordset_to_uset( Ns2, Us2),
	write( Ns2), write( '	--> '), write( Us2), nl,
	Us1 = Us2,
	uset_to_nat_ordset( Us1, Ns),
	write( Ns), write( '	<-- '), write( Us1), nl.


%type	nat_ordset_to_uset( ordset(nat), uset)
%mode	nat_ordset_to_uset( +, -)

nat_ordset_to_uset( Ns, Us) :-
	Us = [0|_],		%  makes empty sets impossible
      %	Us = [_|_],		%  allow empty sets
	nat_ordset_to_uset_1( 1, Ns, Us).


%type	nat_ordset_to_uset_1( nat, ordset(nat), uset)
%mode	nat_ordset_to_uset_1( +, +, -)

nat_ordset_to_uset_1( _, [], [U|_]) :-
	!,
	U = 1.					%  empty set fails here

nat_ordset_to_uset_1( N, [N|Ns], [_,U1|Us]) :-
	!,
	M is N+1,
	nat_ordset_to_uset_1( M, Ns, [U1|Us]).

nat_ordset_to_uset_1( N, Ns, [U0,U1|Us]) :-
	U0 = U1,				%  unify to denote non-member
	M is N+1,
	nat_ordset_to_uset_1( M, Ns, [U1|Us]).


%type	uset_to_nat_ordset( uset, ordset(nat))
%mode	uset_to_nat_ordset( +, -)

uset_to_nat_ordset( Us, Ns) :-
	uset_to_nat_ordset_1( 1, Us, Ns).


%type	uset_to_nat_ordset_1( nat, uset, ordset(nat))
%mode	uset_to_nat_ordset_1( +, +, -)

uset_to_nat_ordset_1( N, [U0,U1|Us], Ns) :-
	 ((	U0 \== U1
	 )->(	Ns = [N|Ns1]
	 );(	Ns = Ns1
	 )),
	 ((	U1 == 1
	 )->(	Ns1 = []
	 );(	M is N+1,
		uset_to_nat_ordset_1( M, [U1|Us], Ns1)
	 )).

----
  __   __    Paul Singleton (Mr)           JANET: paul@uk.ac.keele.cs
 |__) (__    Computer Science Dept.        other: paul@cs.keele.ac.uk
 |  .  __).  Keele University, Newcastle,    tel: +44 (0)782 621111 x7355
             Staffs ST5 5BG, ENGLAND         fax: +44 (0)782 713082