valid bracket list in prolog

Question

I'm trying to test if a list of brackets is valid. My code:

checkbrackets([]).
checkbrackets(['('|T]):-
    T = [')'|List],
    checkbrackets(List).    
checkbrackets(['('|T]):-
    T = ['('|List],
    append(Rest,[')'],T),
    checkbrackets(Rest).

My code works for ['(', '(', ')', '(', '(', ')', ')', ')']
but it fails for ['(', '(', ')', ')', '(', ')'].
What am I doing wrong? Is it possible to write such a test without additional arguments like counters?

Answer 1

your append(Rest, [')'], T) will parse until the end of the list, but it is not said that the opening bracket will eventually match with the last closing bracket, for example ()() does not.

That being said, I think you make things overcomplicated. Instead of obtaining all sorts of sublists, you can use a single scan here: you use an accumulator that you initialize with 0, and the accumulator should eventually end with 0 and never be less than zero, so:

checkbrackets(B) :-
    checkbrackets(B, 0).

checkbrackets([], 0).  %% ← at the end, zero
checkbrackets([')'|T], N) :-
    N > 0,   %% ← always greater than or equal to zero.
    N1 is N-1,
    checkbrackets(T, N1).
checkbrackets(['('|T], N) :-
    N1 is N+1,
    checkbrackets(T, N1).

Answer 2

For the sake of completeness, here is a solution without additional arguments.

checkbrackets([]).
checkbrackets(['('|Rest]):-
    append(Sub1,[')'|Sub2],Rest),
    checkbrackets(Sub1),
    checkbrackets(Sub2).

It simply follows the definition of "properly parenthesized" expression. Either it is empty, or it starts with a (, followed by a properly parenthesized subexpression (Sub1), followed by ), followed by another properly parenthesized subexpression (Sub2).

However, it is fairly inefficient as compared to the direct solution with one extra argument presented by Willem Van Onsem. The main issue is that the append/3 call needs to non-deterministically "guess" the position of the matching closing parenthesis and this generates a lot of backtracking.