numgen(0).
numgen(X) :- numgen(Y), X is Y + 1.

upto(X, Max) :- numgen(X), ( X =< Max ; X > Max, !, fail).

jadd(X, Y, Z) :- number(X), number(Y), Z is X + Y.
jadd(X, Y, Z) :- var(X), number(Y), number(Z), X is Z - Y, X >= 0.
jadd(X, Y, Z) :- var(X), number(Y), var(Z), numgen(X), Z is X + Y.
jadd(X, Y, Z) :- number(X), var(Y), number(Z), Y is Z - X, Y >= 0.
jadd(X, Y, Z) :- number(X), var(Y), var(Z), numgen(Y), Z is X + Y.
jadd(X, Y, Z) :- var(X), var(Y), number(Z), upto(X, Z), Y is Z - X.
jadd(X, Y, Z) :- var(X), var(Y), var(Z), numgen(Z), upto(X, Z), Y is Z - X.

len([], 0).
len([Car | Cdr], N) :- len(Cdr, M), N is M + 1.

% len([2,4,6,8], X) correctly sets X to 4
% len(X, 5) correctly generates a 5 item list of variables, but will look for another solution
% len([X, cat, Y | Rest], 6) produces a 6 item list with cat second, but will look for another

addup([], 0).
addup([Car | Cdr], N) :- addup(Cdr, M), jadd(M, Car, N).

% addup([1, 2, X, 4], 10) finds X=3
% addup([1, 2, X, Y], 10) finds X=7 Y=0, but loops infinitely in search of next solution
% addup([1, 2, X, 4], Y) finds an infinite number of solutions
% addup([1, 2, X, Y], Z) finds an infinite number of solutions, but not in a good way
% addup(X, 6) finds X=[6] and all length-2 solutions but then gets stuck

mem(X, [X | Rest]).
mem(X, [Y | Rest]) :- mem(X, Rest).

% mem(X, [1, 3, 5, 7, 6]) correctly produces all solutions then stops.
% make sure you understand what happens with all of the following:
% mem(4, [1, 3, 5, X, 7]).
% mem(X, [1, 3, 5, Y, 7]).
% mem(X, [1, 3, 5, X, 7]).
% mem(4, Y).
% mem(X, Y).
% mem(3, Y), mem(5, Y).

% mem(X, [2, 4, 6, 8]), write(X), fail.
% gives us all the members of a list, one by one, through backtracking.
% it makes a list into a generator.

% here is another generator
a(1).
a(3).
a(5).
a(7).
% a(X), write(X), fail.

% can you reverse the process, design a prolog query that produces
% the list [1, 3, 5, 7] from the predicate "a"?

% insert into already ordered list

ins(X, [], [X]).
ins(X, [Car | Cdr], [X, Car | Cdr]) :- X < Car.
ins(X, [Car | Cdr], [Car | Y]) :- X >= Car, ins(X, Cdr, Y).

% ins(5, [1, 3, 7, 9], X) gives X=[1, 3, 5, 7, 9]
% ins(X, [1, 3, 7, 9], Y) doesn't work
% ins(X, [1, 3, 7, 9], [1, 3, 5, 7, 9]) doesn't work either

% insertion sort based on that function

isrt([], []).
isrt([Car | Cdr], S) :- isrt(Cdr, T), ins(Car, T, S).

% isrt([3,1,2,4], X) correctly produces X=[1,2,3,4]
% isrt(X, [1,2,3,4]) doesn't work
% isrt(X, Y) produces two correct solutions then fails

% the same as ins, but with no guards

allins(X, [], [X]).
allins(X, [Car | Cdr], [X, Car | Cdr]).
allins(X, [Car | Cdr], [Car | Y]) :- allins(X, Cdr, Y).

% allins(5, [1, 3, 7, 9], X) produces all 5 solutions
% allins(5, X, [1, 3, 5, 7, 9]) cleverly finds that X must be [1, 3, 7, 9]
% allins(X, [1, 3, 7, 9], [1, 3, 5, 7, 9]) amazingly finds that 5 is the missing number

perm([], []).
perm([Car | Cdr], S) :- perm(Cdr, T), allins(Car, T, S).

% perm([a, b, c, d], X) correcly produces all 24 permutations then stops
% perm(X, [w, x, y, z]) amazing! gets all 24, but doesn't know to stop
% perm([1, X, 5, 7], [3, 7, Y, 5]) finds X=3 Y=1 then stops
% perm(X, Y). Try it. It gets every possibility.
% How does it do it?

% others to try.
% work out what tricks you expect them to be capable of, then see if you were right

% append two lists together

ap([], X, X).
ap([Car | Cdr], Acc, [Car | Rest]) :- ap(Cdr, Acc, Rest).

% could this be useful if it could work? can it work?

ap3(A, B, C, D) :- ap(A, B, X), ap(X, C, D).

% what does ap3(X, Y, Z, [1, 2, 3, 4, 5]) do?

% reverse a list

revrs(In, Out) :- rev(In, [], Out).

rev([], Acc, Acc).
rev([Car | Cdr], Acc, Ans) :- rev(Cdr, [Car | Acc], Ans).