[mercury-users] Self-referential data structures

[Warwick HARVEY]

Peter Schachte <pets at students.cs.mu.OZ.AU> writes:
> On Mon, 1 Dec 1997, Fergus Henderson wrote:
>
> > I have just thought of another solution.  We could provide a new
> > procedure in the `store' module to create a circular element.
> > This procedure would take as an argument a function which when
> > given a reference (mutvar) to type T produces a value of type T.
>
> Could you give us a quick example of how this could be used?

Given

    % Provided by store module
:- pred new_circ_elem(func(mutvar(T, S)) = T is det,
		      mutvar(T, S)::out,
                      store(S)::di, store(S)::uo) is det.

    % From the module you're writing
:- type elem(T, S) ---> elem(T, handle(T, S), handle(T, S)).
                   % i.e. elem(Data, Prev, Next)
:- type handle(T, S) == mutvar(elem(T, S), S).

You can write:

    ...
    new_circ_elem(new_single_element_circular_list(Data), Ref, S0, S1),
    ...

:- pred new_single_element_circular_list(T, handle(T, S), elem(T, S)).
:- mode new_single_element_circular_list(in, in, out) is det.

new_single_element_circular_list(Data, Ref, Elem) :-
    Elem = elem(Data, Ref, Ref).

As Fergus writes:

> > This avoids the need for null references (and hence the need to
> > document for every procedure taking a reference what happens if
> > the reference is null).  It avoids the need to use a maybe(T) type.
>
> How?  In many uses of circular structures, there's still the need for
> empty structures.  How can you handle these without some use of a
> maybe type, or making everything semidet/nondet?

Sure, and if you need empty structures, you still have to use maybe(T) or
similar.  But in many cases you don't (e.g. circular lists - all elements
always have a previous and next), and so if you can avoid using them in
those cases, you win.  This is what Fergus is referring to (and not general
circular data structures), since this is what I raised as being a problem
last week (how to create an element that points to itself without requiring
the artificial introduction of maybes or similar).

				Warwick

----------------------------------------------------------------------------
Warwick Harvey                                    email: warwick at cs.mu.OZ.AU
Department of Computer Science                        phone: +61-3-9344-9171
University of Melbourne                                 fax: +61-3-9348-1184
Parkville, Victoria, AUSTRALIA 3052     web: http://www.cs.mu.OZ.AU/~warwick