prolog - sublist of list - alternative approach

Question

I implemented function to get sublist of list, for example:

sublist([1,2,4], [1,2,3,4,5,1,2,4,6]).
true

sublist([1,2,4], [1,2,3,4,5,1,2,6]). false look at my solution:

my_equals([], _).
my_equals([H1|T1], [H1|T2]) :- my_equals(T1, T2).

sublist([], _).
sublist(L1, [H2|T2]) :- my_equals(L1, [H2|T2]); sublist(L1, T2).  

Could you give me another solution ? Maybe there is exists some predefined predicate as my_equals ?

Langston

my_equals(L1, L2) would be equivalent to append(L1, _, L2). – Kristiekristien

A better name than my_equals would be prefix_of. – Anosmia

@lurker, Tell me if I correctly understand you, please. In reality, append(L1, _, L2) checks if L1 (entire) is prefix of L2. Analogously, append(_, L1, L2) checks if L1 (entire) is sufix of L2,. yeah ? – Langston

@HaskellFun you got it :) – Kristiekristien

Although I would probably change the terminology and rather than say checks I'd say succeeds. So, append(_, L1, L2) succeeds if L1 is a suffix of L2. – Kristiekristien

Answer 1

There's also a DCG approach to the problem:

substr(Sub) --> seq(_), seq(Sub), seq(_).

seq([]) --> [].
seq([Next|Rest]) --> [Next], seq(Rest).

Which you would call with:

phrase(substr([1,2,4]), [1,2,3,4,5,1,2,4,6]).

You can define:

sublist(Sub, List) :-
    phrase(substr(Sub), List).

So you could call it by, sublist([1,2,4], [1,2,3,4,5,1,2,4,6])..

---

Per @mat's suggestion:

substr(Sub) --> ..., seq(Sub), ... .

... --> [] | [_], ... .

Yes, you can have a predicate named .... :)

---

Per suggestions from @repeat and @false, I changed the name from subseq (subsequence) to substr (substring) since the meaning of "subsequence" embraces non-contiguous sequences.

Kristiekristien

...//0 would be handy here: ..., list(Sub), .... – Accusatory

Nice! ... --> [] | [_], ... ;-) – Accusatory

@Accusatory oy, I can be so verbose sometimes. :) – Kristiekristien

@Loydloydie yes, you're right. seq//1 is better. Thanks. – Kristiekristien

Note that subseq should rather be called substring due to the entirely different meaning of subsequence. That is odd, but it is the "common" terminology. I still have to update my own courses for this... – Loydloydie

I second what false said. "Subsequence"(en.m.wikipedia.org/wiki/Subsequence) means you can have holes in it, "substring" means 'holes not allowed'. In this regard the version 3 of your answer was better than version 5 (the current one). I suggest going back to 3. – Anosmia

@Anosmia I can definitely see "subsequence" being an issue due to the "holes allowed" aspect of the definition. I struggle with "substring" because I don't think of a series of numbers, for example, as a "string". Perhaps, then, I should call it a "contiguous subsequence" or "unbroken subsequence" or "partial sequence"? – Kristiekristien

Finding good names is hard. How about the name sublist instead of substring? It's somewhat parallel to subarray as in "maximum subarray problem", yet simple and concise... – Anosmia

@repeat, I believe false objected to "list" and I assumed it applied to sublist. – Kristiekristien

@Anosmia I did notice in this disseration, on page 6, it says, "Es must be a subsequence of Es0" as in contiguous, so perhaps my original usage was in good company. :) – Kristiekristien

@lurker. It sure is! – Anosmia

@pasabaporaqui they aren't exactly the same as could be illustrated by observing the ordering difference of results of, for example, the query, sublist(A, [a,b,c,d]). – Kristiekristien

Answer 2

You can unify a sublist using append/3, like this:

sublist(SubList, List):-
  append(_, Tail, List),
  append(SubList, _, Tail).

