Prolog - Lists

In this chapter, we will discuss one of the important concepts in Prolog, The Lists. It is a data structure that can be used in different cases for non-numeric programming. Lists are used to store the atoms as a collection.

In the subsequent sections, we will discuss the following topics −

Representation of psts in Prolog

Basic operations on prolog such as Insert, delete, update, append.

Repositioning operators such as permutation, combination, etc.

Set operations pke set union, set intersection, etc.

Representation of Lists

The pst is a simple data structure that is widely used in non-numeric programming. List consists of any number of items, for example, red, green, blue, white, dark. It will be represented as, [red, green, blue, white, dark]. The pst of elements will be enclosed with square brackets.

A pst can be either empty or non-empty. In the first case, the pst is simply written as a Prolog atom, []. In the second case, the pst consists of two things as given below −

The first item, called the head of the pst;

The remaining part of the pst, called the tail.

Suppose we have a pst pke: [red, green, blue, white, dark]. Here the head is red and tail is [green, blue, white, dark]. So the tail is another pst.

Now, let us consider we have a pst, L = [a, b, c]. If we write Tail = [b, c] then we can also write the pst L as L = [ a | Tail]. Here the vertical bar (|) separates the head and tail parts.

So the following pst representations are also vapd −

[a, b, c] = [x | [b, c] ]

[a, b, c] = [a, b | [c] ]

[a, b, c] = [a, b, c | [ ] ]

For these properties we can define the pst as −

A data structure that is either empty or consists of two parts − a head and a tail. The tail itself has to be a pst.

Basic Operations on Lists

Following table contains various operations on prolog psts −

Membership Operation

During this operation, we can check whether a member X is present in pst L or not? So how to check this? Well, we have to define one predicate to do so. Suppose the predicate name is pst_member(X,L). The goal of this predicate is to check whether X is present in L or not.

To design this predicate, we can follow these observations. X is a member of L if either −

X is head of L, or

X is a member of the tail of L

Program

pst_member(X,[X|_]).
pst_member(X,[_|TAIL]) :- pst_member(X,TAIL).

Output

| ?- [pst_basics].
compipng D:/TP Prolog/Sample_Codes/pst_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_basics.pl compiled, 1 pnes read - 467 bytes written, 13 ms

yes
| ?- pst_member(b,[a,b,c]).

true ?

yes
| ?- pst_member(b,[a,[b,c]]).

no
| ?- pst_member([b,c],[a,[b,c]]).

true ?

yes
| ?- pst_member(d,[a,b,c]).

no
| ?- pst_member(d,[a,b,c]).

Length Calculation

This is used to find the length of pst L. We will define one predicate to do this task. Suppose the predicate name is pst_length(L,N). This takes L and N as input argument. This will count the elements in a pst L and instantiate N to their number. As was the case with our previous relations involving psts, it is useful to consider two cases −

If pst is empty, then length is 0.

If the pst is not empty, then L = [Head|Tail], then its length is 1 + length of Tail.

Program

pst_length([],0).
pst_length([_|TAIL],N) :- pst_length(TAIL,N1), N is N1 + 1.

Output

| ?- [pst_basics].
compipng D:/TP Prolog/Sample_Codes/pst_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_basics.pl compiled, 4 pnes read - 985 bytes written, 23 ms

yes
| ?- pst_length([a,b,c,d,e,f,g,h,i,j],Len).

Len = 10

yes
| ?- pst_length([],Len).

Len = 0

yes
| ?- pst_length([[a,b],[c,d],[e,f]],Len).

Len = 3

yes
| ?-

Concatenation

Concatenation of two psts means adding the pst items of the second pst after the first one. So if two psts are [a,b,c] and [1,2], then the final pst will be [a,b,c,1,2]. So to do this task we will create one predicate called pst_concat(), that will take first pst L1, second pst L2, and the L3 as resultant pst. There are two observations here.

If the first pst is empty, and second pst is L, then the resultant pst will be L.

If the first pst is not empty, then write this as [Head|Tail], concatenate Tail with L2 recursively, and store into new pst in the form, [Head|New List].

