How to recognize A^n B^n language in Prolog without arithmetics and for any A, B where A != B?
With known A = a and B = b we could write
% For each 'a' save 'b' in a list, then check
% whether constructed list is equal to the rest of input list
anbn(L) :- anbn(L, []).
anbn(L, L).
anbn([a|L],A) :- anbn(L, [b|A]).
For any A and B I was thinking of a solution starting with
anbn(L) :- anbn(L, []).
anbn([H|L],[]) :- anbn(L,[H]). % save an element
anbn([H|L], [H|A]) :- anbn(L, [H,H|A]). % make sure front elements are the same
so that the first elements are all the same, but than I don't see an elegant way of checking whether all elements in the rest of the list are the same and different than the elemenets in the front.
I could check whether the rest is as long as the stored list and then whether it only consists of the second type elements but I believe I'm overcomplicating the problem and there exists a short and simple solution.
Edit: back to the original solution, and sticking to it:
anbn(List) :- List = [] -> true; List = [A|Rest], a(Rest, A, 0).
a([A|Rest], A, N) :- !, a(Rest, A, s(N)).
a([B|Rest], _, N) :- b(Rest, B, N).
b([B|Rest], B, s(N)) :- b(Rest, B, N).
b([], _, 0).
It is iterative, it does not create choice-points, it is obvious, and it is correct, if all elements of the list are ground.