% ===========================================================================
% Deklaratív Programozás 1.-2. gyakorlat, Prolog listakezelő eljárások
% ===========================================================================

% I. rész: append és társai
% -------------------------

% append(L1, L2, L3): Az L3 lista az L1 és L2 listák elemeinek 
% egymás után fűzésével áll elő.
append([], L, L).                 % Üres listát L elé füzve L-et kapunk.
append([X|L1], L2, [X|L3]) :-     % Egy [X|L1] listát L2 elé füzve egy [X|L3] listát kapunk
        append(L1, L2, L3).       % ha L1-et L2 elé füzve L3-at kapjuk.

% Új anyag: a funktor fogalma:

% A nem-változó kifejezésekhez Prologban funktor-t rendelünk.

% Egy f(a1, ..., an) n-argumentumú struktúra funktora
% (ahol f a struktúra neve): f/n.
% Egy c (név- vagy szám-)konstans funktora: c/0

% Egy eljáráshoz tartozó klózok fejeinek funktora ugyanaz, ezt hívjuk
% az eljárás funktorának.
 
% Az eljárást tehát a funktora azonosítja.

% Prologban megengedett az hogy ugyanazt az eljárásnevet több eljárásban is
% használjuk, különböző argumentumszámokkal. Így például ugyanabban a programban
% egyszerre szerepelhet az append/3 és az append/4 funktorú eljárás (lásd alább).


% Új anyag: a móddeklaráció

% A móddeklaráció formája

% :- mode <eljárásnév>(<mód>, ..., <mód>)

% ahol <mód> lehet +, -, vagy ?.

% A + mód jelentése: az adott argumentum nem változó.
% A - mód jelentése: az adott argumentum változó
% A ? mód jelentése: az adott argumentum lehet változó és nem-változó is.

% Példa:

:- mode append(+,+,+).

% A fenti móddeklaráció jelentése: deklaráljuk, hogy az append/3 eljárást csak
% behelyettesített argumentumokkal hívjuk meg. A móddeklarációkat a Prolog rendszerek
% többsége figyelemen kívül hagyja.

% Hajtsuk végre  a következő append hívásokat, rajzoljuk fel a keresési fákat!

% ?- append([1,2], [3,4], L).         % (1a)
% ?- append([1,2], L2, L3).           % (1b)
% ?- append(L1, L2, [1,2,3,4]).       % (2)
% ?- append([1,2], L2, [1,2,3,4]).    % (3)
% ?- append(L1, [a], L3).             % (4)

% Kövessük végig az eredménylisták építését!

% Vegyük észre, hogy az append/3 eljárásban a második argumentumban levő
% Prolog kifejezés behelyettesítettsége, üres vagy nemüres lista volta nem
% játszik szerepet: az (1) és (2) példák ugyanazt a futást, ugyanazt a
% keresési teret adják. 

% Az egyes hívásoknak megfelelő módok:

% (1a) és (1b):  append(+. ?. -).
% (2):           append(-. ?. +).
% (3):           append(+. ?. +).
% (4):           append(-. ?. -).

% Vegyük észre, hogy az append/3 eljárás végtelen választási pontot hoz létre, 
% ha az append(-, +, -) vagy append(-, -, -) módban hívjuk meg:

% | ?- append(L1, [a], L2).
% L1 = [], L2 = [a] ? ;
% L1 = [_A], L2 = [_A,a] ? ;
% L1 = [_A,_B], L2 = [_A,_B,a] ? ;
% L1 = [_A,_B,_C], L2 = [_A,_B,_C,a] ? ;
% L1 = [_A,_B,_C,_D], L2 = [_A,_B,_C,_D,a] ? ;
% L1 = [_A,_B,_C,_D,_E], L2 = [_A,_B,_C,_D,_E,a] ? ;
% L1 = [_A,_B,_C,_D,_E,_F], L2 = [_A,_B,_C,_D,_E,_F,a] ? ;
% L1 = [_A,_B,_C,_D,_E,_F,_G], L2 = [_A,_B,_C,_D,_E,_F,_G,a] ? ;
% L1 = [_A,_B,_C,_D,_E,_F,_G,_H], L2 = [_A,_B,_C,_D,_E,_F,_G,_H,a] ? ;
% L1 = [_A,_B,_C,_D,_E,_F,_G,_H,_I], L2 = [_A,_B,_C,_D,_E,_F,_G,_H,_I,a] ? ;
% L1 = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J], L2 = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J|...] ? <0
% L1 = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J], L2 = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,a] ? 
% yes
% | ?- 

% Példák az append/3 alkalmazására:

% Írjuk  meg a következő fejkommenttel jellemzett eljárásokat!

% ------------
% append(L1, L2, L3, L123) : L1, L2 és L3 egymás után füzése az L123 listát adja.

% Első, nem hatékony, szétszedésre nem alkalmas változat:
append0(L1, L2, L3, L123) :-
	append(L1, L2, L12), append(L12, L3, L123).

% | ?- append0(L1, L2, L3, []).
% L1 = [],
% L2 = [],
% L3 = [] ? ;
% végtelen ciklus!
% ^C  
% Prolog interruption (h for help)? a
% % Execution aborted
% % source_info
% | ?-

% Hatékony, szétszedésre is alkalmas változat:
append(L1, L2, L3, L123) :-
	append(L1, L23, L123), append(L2, L3, L23).

% ------------
% párban(Lista, Elem): A Lista számlistának Elem olyan
% eleme, amelyet egy ugyanilyen elem követ.
párban(L, E) :-
    append(_, [E,E|_], L).

% | ?- párban([1,8,8,3,4,4], E).
%        E = 8 ? ; E = 4 ? ; no

% ------------
% dadogó(L, D): D olyan nem üres részlistája L-nek,
% amelyet egy vele megegyező részlista követ.
dadogó(L, D) :-
        append(_, Farok, L),
        D = [_|_],
        append(D, Vég, Farok),
        append(D, _, Vég).

% | ?- dadogó([2,2,1,2,2,1], D).
%        D = [2] ? ; D = [2,2,1] ? ; D = [2] ? ; no


% ------------
% nrev(L, R): Az R lista az L megfordítása --- naív megoldás.
nrev([], []).
nrev([X|L], R) :-
    nrev(L, RL),
    append(RL, [X], R).

% ------------
% reverse(L, R): Az R lista az L megfordítása.
% Lineáris lépésszámú megoldás.
reverse(L, R) :-  revapp(L, [], R).

% ------------
% revapp(L1, L2, R): L1 megfordítását L2 elé fűzve kapjuk R-t.
revapp([], R, R).
revapp([X|L1], L2, R) :-
    revapp(L1, [X|L2], R).

% append/3 és revapp/3 analógiája:
%            - append/3: lista építése előlről 
%            - revapp/3: lista építése hátulról 

% ------------
% permutation(Lista, Perm): Lista egy permutációja a Perm lista.
permutation([], []).
permutation(Lista, [Elso|Perm]) :- 
	select(Elso, Lista, Maradek),
	permutation(Maradek, Perm).


% II. rész: beszúrás listába adott pozícióra
% ------------------------------------------

% Examples of list handling predicates


% ===========================================

% ---------------------------------------------------------------
% insert_nth(N, L0, E, L): inserting element E into list L0
% before its Nth element gives list L.

% If N is known, use versions 1 or 2 below.
% If N in not known, then use version 3 if L0 is known and
% version 4 if L is known.