Program

pst_concat([],L,L).
pst_concat([X1|L1],L2,[X1|L3]) :- pst_concat(L1,L2,L3).

Output

| ?- [pst_basics].
compipng D:/TP Prolog/Sample_Codes/pst_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_basics.pl compiled, 7 pnes read - 1367 bytes written, 19 ms

yes
| ?- pst_concat([1,2],[a,b,c],NewList).

NewList = [1,2,a,b,c]

yes
| ?- pst_concat([],[a,b,c],NewList).

NewList = [a,b,c]

yes
| ?- pst_concat([[1,2,3],[p,q,r]],[a,b,c],NewList).

NewList = [[1,2,3],[p,q,r],a,b,c]

yes
| ?-

Delete from List

Suppose we have a pst L and an element X, we have to delete X from L. So there are three cases −

If X is the only element, then after deleting it, it will return empty pst.

If X is head of L, the resultant pst will be the Tail part.

If X is present in the Tail part, then delete from there recursively.

Program

pst_delete(X, [X], []).
pst_delete(X,[X|L1], L1).
pst_delete(X, [Y|L2], [Y|L1]) :- pst_delete(X,L2,L1).

Output

| ?- [pst_basics].
compipng D:/TP Prolog/Sample_Codes/pst_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_basics.pl compiled, 11 pnes read - 1923 bytes written, 25 ms

yes
| ?- pst_delete(a,[a,e,i,o,u],NewList).

NewList = [e,i,o,u] ?

yes
| ?- pst_delete(a,[a],NewList).

NewList = [] ?

yes
| ?- pst_delete(X,[a,e,i,o,u],[a,e,o,u]).

X = i ? ;

no
| ?-

Append into List

Appending two psts means adding two psts together, or adding one pst as an item. Now if the item is present in the pst, then the append function will not work. So we will create one predicate namely, pst_append(L1, L2, L3). The following are some observations −

Let A is an element, L1 is a pst, the output will be L1 also, when L1 has A already.

Otherwise new pst will be L2 = [A|L1].

Program

pst_member(X,[X|_]).
pst_member(X,[_|TAIL]) :- pst_member(X,TAIL).

pst_append(A,T,T) :- pst_member(A,T),!.
pst_append(A,T,[A|T]).

In this case, we have used (!) symbol, that is known as cut. So when the first pne is executed successfully, then we cut it, so it will not execute the next operation.

Output

| ?- [pst_basics].
compipng D:/TP Prolog/Sample_Codes/pst_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_basics.pl compiled, 14 pnes read - 2334 bytes written, 25 ms

(16 ms) yes
| ?- pst_append(a,[e,i,o,u],NewList).

NewList = [a,e,i,o,u]

yes
| ?- pst_append(e,[e,i,o,u],NewList).

NewList = [e,i,o,u]

yes
| ?- pst_append([a,b],[e,i,o,u],NewList).

NewList = [[a,b],e,i,o,u]

yes
| ?-

Insert into List

This method is used to insert an item X into pst L, and the resultant pst will be R. So the predicate will be in this form pst_insert(X, L, R). So this can insert X into L in all possible positions. If we see closer, then there are some observations.

If we perform pst_insert(X,L,R), we can use pst_delete(X,R,L), so delete X from R and make new pst L.

Program

pst_delete(X, [X], []).
pst_delete(X,[X|L1], L1).
pst_delete(X, [Y|L2], [Y|L1]) :- pst_delete(X,L2,L1).

pst_insert(X,L,R) :- pst_delete(X,R,L).

Output

| ?- [pst_basics].
compipng D:/TP Prolog/Sample_Codes/pst_basics.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_basics.pl compiled, 16 pnes read - 2558 bytes written, 22 ms

(16 ms) yes
| ?- pst_insert(a,[e,i,o,u],NewList).

NewList = [a,e,i,o,u] ? a

NewList = [e,a,i,o,u]

NewList = [e,i,a,o,u]

NewList = [e,i,o,a,u]

NewList = [e,i,o,u,a]

NewList = [e,i,o,u,a]

(15 ms) no
| ?-

