/***** 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).