johnson@cogsci.ed.ac.uk (Mark Johnson) (02/18/91)
Of course, any cyclic structure can be "broken up" into an acyclic structure by naming its nodes (say, with numbers) and storing their values in some sort of array. For some applications the packages in the standard libraries that run in n lg n time are satisfactory, but for, say, dealing with larger FSAs the non-constant access time is too great a price to pay. (Asserting the relevant facts into the database can give almost constant time access, but at the high cost of assertion, not to mention the abandonment of the simple logical semantics). Cyclic structures allow DFSAs to be implemented so that following an arc can be performed in constant time. Mark
bimandre@saturnus.cs.kuleuven.ac.be (Andre Marien) (02/19/91)
Cyclic structures are certainly possible, and do have some use.
As M. Johnson says in reply to D. Bowen, a database can be used but is
undesirable. It is indeed almost always "a BAD thing", to quote an expert.
Examples can always be criticized, but it helps to focus the discussion.
So, one more example: a tree with next and previous pointers.
One can build nice programs on top of this. Just one idea: in the
beginning you use an open ended tree (additions/search can be combined).
Then you 'link in' the next and previous pointers and now you can
walk around very easily and very fast.
Andre' Marien
bimandre@cs.kuleuven.ac.be
% copyrigth notice (sorry)
% author : Andre' Marien
% company : BIM
%
% please keep this notice with the code
% use is free for academic and research purposes
%
:-compatibility.
% list_to_tree(List,Tree)
%
% List : + : list of pairs Key-Data
%
% Tree : - :a tree with next and previous pointers instead of nil elements
% (called linked tree in this file)
list_to_tree(L,T) :-
make_base_tree(L,T),
link_tree(T) .
% make_base_tree(List,Tree)
%
% List : + : list of pairs Key-Data
%
% Tree : - : an open ended tree
%
make_base_tree([],T) .
make_base_tree([E|L],T) :-
insert_base_tree(T,E),
make_base_tree(L,T) .
insert_base_tree(T,K-D) :-
insert_base_tree(T,K,K-D) .
insert_base_tree(T,K,KD) :- var(T), !,
T = t(L,KD,R) .
insert_base_tree(t(L,K0-_,R),K,KD) :-
K @=< K0, !,
insert_base_tree(L,K,KD) .
insert_base_tree(t(L,K0-_,R),K,KD) :-
insert_base_tree(R,K,KD) .
% link_tree(Tree)
%
% Tree : in : an open ended tree
% out : a tree with next and previous pointers instead of free vars
% (these are wrapped in s/1 functor)
%
link_tree(T) :- var(T), !,
T = [] .
link_tree(T) :-
T = t(L,KD,R),
link_tree_l(L,[],T),
link_tree_r(R,T,[]) .
link_tree_l(T,Prev,Next) :- var(T), !,
T = s(Prev) .
link_tree_l(T,Prev,Next) :-
T = t(L,KD,R),
link_tree_l(L,Prev,T),
link_tree_r(R,T,Next) .
link_tree_r(T,Prev,Next) :- var(T), !,
T = s(Next) .
link_tree_r(T,Prev,Next) :-
T = t(L,KD,R),
link_tree_l(L,Prev,T),
link_tree_r(R,T,Next) .
% tree_to_list_a(Tree,AscendingList)
%
% Tree : + : a linked list
%
% AscendingList : - : a ascending list of the Key-Data pairs
%
tree_to_list_a(T,L) :-
min(T,MT),
tree_to_list_a_h(MT,L) .
tree_to_list_a_h([],[]) .
tree_to_list_a_h(t(LN,D,RN),[D|L]) :-
next(t(LN,D,RN),NT),
tree_to_list_a_h(NT,L) .
% tree_to_list_d(Tree,DecendingList)
%
% Tree : + : a linked tree
%
% DecendingList : - : a decending list of the Key-Data pairs
%
tree_to_list_d(T,L) :-
max(T,MT),
tree_to_list_d_h(MT,L) .
tree_to_list_d_h([],[]) .
tree_to_list_d_h(t(LN,D,RN),[D|L]) :-
previous(t(LN,D,RN),NT),
tree_to_list_d_h(NT,L) .
% min(Tree,Node)
%
% Tree : + : a linked tree
%
% Node : - : the smallest Node in this Tree
%
min(T,MT) :-
T = t(L,D,R),
min(L,T,MT) .
min(s(_),MT,MT) .
min([],MT,MT) .
min(t(L,D,R),_,MT) :-
min(L,t(L,D,R),MT) .
% max(Tree,Node)
%
% Tree : + : a linked tree
%
% Node : - : the biggest Node in this Tree
%
max(T,MT) :-
T = t(L,D,R),
max(R,T,MT) .
max(s(_),MT,MT) .
max([],MT,MT) .
max(t(L,D,R),_,MT) :-
max(R,t(L,D,R),MT) .
% previous(Node,PreviousNode)
%
% Node : + : some node of a linked tree
%
% PreviousNode : - : the previous node in the linked tree
%
previous(t(L,D,R),P) :-
previous_n(L,P) .
previous_n(s(P),P) .
previous_n(t(L,D,R),P) :-
max(R,t(L,D,R),P) .
% next(Node,NextNode)
%
% Node : + : some node of a linked tree
%
% NextNode : - : the next node in the linked tree
%
next(t(L,D,R),P) :-
next_n(R,P) .
next_n(s(P),P) .
next_n(t(L,D,R),P) :-
min(L,t(L,D,R),P) .
% write_rdbl(Tree)
%
% Tree : + : a linked tree
%
% This predicate writes a linked tree in a more readable form.
% If you look at it from the right of the page, it almost looks ok.
%
write_rdbl(T) :-
rewrite_tree(T,WT),
write_rdbl(WT,0) .
rewrite_tree(s([]),bp([])) :- ! .
rewrite_tree(s(t(_,PD,_)),bp(PD)) .
rewrite_tree(t(L,KD,R),t(NL,KD,NR)) :-
rewrite_tree(L,NL),
rewrite_tree(R,NR) .
write_rdbl(bp(D),N) :-
NN is N + 3,
spaces(NN), write('<-'), write(D), nl .
write_rdbl(t(L,KD,R),N) :-
NN is N + 3,
write_rdbl(R,NN), % yes, this is odd, but ok
spaces(NN), write(KD), nl,
write_rdbl(L,NN) . % yes, this is odd, but ok
% some tests (?)
%
list([4-vier,8-acht,2-twee,1-een,3-drie,5-vijf,6-zes,7-zeven]) .
list([e-1,f-2,a-3,c-4,b-5,d-6]) .
t0 :-
list(L),
list_to_tree(L,T),
write_rdbl(T), nl .
t1 :-
list(L), write(L), nl,
list_to_tree(L,T), write_rdbl(T), nl,
tree_to_list_a(T,AL), write(AL), nl .
t2 :-
list(L), write(L), nl,
list_to_tree(L,T), write_rdbl(T), nl,
tree_to_list_d(T,AL), write(AL), nl .