% =========================================================================== % Deklaratív Programozás 2. gyakorlat, Prolog listakezelő eljárások % =========================================================================== % Examples of list handling predicates :- use_module(library(lists)). % Example 1: Inserting an element into a list % =========================================== % --------------------------------------------------------------- % 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 % | ?- % :- 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), append(L1, [E|L2], L), length(L1, N1), N is N1+1. % | ?- 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), append(L1, L2, L0), length(L1, N1), N is N1+1. % | ?- 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= Value = V1 ; key_map_value_4(Key, Map, Value) ). % Version 4 is usable only when the Key argument is instantiated. It stops % scanning the list as soon as the given Key is found. % :- mode key_map_value_5(?, +, ?). key_map_value_5(Key, [K1-V1|Map], Value) :- ( Key = K1, Value = V1 -> true ; key_map_value_5(Key, Map, Value) ). % :- mode key_map_value_6(?, +, ?). key_map_value_6(Key, Map, Value) :- ( member(Key-Value, Map) -> true ). % :- mode key_map_value_7(+, +, ?). key_map_value_7(Key, Map, Value) :- memberchk(Key-Value, Map). % Versions 5, 6, and 7 are equivalent. These return at most one solution. % | ?- key_map_value_1(1, [1-a,2-b,3-a], V). % V = a ? ; % no % | ?- key_map_value_1(3, [1-a,2-b,3-a], V). % V = a ? ; % no % | ?- key_map_value_1(K, [1-a,2-b,3-a], a). % K = 1 ? ; % K = 3 ? ; % no % | ?- key_map_value_1(K, [1-a,2-b,3-a], b). % K = 2 ? ; % no % | ?- key_map_value_1(K, [1-a,2-b,3-a], V). % K = 1, % V = a ? ; % K = 2, % V = b ? ; % K = 3, % V = a ? ; % no % | ?- key_map_value_4(3, [1-a,2-b,3-a], V). % V = a ? ; % no % | ?- key_map_value_4(K, [1-a,2-b,3-a], a). % K = 1 ? ; % no % | ?- key_map_value_4(K, [1-a,2-b,3-a], b). % no % | ?- key_map_value_4(K, [1-a,2-b,3-a], V). % K = 1, % V = a ? ; % no % | ?- key_map_value_5(3, [1-a,2-b,3-a], V). % V = a ? ; % no % | ?- key_map_value_5(K, [1-a,2-b,3-a], a). % K = 1 ? ; % no % | ?- key_map_value_5(K, [1-a,2-b,3-a], b). % K = 2 ? ; % no % | ?- key_map_value_5(K, [1-a,2-b,3-a], V). % K = 1, % V = a ? ; % no % Example 3: Splitting a list % =========================== % --------------------------------------------------------------------------- % 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. % Example set 5: Various list utilities % ===================================== % --------------------------------------------------------------------------- % 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 % --------------------------------------------------------------------------- % 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.6 % ================= % % Produce efficient versions of nth_elem for mode (+,?,?), by specialising % the code of % % (a) split_list_1 % (b) split_list_2 % --------------------------------------------------------------------------- % 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.7 % ================= % 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. % Example set 6: Matrix operations % ================================ % A matrix is represented as a list of rows, each row being a list of elements. % --------------------------------------------------------------------------- % matrix_elem(RowI, ClmI, Matrix, Elem): Elem is the element of % matrix Matrix appearing in row number RowI and column number ClmI. matrix_elem(RowI, ClmI, Matrix, Elem) :- nth(RowI, Matrix, Row), nth(ClmI, Row, Elem). % matrix_row(RowI, Matrix, Row): Row is RowI-th row of matrix Matrix. matrix_row(RowI, Matrix, Row) :- nth(RowI, Matrix, Row). % matrix_column(ClmI, Matrix, Clm): Clm is ClmI-th column of matrix Matrix. matrix_column(_, [], []). matrix_column(I, [Row|Rows], [XI|XIs]) :- nth(I, Row, XI), matrix_column(I, Rows, XIs). % matrix_block(RowI, ClmI, RowS, ClmS, Matrix, Block): % Block is a list of elements in the submatrix of Matrix % whose upper left corner is at (RowI, ClmI) and whose size % is (RowS, ClmS). matrix_block(RowI, ClmI, RowS, ClmS, Matrix, Block) :- sublist(Matrix, RowI, RowS, SubMatrix), matrix_columns(ClmI, ClmS, SubMatrix, Block). % matrix_columns(ClmI, ClmS, Matrix, Block) matrix_columns(_, _, [], []). matrix_columns(ClmI, ClmS, [Row|Rows], [SR|SRs]) :- sublist(Row, ClmI, ClmS, SR), matrix_columns(ClmI, ClmS, Rows, SRs). % | ?- matrix_elem(2, 1, [[a,b],[c,d]], E). % E = c ? ; % no % | ?- matrix_row(2, [[a,b],[c,d]], R). % R = [c,d] ? ; % no % | ?- matrix_column(2, [[a,b],[c,d]], C). % C = [b,d] ? ; % no % | ?- matrix_block(2, 1, 1, 2, [[a,b],[c,d]], B). % B = [[c,d]] ? ; % no % | ?- matrix_block(2, 1, 2, 2, [[a,b,c],[d,e,f],[g,h,i]], B). % B = [[d,e],[g,h]] ? ; % no