Search code examples
prologdcg

How to program in Prolog a function that does operations on lists


How can I make a program in Prolog that contains n numbers of a and n numbers of b, it's important to note here that the number of a and b in the list must be equal, also the list must always start with a and finish with b, otherwise it's false. Example : [a,b] is true, [a,a,a,b,b,b] is true, [a,a,a,a] is false and [a,a,a,b,b] is also false.

Here is what I tried to do :

langageB([b]).
langageB([b| S]):- langageB(S).

language([]).

langage([a,b]).
langage([a | S]):- langage(S).
langage([a| S]):- langageB(S).

But it does not work as I want it to.


Solution

  • Using DCG notation, the desired language can be defined as:

    langage --> [a,b].
    langage --> [a], langage, [b]. % For each a at the beginning of the list 
                                   % there must be a corresponding b at the end
    
    langage(List) :- phrase(langage, List).
    

    Examples:

    ?- langage([a,a,a,b,b,b]).
    true .
    
    ?- langage([a,a,b,b,b]).
    false.
    
    ?- langage(L).
    L = [a, b] ;
    L = [a, a, b, b] ;
    L = [a, a, a, b, b, b] ;
    L = [a, a, a, a, b, b, b, b] .
    

    If you want to see how to define the predicate directly using difference lists, you can list the clauses of the predicate langage/2:

    ?- listing(langage).
    
    langage([a, b|A], A).
    
    langage([a|A], B) :-
        langage(A, C),
        C=[b|B].
    

    So, an alternative solution is:

    langage(List) :-
      langage(List, []).
    
    langage([a, b|A], A).
    
    langage([a|A], B) :-
        langage(A, C),
        C = [b|B].