List in Prolog

It is important for any programming tool to have some functionality of handling collections like array, list or something else. Prolog use lists for the very purpose and I must warn C/C++ programmers (or even Java, C# or any other C-like language fan) that lists are not arrays but similar to it.

A list must be declared as list type in domains section or in predicate section, it should be mentioned that we are using list.

In domains section, we do it by declaring a new domain and equaling it to a list type, declared by name of type followed by an asterisk; e.g.:

numList=integer*

if one like to avoid domain section, but use list it should be mentioned in predicate section like this:

somePredicate(integer*)

A list is presented as a comma-separated bracket closed tuple of same type:

[a,b,c,]

[1,15,2,100,11,12,19]

[“Car”,“House”,”pen”,”tree”,”Etc”]

List is not random access container but can be accessed in sequence. First element of a list can be accessed in kind of weird way:

[Head|Tail]

If we pass a list there, Head will contain the first element while Tail contains another list excluding the first elemetn. Hence, we need to write some extra lines of code to access nth element.

I would like to avoid further explanation, which you can find a lot in the internet, but will go forward to placing an example code:

/*nafSadh.org*/
/*Example code on LIST in Prolog*/
domains

numList=integer*
key,index,element,minimum,maximum,sum,count=integer
average=real

predicates

/*Traverse list*/
trav(numList)
/*Search an element in the list*/
search(numList,key,index)
search(numList,key)
/*Get the last element of list*/
last(numList,element)
last(numList)
/*Get nth element of list*/
nth(numList,index)
/*get the minimum valued element out of list*/
min(numList)
min(numList,minimum)
/*get the maximum valued element out of list*/
max(numList,maximum)
max(numList)
/*find the average value of elements in list*/
avg(numList)
avg(numList,average)
avg(numList,sum,count)

clauses

/*TRAV*/
trav([]):-
nl.
trav([H|Tail]):-
write(H,”,”),trav(Tail).

/*SEARCH*/
search(List,Key):-
search(List,Key,1).
search([],_,_):-
write(“Not Found”),nl.

search([H|_],Key,I):-
H=Key,write(“Found at “,I),nl.

search([_|T],Key,I):-
II=I+1,search(T,Key,II).

/*LAST*/
last(List):-
last(List,E),write(E),nl.

last([Head],E):-
E=Head.
last([_|Tail],E):-
last(Tail,E).

/*NTH ELEM*/
nth([],_):-
write(“overflow”),nl.

nth([Head|_],I):-
I=1,write(Head),nl.

nth([_|Tlist],I):-
II=I-1,nth(Tlist,II).

/*MIN*/
min([H|T]):-
min(T,H).
min([],Min):-
write(Min),nl.
min([H|T],Min):-
H<Min,M1n=H,min(T,M1n).
min([_|T],Min):-
min(T,Min).

/*MAX*/
max([H|T]):-
max(T,H).
max([],Max):-
write(Max),nl.
max([H|T],Max):-
H>Max,M4x=H,max(T,M4x).
max([_|T],Max):-
max(T,Max).

/*AVG*/
avg([]):-
write(“Empty List”),nl.
avg(List):-
avg(List,Avg),write(Avg),nl.
avg(List,Avg):-
avg(List,Sum,C),Avg=Sum/C.
avg([H],Sum,C):-
Sum=H,C=1.
avg([H|T],Sum,C):-
avg(T,S,Count),Sum=S+H,C=Count+1.

Happy Prolog!

Unlike some of my fellow bloggers, I hold pure authorship to the codes placed here and these codes have never been cut pasted from some other site or plagiarized from any fellow student. Being frightened by some web publisher, I hereby have to claim my copyright on elements presented here.

All elements published here are published under NS7 Open Content License, which express that,

  • if anyone use the content, partial or full in any context, s/he shall must mention the source and refer to the hyperlink
  • any code under this license must not be published in any media unless modified significantly and that modification executes well enough without harm and credit to actual author is mentioned
  • if anyone need to use code, published under this license,  as example s/he can do it by mentioning actual author and shall not host a source file but refer to the original one, with another hyperlink to content accompanying, if accompanies one, the very code. As this code shall be used as example, content text should be relevant and example code should not be more than 40% of total content.
  • Mentions to authors of codes and contents under this license must be in a good manner. Mention should be in same font of normal text of the content used in, font size should be of same size or larger than normal text of the content but in any case minimum size in electronic media is 12px or 11pt in print media. Normal text is regarded as that kind of text that comprises of a minimum of 70% of total content.
  • contents presented here can be used for personal and academic purpose without any mention but shall not be published without taking proper permission from actual author

Prolog program to find GCDs and LCMs

The least common multiple (LCM) of two integers a, b is the smallest positive integer that is a multiple of both a and b.

Despite of the fact, there exist several formulas to calculate the LCM of two integers, most popular formula, especially to the programmers, is by using GCD of the two:

LCM(a, b) = a*b/ GCD(a,b)

Therefore, we need to focus on calculating GCD before we do LCM.

Greatest Common Divisor (gcd) of two or more non-zero integers is the largest positive integer that divides the numbers without a remainder.

For sake of simplicity, we will reduce GCD function to take two arguments in decreasing order, i.e. a>=b.

Now only for the users ease, we will handle the opposite case (a<b) by swapping the arguments and calling GCD(b,a).

Other cases to be handled, include, a=b, b=0 and a<b.

  • if a=b, then GCD is also same (b).
  • If b=0, (here it is the base case of recursion), GCD is a
  • Else, GCD(a,b)=GCD(b,c), where c=a modulo b

To handle predicates with care, we use two type of gcd,

  1. with 2 arguments, the input numbers
  2. with 3 arguments, 2 inputs and one result (GCD)

Likewise, lcm also has two overloads for the same reason.

Henceforth, I may hereby present a code devised for the very course by the lazy brain of mine below:

domains

num,result=integer

predicates

lcm(num,num)
lcm(num,num,result)
gcd(num,num)
gcd(num,num,result)

clauses

lcm(X1,X2):-
lcm(X1,X2,Y),write(Y),nl.
lcm(X1,X2,Y):-
gcd(X1,X2,Y1),Y=X1*X2/Y1.

gcd(X1,X2):-
gcd(X1,X2,Y),write(Y),nl.

gcd(X1,0,Y):-
Y=X1.

gcd(X1,X2,Y):-
X1=X2,Y=X2.

gcd(X1,X2,Y):-
X1<X2,gcd(X2,X1,Y).

gcd(X1,X2,Y):-
X3=X1 mod X2, gcd(X2,X3,Y).

Happy Prolog!

Prolog program to Calculate factorial of N

We know the formula for calculating n! (factorial of n)  is:

n! = n * (n-1)!

We can interpret this simple mathematical equation into a Prolog program. To do so, we must determine the basis of the recursion,

0! = 1

We will use two predicates here,

  1. factorial predicate with one argument N, that will calculate and N!
  2. factorial predicate with two arguments N and X. This function is recursively used. It will also calculate N!, but store it in the argument X in the process if recursion.

Code snippet given below is a sample program for the purpose.

predicates

factorial(integer,integer)
factorial(integer)

clauses

/* Base Case, 0!=1*/
factorial(0,X):-
X=1.
/* recursion for factorial */
factorial(N,X):-
NN=N-1,
factorial(NN,X1),
X=X1*N.
/*One argument function*/
factorial(N):-
factorial(N,X),
write(X).

Hope you will enjoy!