CODEWITHSUNDEEP
listprolog
skazhy
skazhy

Reputation: 4651

Outputting final list from recursive predicate in Prolog

I wrote a program, that finds the longest coprime subsequence in a Prolog list (it is not yet perfect):

longest_lcs([A, B | Tail],X) :- gcd(A,B,1),lcs([B | Tail],X,A,1).
longest_lcs([A, B | Tail],X) :- lcs([B | Tail],X,A,0).

lcs([],G,_,_) :- rev(G,G1),write(G1).

lcs([A, B | Tail],G,Q,_) :- gcd(B,Q,1), gcd(A,B,1), lcs([B | Tail], [Q | G], A, 1),!.
lcs([A, B | Tail],G,Q,_) :- gcd(B,Q,1);gcd(A,B,1), lcs([B | Tail], [Q | G], A, 0).

lcs([A, B | Tail],G,_,0) :- gcd(A,B,1), lcs([B | Tail], G, A, 1).
lcs([A, B | Tail],G,_,1) :- lcs([B | Tail], G, A, 1).
lcs([A, B | Tail],G,_,0) :- lcs([B | Tail], G, A, 0).

lcs([A],G,Q,_) :- gcd(Q,A,1),lcs([], [A, Q | G], _, _).

Currently I output the subsequence with the write predicate, but I need it to run the following way:

?- longest_lcs([1,2,3,4],X).
X = [1,2,3,4]

?- longest_lcs([2,4,8,16],X).
X = []

What modifications do I need to make, so this works?

Upvotes: 1

Views: 369

Answers (1)

mat
mat

Reputation: 40768

Why do you want to use write/1? Focus on a clear declarative description of what you want, and the toplevel will do the writing for you. A possible formulation for a longest coprime subsequence is: It is a coprime subsequence, and no other coprime subsequnce is longer. The code could look similar to this:

list_lcpsubseq(Ls, Subseq) :-
    list_subseq(Ls, Subseq),
    coprimes(Subseq),
    length(Subseq, L),
    \+ ( list_subseq(Ls, Others), coprimes(Others), length(Others, O), O > L ).

Upvotes: 4

Related Questions