% :- mode insert_nth_1(+, ?, ?, ?).
insert_nth_1(1, L0, E, [E|L0]).
insert_nth_1(N, [X|L0], E, [X|L]) :-
        N > 1, N1 is N-1,
        insert_nth_1(N1, L0, E, L).

                %  | ?- insert_nth_1(3, [a,b,c,d,e], i, L).
                %  L = [a,b,i,c,d,e] ? ;
                %  no
                %  | ?- insert_nth_1(3, [a,b,c,d,e], X, L).
                %  L = [a,b,X,c,d,e] ? ;
                %  no
                %  | ?- insert_nth_1(3, L0, X, L).
                %  L = [_A,_B,X|_C],
                %  L0 = [_A,_B|_C] ? ;
                %  no
                %  | ?- insert_nth_1(3, [1], 2, L).
                %  no
                %  | ?- insert_nth_1(N, [1], 2, [1,2]).
                %  ! Instantiation error in argument 1 of > /2
                %  ! goal:  _56>1
                %  | ?-

% Új anyag:
% Feltételes szerkezet Prologban:

%              ( feltétel -> akkor
%              ; egyébként
%              )

% jelentése: ha a "feltétel" célsorozat sikeresen lefut,
% akkor az "akkor"célsorozatot hajtjuk végre,
% egyébként az "egyébként" célsorozatot.

% :- mode insert_nth_2(+, ?, ?, ?).
insert_nth_2(N, L0, E, L) :-
        (   N =:= 1 ->  L = [E|L0]
        ;   N > 1, N1 is N-1,
            L0 = [X|L1], L = [X|L2],
            insert_nth_2(N1, L1, E, L2)
        ).

                %  Calling insert_nth_2/4 produces the exactly same 
                %  answers as calling insert_nth_1/4, as shown above.

% :- mode insert_nth_3(?, +, ?, ?).
insert_nth_3(N, L0, E, L) :-
        append(L1, L2, L0),
        length(L1, N1),
        N is N1+1,
	append(L1, [E|L2], L).

                %  | ?- insert_nth_3(N, [1], 2, [1,2]).
                %  N = 2 ? ;
                %  no
                %  | ?- insert_nth_3(N, [1], 2, L).
                %  L = [2,1],
                %  N = 1 ? ;
                %  L = [1,2],
                %  N = 2 ? ;
                %  no
                %  | ?- insert_nth_3(N, [1], X, L).
                %  L = [X,1],
                %  N = 1 ? ;
                %  L = [1,X],
                %  N = 2 ? ;
                %  no
                %  | ?- insert_nth_3(N, L0, X, [1,2]).
                %  N = 1,
                %  X = 1,
                %  L0 = [2] ? ;
                %  N = 2,
                %  X = 2,
                %  L0 = [1] ? ;
                %  Prolog interruption (h for help)? a
                %  % Execution aborted
                %  | ?- 

% Note: the execution has been aborted above because Prolog is in an infite
% loop here. This is so in the examples shown later in this file, too.

% :- mode insert_nth_4(?, ?, ?, +).
insert_nth_4(N, L0, E, L) :-
        append(L1, [E|L2], L),
        length(L1, N1),
        N is N1+1,
        append(L1, L2, L0).

                %  | ?- insert_nth_4(N, [1], 2, [1,2]).
                %  N = 2 ? ;
                %  no
                %  | ?- insert_nth_4(N, [1], X, [1,2]).
                %  N = 2,
                %  X = 2 ? ;
                %  no
                %  | ?- insert_nth_4(N, L0, X, [1,2]).
                %  N = 1,
                %  X = 1,
                %  L0 = [2] ? ;
                %  N = 2,
                %  X = 2,
                %  L0 = [1] ? ;
                %  no
                %  | ?- insert_nth_4(N, [1], 2, L).
                %  L = [2,1],
                %  N = 1 ? ;
                %  L = [1,2],
                %  N = 2 ? ;
                %  Prolog interruption (h for help)? a
                %  % Execution aborted

% Examples using insert_nth:

text("abrakadabra").
text("almakarika").
text("szilva").
text("fahej").
text("barnacukor").
text("haragosaik").