The first call to append/3 will split List into two parts (i.e. dismiss the some "leading" items from List. The second call to append/3 will check whether SubList is itself a sublist of Tail.

As @false's suggests it would be better, at least for ground terms, to exchange goals,

sublist(SubList, List):-
  append(SubList, _, Tail),
  append(_, Tail, List).

Rambler

Isn't it better to exchange goals? – Loydloydie

How is it possible to use Tail ? There is no this variable on the left side ? – Langston

The second implementation has a termination issue I think. – Kristiekristien

@HaskellFun the predicate append/3 is a predicate that nicely defines a relation. In Prolog, a relation can "generate" results, so append(Sublist, _, Tail) will succeed for values of Tail that has variables. As an elucidating exercise, at the Prolog prompt, try the query, append([a,b,c], _, Tail) and see what kind of results you get. :) – Kristiekristien

@lurker: Yes, with non-ground terms I prefer the first implementation (in my opinion) if the procedure used for generating solutions. – Rambler

Answer 3

This is an alternative solution to Lurkers, which is slightly faster, assuming S is much shorter than L in length and thus the phrase/3 DCG translation time is negligible:

sublist(S, L) :-
     phrase((..., S), L, _).

If S=[X1,..,Xn] it will DCG translate this into a match I=[X1,..,Xn|O] before execution, thus delegating my_equals/2 completely to Prolog unification. Here is an example run:

?- phrase((..., [a,b]), [a,c,a,b,a,c,a,b,a,c], X).
X = [a, c, a, b, a, c] ; 
X = [a, c] ; 
false.

Bye

P.S.: Works also for other patterns S than only terminals.

Joyann

Answer 4

Maybe there is exists some predefined predicate

If your Prolog has append/2 from library(lists):

sublist(S, L) :- append([_,S,_], L).

Another fairly compact definition, available in every (I guess) Prolog out there:

sublist(S, L) :- append(S, _, L).
sublist(S, [_|L]) :- sublist(S, L).

Phenice

Answer 5

Solution in the original question is valid just, as has been said, remark that "my_equals" can be replaced by "append" and "sublist" loop by another append providing slices of the original list.

However, prolog is (or it was) about artificial intelligence. Any person can answer immediately "no" to this example:

sublist([1,1,1,2], [1,1,1,1,1,1,1,1,1,1] ).

because a person, with simple observation of the list, infers some characteristics of it, like that there are no a "2".

Instead, the proposals are really inefficient on this case. By example, in the area of DNA analysis, where long sequences of only four elements are studied, this kind of algorithms are not applicable.

Some easy changes can be done, with the objective of look first for the most strongest condition. By example:

/* common( X, Y, C, QX, QY ) => X=C+QX, Y=C+QY */ 
common( [H|S2], [H|L2], [H|C2], DS, DL ) :- !,
     common( S2, L2, C2, DS, DL ).
common( S, L, [], S, L ).

sublist( S, L ) :-
  sublist( [], S, L ). 

sublist( P, Q, L ) :- /* S=P+Q */ 
  writeln( Q ),
  length( P, N ),
  length( PD, N ), /* PD is P with all unbound */
  append( PD, T, L ), /* L=PD+T */ 
  common( Q, T, C, Q2, _DL ), /* S=P+C+Q2; L=PD+C+_DL */
  analysis( L, P, PD, C, Q2 ).  

analysis( _L, P, P, _C, [] ) :- !. /* found sublist */

analysis( [_|L2], P, _PD, C, [] ) :- !,
  sublist( P, C, L2 ).

analysis( [_|L2], P, _PD, C, Q2 ) :-
  append( P, C, P2 ),
  sublist( P2, Q2, L2 ).

Lets us try it:

?- sublist([1,1,1,2], [1,1,1,1,1,1,1,1,1,1]).
[1,1,1,2]
[2]
[2]
[2]
[2]
[2]
[2]
[2]
[2]
false.

see how "analysis" has decided that is better look for the "2".

Obviously, this is a strongly simplified solution, in a real situation better "analysis" can be done and patterns to find must be more flexible (the proposal is restricted to patterns at the tail of the original S pattern).

Perales