[mercury-users] Circular lists

[Fergus Henderson]

On Thu, Nov 27, 1997 at 11:21:01AM +1100, Thomas Charles CONWAY wrote:
> 
> With all this talk of circular lists, I thought people might be
> interested/amused by the following.
> 
> Beware, it is a complete hack, but IMHO quite cute.

Heaven forbid!  "Cute" is not the word that springs to mind ;-)

Actually you don't need to use the C interface.  You can do this
sort of thing using the existing features of Mercury (>= 0.7.2),
namely the `store' module, as shown below.

	:- module inflist.
	:- interface.
	:- import_module list.

	:- pred circularize(list(T)::di, list(T)::out) is det.

	:- implementation.
	:- import_module store.

	circularize(A, B) :-
		store__init(S0),
		store__new_ref(A, ARef, S0, S1),
		clobber_tail(ARef, ARef, S1, S2),
		store__extract_ref_value(S2, ARef, B).

	:- pred clobber_tail(ref(list(T), S)::in, ref(list(T), S)::in,
				store(S)::di, store(S)::uo) is det.

	clobber_tail(TailRef, HeadRef) -->
		store__ref_functor(TailRef, _Name, Arity),
		( { Arity = 0 } ->
			store__set_ref(TailRef, HeadRef)
		;
			store__arg_ref(TailRef, 1, NewTailRef),
			clobber_tail(NewTailRef, HeadRef)
		).

I'm not sure that this is a virtue.  If you want to manipulate
circular lists, then you are better off keeping the representation
as a reference and store, rather than extracting a circular value
using store__extract_ref_value/3, because operations on a circular
values are likely to loop.

Incidentally, the above method is similar to Warwick's "Solution 2";
the difference is that instead of using the `no' functor of a `maybe' type,
we're using the `[]' functor of the list type.

Note that store__extract_ref_value/3 does not do any check for cycles,
so it is sound only if the semantics of equality do NOT include
finiteness axioms (i.e. axioms of the form `all [X] X \= f(..., X, ...)',
in particular for lists, `all [X] X \= [_|X]').  The Mercury language
reference manual is a little bit vague on this point: it just refers to
"the usual equality axioms".  Normally the mode system prevents you from
creating circular values, so the point is moot.  However it is possible
to create circular values using the `store' module, as shown above, so
I guess we should clarify that.

Also I should point out that type `ref' defined in the `store' module is
a fairly low-level facility, and that it is often better to write code at a
higher level.  For example, for circularly linked lists it would be
better to use store's `mutvar' type rather than its `ref' type.
The fact that it is _possible_ to write very low-level code doesn't mean
that it is a good idea.

Hmm, time to start the obfuscated Mercury competition? ;-)

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   WWW: <http://www.cs.mu.oz.au/~fjh>  
Note: due to some buggy software and a (probably accidental)
denial-of-service attack, any mail sent to me between
	Tue Nov 25 20:00:00 UTC (6am Wed, local time)
and	Wed Nov 26 06:00:00 UTC (4pm, local time)
may have gone into the bit-bucket.  Please re-send it.