/***** Making change for $1: */
change(Q,D,N,P) :-
member(Q,[0,1,2,3,4]), /* quarters */
member(D,[0,1,2,3,4,5,6,7,8,9,10]) , /* dimes */
member(N,[0,1,2,3,4,5,6,7,8,9,10, /* nickels */
11,12,13,14,15,16,17,18,19,20]),
Sum is 25*Q +10*D + 5*N,
Sum =< 100,
P is 100-Sum.
/***** Defining sorting as an ordered permutation of a list: */
/* select(X, HasAnX, HasOneLessX) "extracts" X from HasAnX,
giving HasOneLessX. It's built into Prolog, but here's its defn, anyway:
select(X, [X|Rest], Rest).
select(X, [Y|Ys], [Y|Zs]) :- select(X, Ys, Zs).
*/
/* permutation(Xs, Zs) holds true if Zs is a reordering of Xs */
permutation([], []).
permutation(Xs, [Z|Zs]) :- select(Z, Xs, Ys), permutation(Ys, Zs).
/* ordered(Xs) holds true if the elements in Xs are ordered by < */
ordered([]).
ordered([X]).
ordered([X,Y|Rest]) :- X =< Y, ordered([Y|Rest]).
/* sorted(Xs, Ys) holds when Ys is the sorted variant of Xs */
sorted(Xs, Ys) :- permutation(Xs, Ys), ordered(Ys).
/***** Defining a quadratic-time sort algorithm: */
/* insert(X, L, LwithX) inserts element X into list L, generating LwithX */
insert(X, [], [X]).
insert(X, [Y|Ys], [X, Y | Ys]) :- X =< Y.
insert(X, [Y|Ys], [Y|Zs]) :- X > Y, insert(X, Ys, Zs).
/* isort(Xs, Ys) generates Ys as the sorted variant of Xs */
isort([], []).
isort([X|Xs], Ys) :- isort(Xs, Zs), insert(X, Zs, Ys).