common subsequences of lists in prolog

Question

I'm trying to write a predicate common(L, S) which from a list of lists L generates in S all common subsequences of the lists in L.

subseq([], _).
subseq([H|S], L) :- append(_, [H|T], L), subseq(S, T).


common(L, X) :- not((
        member(A, L),
        not(subseq(X, A))
       )).

It just gives me 'true' even with wrong input.

For example:

common([[1,2,3,4], [2,3], [12]], X). true

Edit

I've noticed that it's actually working but it's just not substituting X with the term for which the predicate is true.

What do you mean with 'yes'? Can you give the exact query? Furthermore that is logical: negation in Prolog is not constructive. So it will either return true or false. — Willem Van Onsem
Yes, sorry about that. I've edited the post adding an example query. — Nikola
Furthermore you want all common subsequences? Because that is a hard problem (in terms of computational complexity). Please specify with a few examples (input and expected output what you aim to do). — Willem Van Onsem
Please note that a subsequence is something different! What you want is called a substring or sublist. — false
Thanks, I have forgotten that. But even after changing the definition of subseq to subseq([], _). subseq([H|S], L) :- append(_, [H|T], L), subseq(S, T). It still behaves the same way. I've noticed that it's working properly when I give it exact values, but when trying to substitute X with the result it doesn't work. It just gives 'yes' — Nikola

false false · Accepted Answer · 2017-06-24T16:18:20

A substring is a non-empty prefix of a suffix.

substring_of(Ys, Xs) :-
   Ys = [_|_],           %  a non-empty
   append(_, Zs, Xs),    %                       a suffix of Xs
   append(Ys, _, Zs).    %             prefix of 

common(Xss, Xs) :-       % Xs is a substring of each element of Xss
   maplist(substring_of(Xs), Xss).

?- common([[1,2,3,4], [2,3,4,5]], Xs).
Xs = [2] ;
Xs = [2, 3] ;
Xs = [2, 3, 4] ;
Xs = [3] ;
Xs = [3, 4] ;
Xs = [4] ;
false.

common subsequences of lists in prolog

1 Answers