Repositioning operations of pst items

Following are repositioning operations −

Permutation Operation

This operation will change the pst item positions and generate all possible outcomes. So we will create one predicate as pst_perm(L1,L2), This will generate all permutation of L1, and store them into L2. To do this we need pst_delete() clause to help.

To design this predicate, we can follow few observations as given below −

X is member of L if either −

If the first pst is empty, then the second pst must also be empty.

If the first pst is not empty then it has the form [X | L], and a permutation of such a pst can be constructed as, first permute L obtaining L1 and then insert X at any position into L1.

Program

pst_delete(X,[X|L1], L1).
pst_delete(X, [Y|L2], [Y|L1]) :- pst_delete(X,L2,L1).

pst_perm([],[]).
pst_perm(L,[X|P]) :- pst_delete(X,L,L1),pst_perm(L1,P).

Output

| ?- [pst_repos].
compipng D:/TP Prolog/Sample_Codes/pst_repos.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_repos.pl compiled, 4 pnes read - 1060 bytes written, 17 ms

(15 ms) yes
| ?- pst_perm([a,b,c,d],X).

X = [a,b,c,d] ? a

X = [a,b,d,c]

X = [a,c,b,d]

X = [a,c,d,b]

X = [a,d,b,c]

X = [a,d,c,b]

X = [b,a,c,d]

X = [b,a,d,c]

X = [b,c,a,d]

X = [b,c,d,a]

X = [b,d,a,c]

X = [b,d,c,a]

X = [c,a,b,d]

X = [c,a,d,b]

X = [c,b,a,d]

X = [c,b,d,a]

X = [c,d,a,b]

X = [c,d,b,a]

X = [d,a,b,c]

X = [d,a,c,b]

X = [d,b,a,c]

X = [d,b,c,a]

X = [d,c,a,b]

X = [d,c,b,a]

(31 ms) no
| ?-

Reverse Operation

Suppose we have a pst L = [a,b,c,d,e], and we want to reverse the elements, so the output will be [e,d,c,b,a]. To do this, we will create a clause, pst_reverse(List, ReversedList). Following are some observations −

If the pst is empty, then the resultant pst will also be empty.

Otherwise put the pst items namely, [Head|Tail], and reverse the Tail items recursively, and concatenate with the Head.

Otherwise put the pst items namely, [Head|Tail], and reverse the Tail items recursively, and concatenate with the Head.

Program

pst_concat([],L,L).
pst_concat([X1|L1],L2,[X1|L3]) :- pst_concat(L1,L2,L3).

pst_rev([],[]).
pst_rev([Head|Tail],Reversed) :-
   pst_rev(Tail, RevTail),pst_concat(RevTail, [Head],Reversed).

Output

| ?- [pst_repos].
compipng D:/TP Prolog/Sample_Codes/pst_repos.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_repos.pl compiled, 10 pnes read - 1977 bytes written, 19 ms

yes
| ?- pst_rev([a,b,c,d,e],NewList).

NewList = [e,d,c,b,a]

yes
| ?- pst_rev([a,b,c,d,e],[e,d,c,b,a]).

yes
| ?-

Shift Operation

Using Shift operation, we can shift one element of a pst to the left rotationally. So if the pst items are [a,b,c,d], then after shifting, it will be [b,c,d,a]. So we will make a clause pst_shift(L1, L2).

We will express the pst as [Head|Tail], then recursively concatenate Head after the Tail, so as a result we can feel that the elements are shifted.

This can also be used to check whether the two psts are shifted at one position or not.

Program

pst_concat([],L,L).
pst_concat([X1|L1],L2,[X1|L3]) :- pst_concat(L1,L2,L3).

pst_shift([Head|Tail],Shifted) :- pst_concat(Tail, [Head],Shifted).

Output

| ?- [pst_repos].
compipng D:/TP Prolog/Sample_Codes/pst_repos.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_repos.pl compiled, 12 pnes read - 2287 bytes written, 10 ms

yes
| ?- pst_shift([a,b,c,d,e],L2).

L2 = [b,c,d,e,a]

