Re: Ann: SWI-Prolog 6.5.3

On 22/11/2013, at 2:33 AM, Boris Vassilev wrote:

> P.S. And there is actually no immediately obvious "sub_list" built-in list
> predicate for efficient searching for (overlapping) substrings in a
> list.... Or again, I have not paid enough attention when reading.

It's not quite clear to me what you want here.

The Quintus library included

substring(Whole, Part, Before, Length, After)
    is true when Whole = Front ++ Part ++ Back
    and length(Front, Before)
    and length(Part, Length)
    and length(Back, After).

substring(Whole, Part, Before, Length) :-
    substring(Whole, Part, Before, Length, _).

substring(Whole, Part, Before) :-
    substring(Whole, Part, Before, _, _).

substring(Whole, Part) :-
    substring(Whole, Part, _, _, _).

SWI Prolog has

sub_string(Whole, Start, Length, After, Part)

  -- The argument order is not friendly to dropping
  -- unwanted length arguments.
  -- The name Start suggests a 1-origin *position*,
  -- in fact, like substring/5 it uses a 0-origin *offset*.

sublist(Whole, Part) :-
    append(_, Suffix, Whole),
    append(Part, _, Suffix).

This only makes sense for Whole a proper list (or at least,
one that doesn't end with a variable; ending with an atom
or the number 42 is no problem).  Given that, this basically
is the classical "naive" string search.  (And since Part
might not be ground, it's not in general going to be possible
to do better.)

sublist(Whole, Part, Before) :-
    append_length(_, Suffix, Whole, Before),
    append(Part, _, Suffix).

This relies on the append_length/4 predicate described in pllib.htm
and present in Quintus library(length).

In fact library(length) includes sublist/[3,4,5],
consistent with substring/[3,4,5].

I don't know that these ever got used.