I figured out the code for testing equal a's and b's in a list but can't understand the underlying recursion

s(A,A).
s(A,D):- l(A,B),s(B,C),r(C,D).

l([a|A],A).

r([b|A],A).

The above code in prolog checks if the given input of a list has equal a's and b's or not.

Such as

s([a,a,b,b],[]).
True.

This involves recursion and difference lists. Can anyone explains how the underlying recursion checks equal a's with b's step by step.

List differences are not easy to understand if you reason about them at a low level.

Therefore, I first recommend a more high-level view:

Over all, your predicate s/2 describes a list. I say "describes", because it not only "checks", but also generates and completes such lists if we want!

We can read each goal of s/2 as "and then some element(s) of the list".

So, forget about the arguments for a moment and consider the abstract structure of the predicate. I use (-->)/2 now instead of (:-)/2 to make clear that I am talking about a small variation of the predicate, where I simply ignore the arguments:

s --> [].
s --> l, s, r.

We can do the same with l/2 and r/2:

l --> [a].
r --> [b].

This is what the predicates describe in an abstract, high-level view of the lists. In this notation, I need not wrestle with list differences and arguments. Instead, I can focus directly on the essence of the program.

It is obvious that you can easily translate such high-level code to the code that you posted. In fact, Prolog performs this translation for you if you consult this code: It is called DCG notation. See dcg for more information.

So, it now is clear: s//0 describes a list that is either empty, or:

• a list described by l//0
• and then a list described by s//0
• and then a list described by r//0.

Since l//0 describes a list with a single element a, and r//0 describes a list with a single element b, it is clear that in the lists that s//0 describes, there is always the same number of as and bs.

We use phrase/2 to invoke a DCG. For example:

?- phrase(s, Ls).
Ls = [] ;
Ls = [a, b] ;
Ls = [a, a, b, b] ;
Ls = [a, a, a, b, b, b] .

If you start to reason about recursion explicitly, you will not make much progress, because it quickly gets too hard to trace the exact steps that are performed by the Prolog engine, and to take all possibilities into account. I recommend you focus on the meaning of your predicates, and try to understand what they are actually describing.

EDIT: If you want to reason about the arguments explicitly, an algebraic analogy may help: We can regard each pair of arguments as describing a list as a "difference" between two lists, a list difference, also in analogy to differential Δ used in calculus.

For example, the "difference" between [X,Y,Z|Rs] and Rs is [X,Y,Z]. Hence, at least symbolically, we can write:

Let us denote with L, L₀, L₁ and L₂ the lists that are described by such differences in the second clause:

Algebraically, we can think about L as the "sum" (concatenation) of the other lists:

For the other lists, we have:

So, in total, we have:

Note that no recursion is necessary to understand this. Instead, what matters is rather the relation between the arguments. Personally, I also find such a derivation less useful than the converse: I think it is much more important to notice this pattern when you write such code, because this means that you can use DCG notation instead, and significantly reduce the number of arguments that are passed around!