# PROLOG

%%% %%% This is one of the example programs from the textbook: %%% %%% Artificial Intelligence: %%% Structures and strategies for complex problem solving %%% %%% by George F. Luger and William A. Stubblefield %%% %%% Corrections by Christopher E. Davis (chris2d@cs.unm.edu) %%% %%% These programs are copyrighted by Benjamin/Cummings Publishers. %%% %%% We offer them for use, free of charge, for educational purposes only. %%% %%% Disclaimer: These programs are provided with no warranty whatsoever as to %%% their correctness, reliability, or any other property. We have written %%% them for specific educational purposes, and have made no effort %%% to produce commercial quality computer programs. Please do not expect %%% more of them then we have intended. %%% %%% This code has been tested with SWI-Prolog (Multi-threaded, Version 5.2.13) %%% and appears to function as intended. %%%%%%%%%%%%%%%%%%%% stack operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%% % These predicates give a simple, list based implementation of stacks % empty stack generates/tests an empty stack member(X,[X|_]). member(X,[_|T]):-member(X,T). empty_stack([]). % member_stack tests if an element is a member of a stack member_stack(E, S) :- member(E, S). % stack performs the push, pop and peek operations % to push an element onto the stack % ?- stack(a, [b,c,d], S). % S = [a,b,c,d] % To pop an element from the stack % ?- stack(Top, Rest, [a,b,c]). % Top = a, Rest = [b,c] % To peek at the top element on the stack % ?- stack(Top, _, [a,b,c]). % Top = a stack(E, S, [E|S]). %%%%%%%%%%%%%%%%%%%% queue operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % These predicates give a simple, list based implementation of % FIFO queues % empty queue generates/tests an empty queue empty_queue([]). % member_queue tests if an element is a member of a queue member_queue(E, S) :- member(E, S). % add_to_queue adds a new element to the back of the queue add_to_queue(E, [], [E]). add_to_queue(E, [H|T], [H|Tnew]) :- add_to_queue(E, T, Tnew). % remove_from_queue removes the next element from the queue % Note that it can also be used to examine that element % without removing it remove_from_queue(E, [E|T], T). append_queue(First, Second, Concatenation) :- append(First, Second, Concatenation). %%%%%%%%%%%%%%%%%%%% set operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % These predicates give a simple, % list based implementation of sets % empty_set tests/generates an empty set. empty_set([]). member_set(E, S) :- member(E, S). % add_to_set adds a new member to a set, allowing each element % to appear only once add_to_set(X, S, S) :- member(X, S), !. add_to_set(X, S, [X|S]). remove_from_set(_, [], []). remove_from_set(E, [E|T], T) :- !. remove_from_set(E, [H|T], [H|T_new]) :- remove_from_set(E, T, T_new), !. union([], S, S). union([H|T], S, S_new) :- union(T, S, S2), add_to_set(H, S2, S_new). intersection([], _, []). intersection([H|T], S, [H|S_new]) :- member_set(H, S), intersection(T, S, S_new),!. intersection([_|T], S, S_new) :- intersection(T, S, S_new),!. set_diff([], _, []). set_diff([H|T], S, T_new) :- member_set(H, S), set_diff(T, S, T_new),!. set_diff([H|T], S, [H|T_new]) :- set_diff(T, S, T_new), !. subset([], _). subset([H|T], S) :- member_set(H, S), subset(T, S). equal_set(S1, S2) :- subset(S1, S2), subset(S2, S1). %%%%%%%%%%%%%%%%%%%%%%% priority queue operations %%%%%%%%%%%%%%%%%%% % These predicates provide a simple list based implementation % of a priority queue. % They assume a definition of precedes for the objects being handled empty_sort_queue([]). member_sort_queue(E, S) :- member(E, S). insert_sort_queue(State, [], [State]). insert_sort_queue(State, [H | T], [State, H | T]) :- precedes(State, H). insert_sort_queue(State, [H|T], [H | T_new]) :- insert_sort_queue(State, T, T_new). remove_sort_queue(First, [First|Rest], Rest).