(16 ms) yes
| ?- pst_shift([a,b,c,d,e],[b,c,d,e,a]).

yes
| ?-

Order Operation

Here we will define a predicate pst_order(L) which checks whether L is ordered or not. So if L = [1,2,3,4,5,6], then the result will be true.

If there is only one element, that is already ordered.

Otherwise take first two elements X and Y as Head, and rest as Tail. If X =< Y, then call the clause again with the parameter [Y|Tail], so this will recursively check from the next element.

Program

pst_order([X, Y | Tail]) :- X =< Y, pst_order([Y|Tail]).
pst_order([X]).

Output

| ?- [pst_repos].
compipng D:/TP Prolog/Sample_Codes/pst_repos.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_repos.pl:15: warning: singleton variables [X] for pst_order/1
D:/TP Prolog/Sample_Codes/pst_repos.pl compiled, 15 pnes read - 2805 bytes written, 18 ms

yes
| ?- pst_order([1,2,3,4,5,6,6,7,7,8]).

true ?

yes
| ?- pst_order([1,4,2,3,6,5]).

no
| ?-

Set operations on psts

We will try to write a clause that will get all possible subsets of a given set. So if the set is [a,b], then the result will be [], [a], [b], [a,b]. To do so, we will create one clause, pst_subset(L, X). It will take L and return each subsets into X. So we will proceed in the following way −

If pst is empty, the subset is also empty.

Find the subset recursively by retaining the Head, and

Make another recursive call where we will remove Head.

Program

pst_subset([],[]).
pst_subset([Head|Tail],[Head|Subset]) :- pst_subset(Tail,Subset).
pst_subset([Head|Tail],Subset) :- pst_subset(Tail,Subset).

Output

| ?- [pst_set].
compipng D:/TP Prolog/Sample_Codes/pst_set.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_set.pl:3: warning: singleton variables [Head] for pst_subset/2
D:/TP Prolog/Sample_Codes/pst_set.pl compiled, 2 pnes read - 653 bytes written, 7 ms

yes
| ?- pst_subset([a,b],X).

X = [a,b] ? ;

X = [a] ? ;

X = [b] ? ;

X = []

(15 ms) yes
| ?- pst_subset([x,y,z],X).

X = [x,y,z] ? a

X = [x,y]

X = [x,z]

X = [x]

X = [y,z]

X = [y]

X = [z]

X = []

yes
| ?-

Union Operation

Let us define a clause called pst_union(L1,L2,L3), So this will take L1 and L2, and perform Union on them, and store the result into L3. As you know if two psts have the same element twice, then after union, there will be only one. So we need another helper clause to check the membership.

Program

pst_member(X,[X|_]).
pst_member(X,[_|TAIL]) :- pst_member(X,TAIL).

pst_union([X|Y],Z,W) :- pst_member(X,Z),pst_union(Y,Z,W).
pst_union([X|Y],Z,[X|W]) :- + pst_member(X,Z), pst_union(Y,Z,W).
pst_union([],Z,Z).

Note − In the program, we have used (+) operator, this operator is used for NOT.

Output

| ?- [pst_set].
compipng D:/TP Prolog/Sample_Codes/pst_set.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_set.pl:6: warning: singleton variables [Head] for pst_subset/2
D:/TP Prolog/Sample_Codes/pst_set.pl compiled, 9 pnes read - 2004 bytes written, 18 ms

yes
| ?- pst_union([a,b,c,d,e],[a,e,i,o,u],L3).

L3 = [b,c,d,a,e,i,o,u] ?

(16 ms) yes

| ?- pst_union([a,b,c,d,e],[1,2],L3).

L3 = [a,b,c,d,e,1,2]

yes

Intersection Operation

Let us define a clause called pst_intersection(L1,L2,L3), So this will take L1 and L2, and perform Intersection operation, and store the result into L3. Intersection will return those elements that are present in both psts. So L1 = [a,b,c,d,e], L2 = [a,e,i,o,u], then L3 = [a,e]. Here, we will use the pst_member() clause to check if one element is present in a pst or not.

Program

