- Prolog - Discussion
- Prolog - Useful Resources
- Prolog - Quick Guide
- Monkey and Banana Problem
- Prolog - Linked Lists
- Towers of Hanoi Problem
- Prolog - Examples of Cuts
- Prolog - Basic Programs
- Tree Data Structure (Case Study)
- Prolog - Built-In Predicates
- Prolog - Inputs and Outputs
- Prolog - Different and Not
- Prolog - Backtracking
- Recursion and Structures
- Prolog - Lists
- Conjunctions & Disjunctions
- Loop & Decision Making
- Prolog - Operators
- Prolog - Data Objects
- Prolog - Relations
- Prolog - Basics
- Prolog - Hello World
- Prolog - Environment Setup
- Prolog - Introduction
- Prolog - Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
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 −
Operations | Definition |
---|---|
Membership Checking | During this operation, we can verify whether a given element is member of specified pst or not? |
Length Calculation | With this operation, we can find the length of a pst. |
Concatenation | Concatenation is an operation which is used to join/add two psts. |
Delete Items | This operation removes the specified element from a pst. |
Append Items | Append operation adds one pst into another (as an item). |
Insert Items | This operation inserts a given item into a pst. |
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 −
Repositioning Operations | Definition |
---|---|
Permutation | This operation will change the pst item positions and generate all possible outcomes. |
Reverse Items | This operation arranges the items of a pst in reverse order. |
Shift Items | This operation will shift one element of a pst to the left rotationally. |
Order Items | This operation verifies whether the given pst is ordered or not. |
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 −
Misc Operations | Definition |
---|---|
Even and Odd Length Finding | Verifies whether the pst has odd number or even number of elements. |
Divide | Divides a pst into two psts, and these psts are of approximately same length. |
Max | Retrieves the element with maximum value from the given pst. |
Sum | Returns the sum of elements of the given pst. |
Merge Sort | Arranges the elements of a given pst in order (using Merge Sort algorithm). |
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 | ?-Advertisements