CODEWITHSUNDEEP
listrecursionprolog
Ans Piter
Ans Piter

Reputation: 573

Looping result during parsing list

I'd like to parsing liste of dozens upper and lower atoms to achieve list of lists

Example

List = ['F1',a,'F2',a,b,'F3',a,b,c,...]

Expected Result

List_F =[['F1',a],['F2',a,b],['F3',a,b,c]|...]

I have two predicates is_lower/1 and is_upper/1 which return true if the current atom is lower (resp. upper), at this stage I succeeded to do this predicate but with little error which the result is relooped

Code

get_functors([],[]).
get_functors([X,Y|Xs],[[X]|Facts]) :-         is_lower(X),is_upper(Y),
                                                   get_functors(Xs,Facts),!. 


get_functors([X,Y|Xs],[[X,Y|Fact]|Facts])     :-      is_lower(X),is_lower(Y),
                                                    get_functors(Xs,[Fact|Facts]).

get_functors([X,Y|Xs],[[X|Fact]|Facts])   :-      is_upper(X),is_lower(Y),
                                                    get_functors(Xs,[Fact|Facts]).

Test

| ?- get_functors(['F1',a,b,'F2',c,d],L).
L = [['F1',a,b],['F2',c,d]] ? ;
L = [['F1',a],[b],['F2',c,d]] ? ;
L = [['F1',a,b,'F2',c,d]] ? ;
L = [['F1',a,b,'F2',c],[d]] ? ;
L = [['F1',a,b,'F2',c,d]] ? ;
L = [['F1',a,b,'F2'],[c,d]] ? ;
L = [['F1',a,b,'F2'],[c],[d]] ? 
yes

I think that is because the Cut "!", but I don't know where I shoud put it

if there are some improvements to this predicate plz suggest them

Upvotes: 0

Views: 34

Answers (1)

lurker
lurker

Reputation: 58244

In the solution you show, if you find you're trying to figure out where to put a cut to trim out incorrect answers, then the logic is not correct somewhere since it allows invalid solutions.

This would make a good problem for a DCG (definite clause grammar) solution, and is more easily conceptualized and solved this way:

get_functors(List, Functors) :-
    phrase(functor_list(Functors), List).

% An empty functor list results from an empty input
% A functor list [F|T] results from seeing a term F follow by a functor list, T

functor_list([]) --> [].
functor_list([F|T]) --> term(F), functor_list(T).

% A term [F|A] is an upper case atom followed by a list of lower case atoms

term([F|A]) --> [F], { is_upper(F) }, lc_atoms(A).

% Recognize a list of lower case atoms 

lc_atoms([]) --> [].
lc_atoms([H|T]) --> [H], { is_lower(H) }, lc_atoms(T).

% Some simple definitions of is_upper and is_lower

is_upper(S) :-
    atom_codes(S, [X|_]),
    X =< 90, X >= 65.

is_lower(S) :-
    \+ is_upper(S).

I threw this together kind of quickly, so there may still be some niggles in it, and it leaves a choice point, but I'll leave that as an exercise for the reader.

Here's a sample query:

| ?-  get_functors(['F1',a,'F2',a,b,'F3',a,b,c], L).

L = [['F1',a],['F2',a,b],['F3',a,b,c]] ? a

(1 ms) no

You can use listing in GNU or SWI Prolog to see the canonical predicate form of the DCG:

functor_list([], A, A).
functor_list([A|B], C, D) :-
        term(A, C, E),
        functor_list(B, E, D).

term([A|B], [A|C], D) :-
        is_upper(A),
        lc_atoms(B, C, D).

lc_atoms([], A, A).
lc_atoms([A|B], [A|C], D) :-
        is_lower(A),
        lc_atoms(B, C, D).

is_upper(A) :-
        atom_codes(A, [B|_]),
        B =< 90,
        B >= 65.

is_lower(A) :-
        \+ is_upper(A).

This would be called directly by:

get_functors(List, Functors) :-
    functor_list(Functors, List, []).

Upvotes: 1

Related Questions