ken@aiva.ed.ac.uk (Ken Johnson) (08/31/88)
<<< CUT HERE: Below this line,this entire file is Prolog executable.
%
% Having once joined in a correspondence about arbitrarily re-arranging
% the elements of lists in linear time, it occurs to me that one might
% flatten the response time by converting the list to a term, exchanging
% elements of the term and building up a new one then converting the term
% back to a list. Converting term to list and back should take order N;
% accessing an element in a term with `arg' is done in constant time (on
% our system, anyway).
%
% It's also an interesting programming puzzle, so stop reading where I've
% put ^Ls if you want to try it yourself. (For people new to the Net:
% when ^L appears at the bottom left of your screen, you have to hit the
% top of the terminal really hard with your fist before it will show you
% the next page.)
%
% Digression: Of course, the question that goes before this is: Do you really need
% to use lists? The Pascal- or Basic-like algorithm assumes you are using
% arrays, that is, at the time you want to do the permutation you want the
% sets of objects to have array-like properties not list-like ones.
% So maybe you could speed up your program by using terms throughout instead
% of lists.
%
% Let us return to our muttons. The programming puzzles that arise are...
%
% Question 1: Given a list of ground* terms, convert them into a term (e.g.
% list_to_term([p,q,r,s],Term) should instantiate Term to
% '$list'(p,q,r,s). I don't care what the functor is. (I am sure it is also
% possible to have uninstantiated variables too but it's too hard for me,
% especially with lists like [A,B,A,C,C] with repeated uninstantiated
% variables! So this isn't guaranteed in such cases.)
%
% Hard way:
list_to_term(List,Term) :-
list_to_term(0,List,Term).
list_to_term(M,[H|T],Term) :-
N is M + 1,
list_to_term(N,T,Term),
arg(N,Term,H).
list_to_term(M,[],Term) :-
functor(Term,'$list',M).
% Easy way:
list_to_term_the_easy_way(List,Term) :-
Term =.. ['$list'|List].
% Question 2: Given a term of the form generated by list_to_term,
% recover the list that generated it. E.G. `term_to_list('$list'(p,q,r),L)
% should instantiate L to [p,q,r].
%
% Hard way:
term_to_list(Term,List) :-
functor(Term,_,N),
term_to_list(1,N,Term,A-A,List-[]).
term_to_list(M,N,_,A-B,A-B) :-
M > N.
term_to_list(M,N,Term,A-[Arg|B],C-D) :-
M =< N,
arg(M,Term,Arg),
M1 is M + 1,
term_to_list(M1,N,Term,A-B,C-D).
% Easy way:
% list_to_term_the_easy_way is bidirectional (above) !.
%
% Question 3:
% In the permutation problem you are going to need both a term whose
% args are the same as the input list, and a term whose args are the
% same as the output list. You can generate them both at the same time
% like this.
% Usage: list_to_term_with_copy([p,q,r],To,Ct,Cl) will instantiate
% To = '$list'(p,q,r), Ct = '$list'(_1,_2,_3), Cl = [_1,_2,_3].
%
% I can't see a fast easy way to do it with =.., though doubtless someone
% else will!
list_to_term_with_copy(List_in,Term_out,Copy_term,Copy_list) :-
list_to_term_with_copy(0,List_in,Term_out,Copy_term,Copy_list).
list_to_term_with_copy(M,[],Term_out,Copy_term,[]) :-
functor(Term_out,'$list',M),
functor(Copy_term,'$list',M).
list_to_term_with_copy(M,[H|T],Tm_out,Cp_term,[New|Cp_list]) :-
N is M + 1,
list_to_term_with_copy(N,T,Tm_out,Cp_term,Cp_list),
arg(N,Tm_out,H),
arg(N,Cp_term,New).
% Now, once you know what you want to exchange, you need only do
exchange_elements(I,J,Term1,Term2) :-
arg(I,Term1,Arg),
arg(J,Term2,Arg).
% and the copied list will come right of its own accord.
--
==============================================================================
From: Ken Johnson (Added ingredient: 50% Bicycle)
Address: AI Applications Institute, The University, EDINBURGH
Phone: 031-225 4464 ext 212
Email: k.johnson@ed.ac.uk
Disclaimer: These are my opinions. If you don't like them, I have others.