% find texts with letter `a' at 4th position, and print
% the text without this letter `a':
test1_slow :-
        (   text(Pat),
            insert_nth_1(4, SubPat, 0'a, Pat), % which other variants?
            format('~s\n', [SubPat]),
            fail
        ;   true
        ).

test1_fast :-
        insert_nth_1(4, SubPat, 0'a, Pat), % which other variants?
        (   text(Pat),
            format('~s\n', [SubPat]),
            fail
        ;   true
        ).

                %  | ?- test1_slow.
                %  abrkadabra
                %  almkarika
                %  hargosaik
                %  yes
                %  | ?- test1_fast.
                %  abrkadabra
                %  almkarika
                %  hargosaik
                %  yes
                %  


% find positions on which a given letter occurs in a text and
% print the text without this letter:
test2 :-
        insert_nth_4(N, Txt, 0'a, "abrakadabra"),
        format('~d -- ~s\n', [N,Txt]),
        fail.
test2.

                %  | ?- test2.
                %  1 -- brakadabra
                %  4 -- abrkadabra
                %  6 -- abrakdabra
                %  8 -- abrakadbra
                %  11 -- abrakadabr
                %  yes

% insert a given letter into each even position of a text:
test3 :-
        insert_nth_3(N, "krumpli", 0'a, Txt),
        N mod 2 =:= 0,
        format('~d -- ~s\n', [N,Txt]),
        fail.
test3.

                %  | ?- test3.
                %  2 -- karumpli
                %  4 -- kruampli
                %  6 -- krumpali
                %  8 -- krumplia
                %  yes

% Home Exercise 1.1: 
% ==================
% Write a variant insert_nth_5/4 which works for both modes
% :- mode insert_nth_5(?, +, ?, ?).
% :- mode insert_nth_5(?, ?, ?, +).
% i.e. when at least one of the list arguments is given.
% It is allowed for insert_nth_5/4 to loop if both list arguments
% are open ended.
%   | ?- insert_nth_5(N, [a,b], X, L).
%   L = [X,a,b],
%   N = 1 ? ;
%   L = [a,X,b],
%   N = 2 ? ;
%   L = [a,b,X],
%   N = 3 ? ;
%   no
%   | ?- insert_nth_5(N, L0, X, [a,b,c]).
%   N = 1,
%   X = a,
%   L0 = [b,c] ? ;
%   N = 2,
%   X = b,
%   L0 = [a,c] ? ;
%   N = 3,
%   X = c,
%   L0 = [a,b] ? ;
%   no
%   | ?- insert_nth_5(1, L0, E, L).
%   L = [E|L0] ? ;
%   Prolog interruption (h for help)? a
%   % Execution aborted

% Home Exercise 1.2 (may be difficult):
% =====================================
% Write a predicate insert_nth_p/4 which is the same as insert_nth_K/4
% except that the first argument is represented as a Peano number, i.e.
% 0 ==> 0, 1 ==> s(0), 2 ==> s(s(0)), ...
% An arbitrary call of insert_nth_p(N, L0, E, L), having only a finite
% number of solutions, should succeed or fail in finite time.

% Note that the predicate insert_nth_p/4 can be implemented using less than
% 100 non-layout characters!

%  | ?- insert_nth_p(s(s(0)), L0, E, L).
%  L = [_A,E|_B],
%  L0 = [_A|_B] ? ;
%  no
%  | ?- insert_nth_p(N, [a], E, L).
%  L = [E,a],
%  N = s(0) ? ;
%  L = [a,E],
%  N = s(s(0)) ? ;
%  no
%  | ?- insert_nth_p(N, L0, E, [a,b]).
%  E = a,
%  N = s(0),
%  L0 = [b] ? ;
%  E = b,
%  N = s(s(0)),
%  L0 = [a] ? ;
%  no
%  | ?- insert_nth_p(N, [b|L0], E, [c|L]).
%  E = c,
%  L = [b|L0],
%  N = s(0) ? ;
%  no
%  | ?- insert_nth_p(N, [b|L0], E, [c,d|L]).
%  no

% Home Exercise 1.3 (difficult)
% =============================

% Write a predicate insert_nth_6/4 which has the same property as
% insert_nth_p/4: an arbitrary call of insert_nth_6/4, having only a finite
% number of solutions, should complete in finite time, and should
% never raise an exception.  Note that this means that insert_nth_6/4
% completes in finite time for all sample calls of insert_nth_K/4, 1=<K=<5,
% given above.

% The predicate insert_nth_6/4 requires the use of non-logical features of
% Prolog, such as nonvar/1, integer/1, etc.

%  | ?- insert_nth_6(2, L0, E, L).
%  L = [_A,E|_B],
%  L0 = [_A|_B] ? ;
%  no
%  | ?- insert_nth_6(N, [a], E, L).
%  L = [E,a],
%  N = 1 ? ;
%  L = [a,E],
%  N = 2 ? ;
%  no
%  | ?- insert_nth_6(N, L0, E, [a,b]).
%  E = a,
%  N = 1,
%  L0 = [b] ? ;
%  E = b,
%  N = 2,
%  L0 = [a] ? ;
%  no
%  | ?- insert_nth_6(N, [b|L0], E, [c|L]).
%  E = c,
%  L = [b|L0],
%  N = 1 ? ;
%  no
%  | ?- insert_nth_6(N, [b|L0], E, [c,d|L]).
%  no


% III. rész: További listakezelő eljárások
% ----------------------------------------

% ---------------------------------------------------------------------------
% split_list(N, L, L1, L2): L can be split to L1 and L2 where the length of
% L1 is N.

% mode split_list_1(+, ?, ?, ?).
split_list_1(0, L, [], L).
split_list_1(N, [X|L], [X|L1], L2) :-
        N > 0,
        N1 is N-1,
        split_list_1(N1, L, L1, L2).

% mode split_list_2(+, ?, ?, ?).
split_list_2(N, L, L1, L2) :-
        (   N =:= 0 -> L1 = [], L2 = L
        ;   N > 0, N1 is N-1,
            L = [X|RL], L1 = [X|RL1],
            split_list_2(N1, RL, RL1, L2)
        ).

                %  | ?- split_list_1(3, [a,b,c,d], L1, L2).
                %  L1 = [a,b,c],
                %  L2 = [d] ? ;
                %  no
                %  | ?- split_list_1(5, [a,b,c,d], L1, L2).
                %  no
                %  | ?- split_list_1(2, L, [a,b], [q,r]).
                %  L = [a,b,q,r] ? ;
                %  no
                %  | ?- split_list_1(2, L, [a], [q,r]).
                %  no
                %  | ?- split_list_1(2, L, L1, [q,r]).
                %  L = [_A,_B,q,r],
                %  L1 = [_A,_B] ? ;
                %  no
                %  | ?- split_list_1(2, L, L1, L2).
                %  L = [_A,_B|L2],
                %  L1 = [_A,_B] ? ;
                %  no
                %  | ?- split_list_1(N, [a,b,q,r], [a,b], [q,r]).
                %  ! Instantiation error in argument 1 of > /2
                %  ! goal:  _56>0
                %  

% Home Exercise 1.4
% =================
% 
% In the database of text/1 find strings with at least 5 characters
% and print the first 5 characters and the rest separated by a space.  
% Try to be as efficient as in test1_fast.


% mode split_list_3(?, +, ?, ?).  % approx.
split_list_3(N, L, L1, L2) :-
        append(L1, L2, L),
        length(L1, N).

% mode split_list_4(+, +, ?, ?). % approx.
split_list_4(N, L, L1, L2) :-
        length(L1, N),
        append(L1, L2, L).

                %  | ?- split_list_3(2, [a,b,c,d], L1, L2).
                %  L1 = [a,b],
                %  L2 = [c,d] ? ;
                %  no
                %  | ?- split_list_3(N, [a,b,q,r], [a,b], [q,r]).
                %  N = 2 ? ;
                %  no
                %  | ?- split_list_3(2, L, [a,b], [q,r]).
                %  L = [a,b,q,r] ? ;
                %  no
                %  | ?- split_list_3(2, L, L1, L2).
                %  L = [_A,_B|L2],
                %  L1 = [_A,_B] ? ;
                %  Prolog interruption (h for help)? a
                %  % Execution aborted
                %  | ?- split_list_4(N, [a,b,q,r], [a,b], [q,r]).
                %  N = 2 ? ;
                %  no
                %  | ?- split_list_4(N, [a,b,q,r], L1, [q,r]).
                %  N = 2,
                %  L1 = [a,b] ? ;
                %  Prolog interruption (h for help)? a
                %  % Execution aborted
                %  

% Home Exercise 1.5
% =================
% 
% (a) Write a predicate mklist specified below
%
% 	mklist(+N, -L): L = [N,...,3,2,1].
%
% (b) Measure the execution time of finding the solution of split_list_3/4
%     using the following goal:
%
% | ?- mklist(5000, _L), statistics(runtime, _),
%      split_list_3(4000, _L, L1, L2),
%      statistics(runtime, [_,T]).
%
%     Similarly measure the execution time of split_list_4/4.
%
% (c) Explain the difference in execution time.
%
% (d) Measure the execution time of finding all solutions of split_list_3/4
%     using the following goal:
%
% | ?- mklist(5000, _L), statistics(runtime, _),                            
%      (   split_list_3(4000, _L, L1, L2), write('solution found'), nl, fail
%      ;   statistics(runtime, [_,T])
%      ).
%
%     Similarly measure the execution time of split_list_4/4.
%
% (e) Explain the differences in execution time.



% ---------------------------------------------------------------------------
% sublist(L0, N, Size, L): L is the sublist of L0 starting at position N
% and of length Size.

% mode sublist(?, +, +, ?).
sublist(L0, N, Size, L) :-
        N1 is N-1,
        split_list_1(N1, L0, _, L1),
        split_list_1(Size, L1, L, _).

                %  | ?- sublist([a,b,c,d,e], 2, 3, SL).
                %  SL = [b,c,d] ? ;
                %  no
                %  | ?- sublist(L, 2, 3, SL).
                %  L = [_A,_B,_C,_D|_E],
                %  SL = [_B,_C,_D] ? ;
                %  no

% Home Exercise 1.6
% =================
 
% Produce efficient versions of sublist/4 by combining the two uses of the
% split_list_1 predicate. Make another variant of sublist/4 by using 
% split_list_2.


% ---------------------------------------------------------------------------
% nth_elem(N, L, E): E is the Nth element of list L.
% The head is the 1st element.

% mode nth_elem_1(+, ?, ?).
nth_elem_1(N, L, E) :-
        N1 is N-1,
        split_list_1(N1, L, _, [E|_]).  % version 2 is OK, too

% mode nth_elem_2(+, ?, ?).
% mode nth_elem_2(?, +, ?).
nth_elem_2(N, L, E) :-
        nth(N, L, E).  % defined in library lists

                %  | ?- nth_elem_1(3, [a,b,c,d], X).
                %  X = c ? ;
                %  no
                %  | ?- nth_elem_1(1, [a,b,c,d], X).
                %  X = a ? 
                %  yes
                %  | ?- nth_elem_1(2, L, X).
                %  L = [_A,X|_B] ? ;
                %  no
                %  | ?- nth_elem_1(N, [a,b,c,d], X).
                %  ! Instantiation error in argument 2 of is/2
                %  ! goal:  _79 is _76-1
                %  | ?- nth_elem_2(N, [a,b,c,d], X).
                %  N = 1,
                %  X = a ? ;
                %  N = 2,
                %  X = b ? ;
                %  N = 3,
                %  X = c ? ;
                %  N = 4,
                %  X = d ? ;
                %  no
                %  | ?- nth_elem_2(2, L, X).
                %  L = [_A,X|_B] ? ;
                %  no
                %   


% Home Exercise 1.7
% =================
% 
% Produce efficient versions of nth_elem for mode (+,?,?), by specialising
% the code of
%
% (a) split_list_1
% (b) split_list_2



% ---------------------------------------------------------------------------
% zip_lists(Xs, Ys, XYs): XYs is the list of pairs of the corresponding
% elements of Xs and Ys.

% mode zip_lists(+, ?, ?).
% mode zip_lists(?, +, ?).
% mode zip_lists(?, ?, +).
zip_lists([], [], []).
zip_lists([X|Xs], [Y|Ys], [X-Y|XYs]) :-
        zip_lists(Xs, Ys, XYs).

% ---------------------------------------------------------------------------
% unzip_lists(XYs, Xs, Ys): XYs is the list of pairs of the corresponding
% elements of Xs and Ys.

% mode unzip_lists(+, ?, ?).
% mode unzip_lists(?, +, ?).
% mode unzip_lists(?, ?, +).
unzip_lists([], [], []).
unzip_lists([X-Y|XYs], [X|Xs], [Y|Ys]) :-
        unzip_lists(XYs, Xs, Ys).

                %  | ?- zip_lists([a,b], [1,2], XYs).
                %  XYs = [a-1,b-2] ? ;
                %  no
                %  | ?- zip_lists([a,b], [1,2,3], XYs).
                %  no
                %  | ?- zip_lists([a,b], Ys, XYs).
                %  Ys = [_A,_B],
                %  XYs = [a-_A,b-_B] ? ;
                %  no
                %  | ?- unzip_lists([a-1,b-2], Xs, Ys).
                %  Xs = [a,b],
                %  Ys = [1,2] ? ;
                %  no
                %  | ?- length(XYs, 2), unzip_lists(XYs, Xs, Ys).
                %  Xs = [_A,_B],
                %  Ys = [_C,_D],
                %  XYs = [_A-_C,_B-_D] ? ;
                %  no
                %  | ?- unzip_lists(XYs, Xs, Ys).
                %  Xs = [],
                %  Ys = [],
                %  XYs = [] ? ;
                %  Xs = [_A],
                %  Ys = [_B],
                %  XYs = [_A-_B] ? ;
                %  Xs = [_A,_B],
                %  Ys = [_C,_D],
                %  XYs = [_A-_C,_B-_D] ? ;
                %  Xs = [_A,_B,_C],
                %  Ys = [_D,_E,_F],
                %  XYs = [_A-_D,_B-_E,_C-_F] ? ;
                %  Xs = [_A,_B,_C,_D],
                %  Ys = [_E,_F,_G,_H],
                %  XYs = [_A-_E,_B-_F,_C-_G,_D-_H] ? 
                %  yes
                %  
% Notice that zip_lists and unzip_lists have the same meaning, but
% different argument order.  Because most Prolog system use so-called
% _first argument indexing_, zip_lists is better in zipping, and
% unzip_lists is better in unzipping, see below.

                %  | ?- mklist(1000000, _L), 
                %       statistics(runtime, _),                            
                %       zip_lists(_L, _L, _LL),
                %       statistics(runtime, [_,T1]),
                %       zip_lists(_, _, _LL),       % zip used for unzipping
                %       statistics(runtime, [_,T2]),
                %       unzip_lists(_LL, _, _),
                %       statistics(runtime, [_,T3]).
                %  T1 = 250,
                %  T2 = 480,
                %  T3 = 300 ? ;
                %  no