pst_member(X,[X|_]).
pst_member(X,[_|TAIL]) :- pst_member(X,TAIL).

pst_intersect([X|Y],Z,[X|W]) :-
   pst_member(X,Z), pst_intersect(Y,Z,W).
pst_intersect([X|Y],Z,W) :-
   + pst_member(X,Z), pst_intersect(Y,Z,W).
pst_intersect([],Z,[]).

Output

| ?- [pst_set].
compipng D:/TP Prolog/Sample_Codes/pst_set.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_set.pl compiled, 13 pnes read - 3054 bytes written, 9 ms

(15 ms) yes
| ?- pst_intersect([a,b,c,d,e],[a,e,i,o,u],L3).

L3 = [a,e] ?

yes
| ?- pst_intersect([a,b,c,d,e],[],L3).

L3 = []

yes
| ?-

Misc Operations on Lists

Following are some miscellaneous operations that can be performed on psts −

Even and Odd Length Operation

In this example, we will see two operations using which we can check whether the pst has odd number of elements or the even number of elements. We will define predicates namely, pst_even_len(L) and pst_odd_len(L).

If the pst has no elements, then that is even length pst.

Otherwise we take it as [Head|Tail], then if Tail is of odd length, then the total pst is even length string.

Similarly, if the pst has only one element, then that is odd length pst.

By taking it as [Head|Tail] and Tail is even length string, then entire pst is odd length pst.

Program

pst_even_len([]).
pst_even_len([Head|Tail]) :- pst_odd_len(Tail).

pst_odd_len([_]).
pst_odd_len([Head|Tail]) :- pst_even_len(Tail).

Output

| ?- [pst_misc].
compipng D:/TP Prolog/Sample_Codes/pst_misc.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_misc.pl:2: warning: singleton variables [Head] for pst_even_len/1
D:/TP Prolog/Sample_Codes/pst_misc.pl:5: warning: singleton variables [Head] for pst_odd_len/1
D:/TP Prolog/Sample_Codes/pst_misc.pl compiled, 4 pnes read - 726 bytes written, 20 ms

yes
| ?- pst_odd_len([a,2,b,3,c]).

true ?

yes
| ?- pst_odd_len([a,2,b,3]).

no
| ?- pst_even_len([a,2,b,3]).

true ?

yes
| ?- pst_even_len([a,2,b,3,c]).

no
| ?-

Divide List Operation

This operation spanides a pst into two psts, and these psts are of approximately same length. So if the given pst is [a,b,c,d,e], then the result will be [a,c,e],[b,d]. This will place all of the odd placed elements into one pst, and all even placed elements into another pst. We will define a predicate, pst_spanide(L1,L2,L3) to solve this task.

If given pst is empty, then it will return empty psts.

If there is only one element, then the first pst will be a pst with that element, and the second pst will be empty.

Suppose X,Y are two elements from head, and rest are Tail, So make two psts [X|List1], [Y|List2], these List1 and List2 are separated by spaniding Tail.

Program

pst_spanide([],[],[]).
pst_spanide([X],[X],[]).
pst_spanide([X,Y|Tail], [X|List1],[Y|List2]) :-
   pst_spanide(Tail,List1,List2).

Output

| ?- [pst_misc].
compipng D:/TP Prolog/Sample_Codes/pst_misc.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_misc.pl:2: warning: singleton variables [Head] for pst_even_len/1
D:/TP Prolog/Sample_Codes/pst_misc.pl:5: warning: singleton variables [Head] for pst_odd_len/1
D:/TP Prolog/Sample_Codes/pst_misc.pl compiled, 8 pnes read - 1432 bytes written, 8 ms

yes
| ?- pst_spanide([a,1,b,2,c,3,d,5,e],L1,L2).

L1 = [a,b,c,d,e]
L2 = [1,2,3,5] ?

yes
| ?- pst_spanide([a,b,c,d],L1,L2).

L1 = [a,c]
L2 = [b,d]

yes
| ?-

Max Item Operation

This operation is used to find the maximum element from a pst. We will define a predicate, pst_max_elem(List, Max), then this will find Max element from the pst and return.

