Project Description
Prolog Arithmetic and Operators
a) Write a predicate to determine if a given integer is prime or not.
You do not need to worry about efficiency for this question. There are many sophisticated ways to find prime numbers but a simple brute force check will suffice.
?- prime(2). true. ?- prime(4). false. ?- prime(7). true. ?- prime(987). false. ?- prime(997). true. b) Write a predicate that finds the greatest common divisor of two positive integers.
Hint: Use Euclid’s algorithm. ?- gcd(6, 12, D). D = 6. ?- gcd(14, 21, D). D = 7. ?- gcd(1071, 462, D). D = 21. c) Write an infix operator =>> that returns true if one of its operands is double the other operand.
?- 40 =>> 20. true. ?- (-4) =>> (-8). true. ?- 1 =>> 0. false. ?- 3 =>> 7. false. d) Write a unary prefix operator isSingleton that determines if a list has exactly one element in it.
?- isSingleton []. false. ?- isSingleton [8]. true. ?- isSingleton [a,b]. false. e) Write two predicates isort and msort that sort a list of integers. The predicate isort should use the insertion sort method; this method starts with an empty list and inserts items one at a time into the correct position. The predicate msort should use the merge sort method. Merge sort splits a list into two halves, recursively sorts each half and then merges them back together. You should expect to write a number of support predicates for this question. ?- isort([7,3,5,4,1,2,6],[1,2,3,4,5,6,7]). true. ?- isort([7,3,5,4,1,2,6],I). I = [1, 2, 3, 4, 5, 6, 7]. ?- msort([4,5,3,2,2], M). M = [2, 2, 3, 4, 5].
2)You must put the following comments at the top of your program code and provide the appropriate information.
% Assignment number, 159.202, 2016 S2 % Family Name, Given Name, Student ID, % Explain what the program is doing . . . Hand-in: Submit your script electronically through stream
% Assignment number, 159.202, 2016 S2
% Family Name, Given Name, Student ID,
% Check if the number is prime
prime(X) :-
X \= 1, X \= 0,
X1 is X – 1,
prime(X, X1).
prime(_X, 1).
prime(_X, 0).
prime(X, N) :-
Mod is X mod N,
Mod \= 0,
N1 is N – 1,
prime(X, N1).
% test
:- include(prime, [1,2,3,4,5,6,7,8,9, 10,11,12,13,14,15,16,17,18,19,20], Xs)
, Xs = [2, 3, 5, 7, 11, 13, 17, 19].
% find greatest common divisor
gcd(A, A, A).
gcd(A, B, D) :-
A > B,
A1 is A – B,
gcd(A1, B, D).
gcd(A, B, D) :-
A < B,
B1 is B – A,
gcd(A, B1, D).
:- gcd(6, 12, 6).
:- gcd(14, 21, 7).
:- gcd(1071, 462, 21).
:- op(500, xfx, =>>).
% Check if one arg is twice as big as another
X =>> Y :-
X is Y * 2.
X =>> Y :-
Y is X * 2.
:- 40 =>> 20.
:- (-4) =>> (-8).
:- \+ (1 =>> 0).
:- \+ (3 =>> 7).
:- op(500, fx, isSingleton).
% check if list is a singleton
isSingleton [_].
:- \+ isSingleton [].
:- isSingleton [8].
:- \+ isSingleton [a,b].
% insertion sort
isort(Src, Dst) :-
% we insert each elem of Src into resulting list (which is initially [])
foldl(insert_ord, Src, [], Dst).
% trivial case
insert_ord(X, [], [X]).
% if current inserted X <= top Y, just prepend X to the list
insert_ord(X, [Y | Rest], [X, Y | Rest]) :-
X =< Y.
% otherwise insert X into the Rest producing Rest1 and prepend Y back
insert_ord(X, [Y | Rest], [Y | Rest1]) :-
X > Y,
insert_ord(X, Rest, Rest1).
:- isort([7,3,5,4,1,2,6],[1,2,3,4,5,6,7]).
% merge sort
%
% idea is: split list on two, recursively merge-sort both and merge the results
%
msort([], []).
msort([X], [X]).
msort(List, Sorted) :-
split(List, A, B), % split
maplist(msort, [A, B], [A1, B1]), % recure
merge(A1, B1, Sorted), % merge
!.
% split: [a,b,c,d,e,f,…] -> ([a,c,e,…], [b,d,f,…])
split(List, A, B) :- split(List, [], [], A, B).
split([], A, B, A, B).
split([X], A, B, [X | A], B).
split([X, Y | Rest], A, B, [X | AN], [Y | BN]) :-
split(Rest, A, B, AN, BN).
% merge two sorted lists into one sorted
merge(L, R, X) :- merge(L, R, [], X).
% if one or another is empty, the result is nonempty one
merge([], R, X, XN) :-
append(X, R, XN).
merge(L, [], X, XN) :-
append(X, L, XN).
% if one top is less than other, it goes first
merge([A | L], [B | R], X, XN) :-
A < B,
append(X, [A], X1),
merge(L, [B | R], X1, XN).
merge([A | L], [B | R], X, XN) :-
B =< A,
append(X, [B], X1),
merge([A | L], R, X1, XN).
:- msort([7,3,5,4,1,2,6],[1,2,3,4,5,6,7]).
Project Details
- Date November 3, 2016
- Tags Programming, Prolog and Clisp