Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!rice!uupsi!sunic!liuida!aste16!felkl
From: felkl@aste16.Berkeley.EDU (Feliks Kluzniak)
Newsgroups: comp.lang.prolog
Subject: Re: Heaps and other data structures (was: interesting exercise)
Message-ID: <1991Feb15.124544.5542@ida.liu.se>
Date: 15 Feb 91 12:45:44 GMT
References: <1991Feb12.013413.24312@cs.ubc.ca> <4765@goanna.cs.rmit.oz.au> <1991Feb13.235655.6202@cs.ubc.ca> <17853@cs.utexas.edu>
Sender: news@ida.liu.se (News Subsystem)
Reply-To: felkl@aste16.Berkeley.EDU (Feliks Kluzniak)
Organization: CIS Dept, Univ of Linkoping, Sweden
Lines: 132

In article <17853@cs.utexas.edu>, turpin@cs.utexas.edu (Russell Turpin) writes:
|> Given lists as primitive data structures, it is easy to create
|> heaps and all other tree-like data structures.  Unfortunately for
|> languages like Prolog and ML, there are many useful data
|> structures that involve cycles and hammocks.  As a simple
|> example, consider a tree each data node of which contains (1) a
|> person's name (and associated data), and (2) a pointer to the
|> node of that person's spouse.  The goal is to support a search
|> through the tree for a named individual, and to then retrieve the
|> data for the spouse in constant time. 
|> 
|> I would be interested if anyone can implement this kind of data
|> structure in Prolog.  (It is possible, of course, to perform the
|> desired application in Prolog using a different data structure.
|> As a computational engine, Prolog is Turing complete.  The issue
|> is not whether the application can be implemented Prolog, but
|> whether one can implement this particular data structure, with
|> its particular performance characteristics.)

Actually, this is quite easy.  Conventional implementations of Prolog
will allow you to create cyclic structures. (But you must know what you
are doing! In particular don't try to print them, and this includes
using the debugger.)  Such tricks are not pretty and in general not
recommended, but sometimes useful.

So, here goes. For simplicity, the information about a person consists
only of an unique name and a "pointer" to the spouse. Just for the fun
of it we will use an "open" binary search tree.

%%%  in_tree( + person record, +- tree )
%  Given a record whose name field is not a variable, locate it in the  tree
%  or insert it if not present.
%  Format of the tree:
%    a "normal" node is  t( left subtree, record, right subtree )
%    a leaf is a variable (new subtrees can be grafted here)
%  Format of the records:
%    p( name, spouse )  where name is an unique identifier and
%                             spouse is either a variable (i.e. no spouse)
%                                    or a person record.
%  NOTE: An attempt to re-insert the same person with a different spouse
%        will fail.

in_tree( p( Name, Spouse ), t( _, p( Name, Spouse ), _ ) ) :-
        nonvar( Name ).
in_tree( p( Name, Spouse ), t( Left, p( AName, _ ), _ ) ) :-
        nonvar( Name ),
        nonvar( AName ),
        Name @< AName,
        in_tree( p( Name, Spouse ), Left ).
in_tree( p( Name, Spouse ), t( _, p( AName, _ ), Right ) ) :-
        nonvar( Name ),
        nonvar( AName ),
        Name @> AName,
        in_tree( p( Name, Spouse ), Right ).


%  create_tree( + list of names, - tree )
%  Given a list of names create a tree of persons without spouses.

create_tree( [], _ ).
create_tree( [ Name | Names ], Tree ) :-
        in_tree( p( Name, _ ), Tree ),
        create_tree( Names, Tree ).



%%%  marry( + person record, + person record )
%  Connect the two records through their spouse fields,
%  fail if can't be done (i.e. at least one of the two fields 
%  is not a variable).
%  CAUTION: a cyclic structure is created here!

marry( P1, P2 ) :-
        P1 = p( _, P2 ),
        P2 = p( _, P1 ).



%%%  spouse_name( + person record, - spouse's name )
%  Retrieve the name of the spouse, return  unmarried  if none.

spouse_name( p( _, Spouse ), unmarried ) :-
        var( Spouse ).
spouse_name( p( _, Spouse ), SpouseName ) :-
        nonvar( Spouse ),
        Spouse = p( SpouseName, _ ).


%%%

test :- 
        create_tree( [ adam, jim, jack, eve, jill ], Tree ),
        write( 'The tree (no cyclic structures yet) :' ),  nl,
        write( Tree ),  nl,
        Bride = p( jill, _ ),
        Groom = p( jack, _ ),
        in_tree( Bride, Tree ),
        in_tree( Groom, Tree ),
        marry( Bride, Groom ),                  % jack <-> jill
        write( 'retrieval :' ),  nl,
        Person = p( jack, Spouse ),
        in_tree( Person, Tree ),
        spouse_name( Person, SpouseName ),
        write( 'Jack''s wife : ' ),
        write( SpouseName ),  nl,
        spouse_name( Spouse, SpousesSpouseName ),
        write( 'Jack''s wife''s husband : ' ),
        write( SpousesSpouseName ),  nl.

--------------------------------------------------------
aste16-2% sicstus
SICStus 0.7 #1: Tue Sep 25 16:52:29 MET DST 1990
| ?- [ex].
{consulting /tmp_mnt/auto/asterix3/guest/felkl/tmp/ex.pl...}
{/tmp_mnt/auto/asterix3/guest/felkl/tmp/ex.pl consulted, 140 msec 3414 bytes}

yes
| ?- test.
The tree (no cyclic structures yet) :
t(_170,p(adam,_164),t(t(t(_377,p(eve,_302),_379),p(jack,_233),t(_469,p(j
jill,_394),_471)),p(jim,_187),_218))
retrieval :
Jack's wife : jill
Jack's wife's husband : jack

yes
| ?- 

You may well ask: why doesn't the Prolog textbook contain such information?
If I may be allowed to paraphrase Lenin: there is such a book...

-- Feliks Kluzniak