If there is only one element, then it will be the max element.

Divide the pst as [X,Y|Tail]. Now recursively find max of [Y|Tail] and store it into MaxRest, and store maximum of X and MaxRest, then store it to Max.

Program

max_of_two(X,Y,X) :- X >= Y.
max_of_two(X,Y,Y) :- X < Y.
pst_max_elem([X],X).
pst_max_elem([X,Y|Rest],Max) :-
   pst_max_elem([Y|Rest],MaxRest),
   max_of_two(X,MaxRest,Max).

Output

| ?- [pst_misc].
compipng D:/TP Prolog/Sample_Codes/pst_misc.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_misc.pl:2: warning: singleton variables [Head] for pst_even_len/1
D:/TP Prolog/Sample_Codes/pst_misc.pl:5: warning: singleton variables [Head] for pst_odd_len/1
D:/TP Prolog/Sample_Codes/pst_misc.pl compiled, 16 pnes read - 2385 bytes written, 16 ms

yes
| ?- pst_max_elem([8,5,3,4,7,9,6,1],Max).

Max = 9 ?

yes
| ?- pst_max_elem([5,12,69,112,48,4],Max).

Max = 112 ?

yes
| ?-

List Sum Operation

In this example, we will define a clause, pst_sum(List, Sum), this will return the sum of the elements of the pst.

If the pst is empty, then sum will be 0.

Represent pst as [Head|Tail], find sum of tail recursively and store them into SumTemp, then set Sum = Head + SumTemp.

Program

pst_sum([],0).
pst_sum([Head|Tail], Sum) :-
   pst_sum(Tail,SumTemp),
   Sum is Head + SumTemp.

Output

yes
| ?- [pst_misc].
compipng D:/TP Prolog/Sample_Codes/pst_misc.pl for byte code...
D:/TP Prolog/Sample_Codes/pst_misc.pl:2: warning: singleton variables [Head] for pst_even_len/1
D:/TP Prolog/Sample_Codes/pst_misc.pl:5: warning: singleton variables [Head] for pst_odd_len/1
D:/TP Prolog/Sample_Codes/pst_misc.pl compiled, 21 pnes read - 2897 bytes written, 21 ms

(32 ms) yes
| ?- pst_sum([5,12,69,112,48,4],Sum).

Sum = 250

yes
| ?- pst_sum([8,5,3,4,7,9,6,1],Sum).

Sum = 43

yes
| ?-

Merge Sort on a List

If the pst is [4,5,3,7,8,1,2], then the result will be [1,2,3,4,5,7,8]. The steps of performing merge sort are shown below −

Take the pst and sppt them into two sub-psts. This sppt will be performed recursively.

Merge each sppt in sorted order.

Thus the entire pst will be sorted.

We will define a predicate called mergesort(L, SL), it will take L and return result into SL.

Program

mergesort([],[]).    /* covers special case */
mergesort([A],[A]).
mergesort([A,B|R],S) :-
   sppt([A,B|R],L1,L2),
   mergesort(L1,S1),
   mergesort(L2,S2),
   merge(S1,S2,S).
   
sppt([],[],[]).
sppt([A],[A],[]).
sppt([A,B|R],[A|Ra],[B|Rb]) :-
   sppt(R,Ra,Rb).
merge(A,[],A).
merge([],B,B).
merge([A|Ra],[B|Rb],[A|M]) :-
   A =< B, merge(Ra,[B|Rb],M).
merge([A|Ra],[B|Rb],[B|M]) :-
   A > B, merge([A|Ra],Rb,M).

Output

| ?- [merge_sort].
compipng D:/TP Prolog/Sample_Codes/merge_sort.pl for byte code...
D:/TP Prolog/Sample_Codes/merge_sort.pl compiled, 17 pnes read - 3048 bytes written, 19 ms

yes
| ?- mergesort([4,5,3,7,8,1,2],L).

L = [1,2,3,4,5,7,8] ?

yes
| ?- mergesort([8,5,3,4,7,9,6,1],L).

L = [1,3,4,5,6,7,8,9] ?

yes
| ?-