matches(ε, []).
matches(X, [X]) :- atom(X).
matches(∪(A, _), S) :- matches(A, S).
matches(∪(_, B), S) :- matches(B, S).
matches(·(A, B), S) :- append(X, Y, S), matches(A, X), matches(B, Y).
matches(*(_), []).
matches(*(A), S) :- append(S1, S2, S), S1 \= [], matches(A, S1), matches(*(A), S2).

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

remove([(C,N)|L], C, [(C,N1)|L]) :- N > 0, N1 is N - 1.
remove([X|L], Y, [X|R]) :- remove(L, Y, R).

put([], C, [(C,1)]).
put([(C,N)|L], C, [(C,N1)|L]) :- N1 is N + 1, !.
put([X|L], Y, [X|R]) :- put(L, Y, R).

change(0, _, []) :- !.
change(X, [(C,N)|Coins], ChangeNew) :-
  remove([(C,N)|Coins], C, CoinsNew),
  Xnew is X - C, Xnew >= 0,
  change(Xnew, CoinsNew, Change),
  put(Change, C, ChangeNew).
change(X, [_|Coins], ChangeNew) :- change(X, Coins, ChangeNew).

