Skip to content

Instantly share code, notes, and snippets.

@raskasa
Created December 14, 2012 03:23
Show Gist options
  • Save raskasa/4282471 to your computer and use it in GitHub Desktop.
Save raskasa/4282471 to your computer and use it in GitHub Desktop.
All useful Prolog functions learned over the course of the semester in CS 341 - Programming Languages.
% Contained within are all the useful Prolog functions learned in CS 341 this past semester (Fall 2012).
% NOTE: Any functions used that are not defined in this file are built-in functions.
% length(+As,-N)
% returns in N the length of the list As
length([],0).
length([A|As],N) :- length(As,M), N is M+1.
% append(+As,+Bs,-Cs)
% returns in Cs the append of lists As and Bs
append([],Bs,Bs).
append([A|As],Bs,[A|Cs]) :- append(As,Bs,Cs).
% reverse(+As,-Xs)
% returns in Xs the reverse of list As
reverse([],[]).
reverse([A|As],Bs) :- reverse(As,Xs), append(Xs,[A|Bs]).
% lists(+As)
% decides if a list is a proper list or not
lists([]).
lists([_|As]) :- lists(As).
% member(+A,+As)
% checks if item A appears in list As
member(A,[A|_]).
member(A,[_|As]) :- member(A,As). % BETTER: member(A,[B|As]) :- \+ A=B, member(A,As).
% prefix(+As,+Bs)
% checks if list As is a prefix of list Bs.
prefix([],_).
prefix([A|As],[A|Bs]) :- prefix(As,Bs).
% delete(+A,+As,-Bs)
% returns in Bs the list obtained from deleting item A fro list As
delete(A,[],[]).
delete(A,[A|As],As).
delete(A,[B|As],[B|Bs]) :- \+ A=B, delete(A,As,Bs).
% select_any(+List,-Item)
% returns in Item a random item from list List
select_any([A],A).
select_any(As,X) :- length(As,L), R is random (L), select(As,R,X).
% shuffle(+As,-Bs)
% returns the shuffle of list As in list Bs
shuffle([],[]).
shuffle([A|As],Bs) :- shuffle(As,Xs), append(Ps,Qs,Xs), append(Ps,[A|Qs],Bs).
% sorted(+As)
% checks if the list (of integers) As is sorted (ascending) or not
sorted([]).
sorted([A]).
sorted([A,B|Bs]) :- A@<B, sorted([B|Bs]).
% sort(+As,-Bs)
% sorts the list (of integers) As into the list Bs
sort(As,Bs) :- shuffle(As,Bs), sorted(Bs).
% delete_all(+Item,+List1,-List2)
% deletes all appearances of Item in List1 and returns answer in List2
delete_all(A,[],[]).
delete_all(A,[A|As],Bs) :- delete_all(A,As,Bs).
delete_all(A,[B|Bs],[B,Cs]) :- \+ A=B, delete_all(A,Bs,Cs).
% remove_duplicates(+List1,-List2)
% removes duplicates from List1 and returns answer in List2
remove_duplicates([],[]).
remove_duplicates([A|As],[A|Bs]) :- delete_all(A,As,Xs), remove_duplicates(Xs,Bs).
% .... and using the predicate 'member'
remove_duplicates([A|As],Bs) :- member(A,As), remove_duplicates(As,Bs).
remove_duplicates([A|As],[A|Bs]) :- \+ member(A,As), remove_duplicates(As,Bs).
% suffix(+List1,+List2)
% checks is List1 is a suffix of List2 (using 'prefx')
suffix(As,Bs) :- reverse(As,Xs), reverse(Bs,Ys), prefix(Xs,Ys).
% .... and without using prefix:
suffix(As,As).
suffix(As,[B|Bs]) :- suffix(As,Bs).
% isort(+As,-Bs)
% sort the list of numbers As and returns the answer in Bs, using insertion sort
isort([],[]).
isort([A|As],Bs) :- isort(A,Xs), insert(A,Xs,Bs).
% insert(+A,+As,-Bs)
% inserts item A into sorted list As to get sorted list Bs
insert(A,[],[]).
insert(A,[B|Bs],[A,B|Bs]) :- A@<B.
insert(A,[B|Bs],[B|Cs]) :- \+ A@<B, insert(A,Bs,Cs).
% gsort
% generically sort the list As into Bs using the comparison operator Less
gsort([],[],Les).
gsort([A|As],Bs,Less) :- gsort(As,Xs,Less), ginsert(A,Xs,Bs,Less).
% ginsert
% generically inserts item A into sorted list As and returns the answer in list Bs
ginsert(A,[],[A],Less).
ginsert(A,[B|Bs],[A,B|Bs],Less) :- P :.. [Less,A,B], call(P)!.
ginsert(A,[B|Bs],[B|Cs],Less) :- P=.. [Less,B,A], call(P), !, ginsert(A,Bs,Cs,Less).
% set(+As)
% checks if As is a set
set([]).
set([A|As]) :- \+ member(A,As), set(As).
% pairs(+X,+Xs,-Ys)
% returns in Ys the list of pairs
pairs(A,[],[]).
pairs(A,[B|Bs],[[A,B]|Cs]) :- pairs(A,Bs,Cs).
% product(+xs,+Ys,-Zs)
% returns in the Cartesian product of sets Xs and Ys in Zs.
product([],Bs,[]).
product([A|As],Bs,Cs) :- pairs(A,Bs,Xs), product(As,Bs,Ys), append*Xs,Ys,Cs).
% power(+As,-Bs)
% returns the set of all subsets of a set
power(+As,-Bs).
power([A|As],Bs) :- power(As,Xs), attach(A,Xs,Ys), append(Xs,Ys,Bs).
attach(A,[],[]).
attach(A,[B|Bs],[[A|B]|Cs]) :- attach(A,Bs,Cs).
@rutvi21
Copy link

rutvi21 commented Apr 1, 2018

please help me with prolog code for cartesian product of three sets @

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment