Adasddaasdsdasadasd

P ROLOG. Lists in P ROLOG. Advanced Issues. List Ordering. Meta Predicates.
Antoni Lig˛ za e
Katedra Automatyki, AGH w Krakowie

2011

Antoni Lig˛ za e

Prolog

1/22

References

[1] Ulf Nilsson, Jan Maluszy´ ski: Logic, Programming and Prolog, John Wiley & n Sons Ltd., pdf, http://www.ida.liu.se/ ulfni/lpp [2] Dennis Merritt: Adventure in Prolog, Amzi, 2004http://www.amzi.com/AdventureInProlog [3] Quick Prolog: http://www.dai.ed.ac.uk/groups/ssp/bookpages/quickprolog/quickprolog.html [4] W. F. Clocksin, C. S. Mellish: Prolog. Programowanie. Helion, 2003 [5] SWI-Prolog’s home: http://www.swi-prolog.org [6] Learn Prolog Now!: http://www.learnprolognow.org [7] http://home.agh.edu.pl/ ligeza/wiki/prolog [8] http://www.im.pwr.wroc.pl/ przemko/prolog

Antoni Lig˛ za eProlog

2/22

List Ordering — Sorting by Insertion
The idea of sorting by insertion In order to sort a list:
1 2

check if the list is empty; an empty list is sorted, if the list is not empty, then:
1 2 3

take of the Head, sort the Tail, insert Head into an appropriate place of Tail.

Insert sort
1 2 3 4 5 6 7 8 9 10

order([],[]). order([H|T],R):order(T,TR), put(H,TR,R).put(H,[],[H]):-!. put(H,[X|Y],[H,X|Y]):H < X,!. put(H,[X|Y],[X|Z]):put(H,Y,Z),!.

Antoni Lig˛ za e

Prolog

3/22

Sorting by Minimum/Maximum
Sorting by finding minimal/maximal element
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

min([X],X):-!. min([P|R],P):- min(R,X),X > P,!. min([P|R],X):- min(R,X),X =< P. max([X],X):-!. max([P|R],P):- max(R,X),X =< P,!. max([P|R],X):- max(R,X),X >P. min-sort([],[]):- !. min-sort(L,[M|LS]):min(L,M), select(M,L,LM), min-sort(LM,LS). min-sort-iter(L,LS):msi(L,[],LS). msi([],LS,LS):- !. msi(L,LA,LS):max(L,M), select(M,L,LM),!, msi(LM,[M|LA],LS).

Antoni Lig˛ za e

Prolog

4/22

Bubblesort
Idea of bubblesort
1 2 3

scan by pairs of elements from left to right, if the order is wrong — correct; continue the scan, if no correctiontakes place, the list is sorted.

Bubblesort
1 2 3 4 5 6

busort(L,S):swap(L,LS), !, busort(LS,S). busort(S,S). swap([X,Y|T],[Y,X|T]):- X > Y. swap([Z|T],[Z|TT]):- swap(T,TT).

Bubblesort 2a
1 2 3 4

busort2a(L,S):append(F,[X,Y|T],L), X>Y, !, append(F,[Y,X|T],NL), busort2a(NL,S). busort2a(S,S).

Antoni Lig˛ za e

Prolog

5/22

Mergesort
Mergesort: split, sort, merge
1 2 3 4 5 6 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22

lse([],W1,W2,W1,W2,_):- !. lse([H|T],L1,L2,W1,W2,l):- lse(T,[H|L1],L2,W1,W2,p), !. lse([H|T],L1,L2,W1,W2,p):- lse(T,L1,[H|L2],W1,W2,l), !. split([],[],[]). split([H|T],[H|U],V):- split(T,V,U). merge([H1|T1],[H2|T2],[H1|T]):H1 < H2, !, merge(T1,[H2|T2],T). merge([H1|T1],[H2|T2],[H2|T]):merge([H1|T1],T2,T),!. merge(X,[],X):-!. merge([],X,X).mergesort([],[]):- !. mergesort([H],[H]):- !. mergesort(L,S):split(L,LL,LR), mergesort(LL,SLL), mergesort(LR,SLR), merge(SLL,SLR,S).

Antoni Lig˛ za e

Prolog

6/22

Quicksort
Idea of quicksort
1 2 3 4

select an arbitrary threshold element, split the list into smaller elements, and bigger elements, sort both the lists, append the lists, including threshold element inside.

Quicksort
1 2 3 45 6 7 8 9 10 11 12 13

qsort([],[]). qsort([H|T],S):split(H,T,L,R), qsort(L,LS), qsort(R,RS), append(LS,[H|RS],S). split(_,[],[],[]). split(H,[A|X],[A|Y],Z):A =< H, !, split(H,X,Y,Z). split(H,[A|X],Y,[A|Z]):A > H, !, split(H,X,Y,Z).

Antoni Lig˛ za e

Prolog

7/22

Loops-repeat-fail
Example loop solutions
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22loop_infinite:repeat, write(’***loop: fail.

’),nl,

loop_infinite_read_write:repeat, read(X), write(’***loop: fail.

’), write(X),nl,

loop_find_fail:d(X), write(’***found: ’),write(X),nl, fail. loop_find_fail. loop_repeat_test:repeat, d(X), write(’***found: ’),write(X),nl, read(Y), X = Y, write(’***end: ’),write(X),nl. d(0). d(1). d(2). d(3). d(4). d(5). d(6). d(7). d(8). d(9).

Antoni Lig˛ za e...