remove(X, [X|L1], L1).
remove(X, [Y|L1], L2) :- remove(X, L1, L3), append([Y], L3, L2).


member(X, [X|R]).
member(X, [Y|R]) :- member(X,R).

append([], L1, L1).
append([H|L1], L2, [H|L3]) :- append(L1, L2, L3).

factorial(0,1).
factorial(1,1).
factorial(N,M) :- 
    N1 is N - 1,
    factorial(N1, M1),
    M is N * M1.

likes(jake, chocolate).
likes(jake, apricots).
likes(darcie, licorice).
likes(darcie, apricots).

speed(ford, 100).
speed(chevy, 105).
speed(dodge, 95).
speed(volvo, 80).
time(ford, 20).
time(chevy, 21).
time(dodge, 24).
time(volvo, 24).
distance(X,Y) :- speed(X,S), time(X, T), Y is S * T.

parent(john, darcie).
parent(darcie, jake).

ancestor(X,X).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

sum([],0).
sum([X|Rest], Y) :- sum(Rest, Z), Y is X + Z.

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

perm([],[]).
perm(L, [X | Rest]) :- remove(X, L, L1), perm(L1, Rest).

sorted([]).
sorted([X]).
sorted([X, Y | List]) :- X =< Y, sorted([Y | List]).

dosort(Old, New) :- perm(Old, New), sorted(New).

merge([], X, X).
merge(X, [], X).
merge([X|R1], [Y|R2], [X|R]) :- X =< Y, merge(R1, [Y|R2], R).
merge([X|R1], [Y|R2], [Y|R]) :- X > Y, merge([X|R1], R2, R).

