Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!turpin
From: turpin@cs.utexas.edu (Russell Turpin)
Newsgroups: comp.lang.prolog
Subject: Heaps and other data structures (was: interesting exercise)
Summary: Tree-like structures are easy, more
	 general data structures are impossible.
Message-ID: <17853@cs.utexas.edu>
Date: 14 Feb 91 01:33:25 GMT
References: <1991Feb12.013413.24312@cs.ubc.ca> <4765@goanna.cs.rmit.oz.au> <1991Feb13.235655.6202@cs.ubc.ca>
Organization: U. Texas CS Dept., Austin, Texas
Lines: 24

-----
In article <1991Feb13.235655.6202@cs.ubc.ca> poole@cs.ubc.ca (David Poole) writes:
>> Wrong.  Heaps work very nicely indeed in Prolog. ...

> Here is a simple solution ...

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.)

Russell