turpin@cs.utexas.edu (Russell Turpin) (02/14/91)
----- 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
felkl@aste16.Berkeley.EDU (Feliks Kluzniak) (02/15/91)
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
micha@ecrc.de (Micha Meier) (02/18/91)
In article <1991Feb15.124544.5542@ida.liu.se> felkl@aste16.Berkeley.EDU (Feliks Kluzniak) writes: > >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.) This is not quite correct, there are Prolog systems (e.g. Sepia), which allow you to set a bound on the depth of the terms being printed, so that you can use even the debugger without any problems. Besides that, any decent Prolog system allows to use portray/1 in the debugger so that you can decide yourself how deep and in which form you want to print your infinite terms. --Micha -- E-MAIL micha@ecrc.de MAIL Micha Meier ECRC, Arabellastr. 17 8000 Munich 81 Germany
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/19/91)
In article <17853@cs.utexas.edu>, turpin@cs.utexas.edu (Russell Turpin) writes: > 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. The answer when presented with a problem like this is to refuse to do it. Take a step back. Ask "what is this useful for?" Do something else that is clean and fast and solves the problem. Imagine, then, that we are given as our raw data, two lists: a list of Person-Info pairs People a list of Person-Person pairs Matings and we want to have a data structure supporting both person_info(Person, Collection, Info) person_and_spouse_info(Person, Collection, PersonInfo, SpouseInfo) "search for a named individual and retrieve the data for the spouse in constant time". Step 1: sort People Step 2: make Matings symmetric (so X-Y and Y-X are both present) and sort it. Step 3: merge the sorted People and Matings, producing a new Mated list, holding Person-mating(Spouse,PersonInfo,SpouseInfo) pairs. Step 4: build a fast access structure for People, PeopleIndex (say a binary tree) Step 5: build a fast access structure for Matings, MatingsIndex (say a binary tree) Step 6: represent the entire collection by a pair collection(PeopleIndex,MatingsIndex) person_info(Person, collection(PeopleIndex,_), Person-Info) :- lookup(Person, PeopleIndex, Info). person_and_spouse_info(Person, collection(_,MatingsIndex), Person-PersonInfo, Spouse-SpouseInfo) :- lookup(Person, MatingsIndex, mating(Spouse,PersonInfo,SpouseInfo)). You don't have cross-links *within* the structure. Instead you have multiple index structures *above* your raw data. No, this doesn't do it the *way* that the poster demanded. So? In a real application, you shouldn't *care*. You should care about correctness and efficiency, but not how it's done. What's more, in a real application, it's not clear to me why it is so all-fired important to get to the spouse (which one?) in constant time. If it takes O(f(N)) time to get to the first person and find there the spouse's name, then it'll take O(f(N)) time to get to the spouse, so the total will be O(f(N)) + O(f(N)) which is still O(f(N)). Bottom line: Yes, some *ways* of doing things *are* slow in Prolog. If you want a language that'll let you hack arbitrary data structures any way you want, use C++ (and *some* day they'll tell you what it means, maybe). -- Professional programming is paranoid programming