Enumerating a sublist with prolog

Question

I'm trying to write a prolog program that behaves in the following fashion: it enumerates all possible consecutive (I'm not sure if that is the proper phrase, i.e. [a,c] is not a sublist of [a,b,c]) sublists, the length of the sublist, the distance from the first element of the proper list to the first element of the sublist and the distance from the last element of the sublist to the last element of the proper list. So input/output would ideally look something like:

| ?- sublist([a,b], SubList, Before, Len, After).
    SubList= [], After = 2, Before = 0, Len = 0 ? ;
    SubList= [a], After = 1, Before = 0, Len = 1 ? ;
    SubList= [a,b], After = 0, Before = 0, Len = 2 ? ;
    SubList= [], After = 1, Before = 1, Len = 0 ? ;
    SubList= [b], After = 0, Before = 1, Len = 1 ? ;
    SubList= [], After = 0, Before = 2, Len = 0 ? ;

So far I can output the sublists properly, and output their lengths, like so:

sublist(L,S,Len) :-
    append(_,L2,L), %getting sublist
    append(S,_,L2), %getting sublist
    length(S,Len).  %getting length of sublist

but I'm having trouble figuring out how I might keep track of 'Before' and 'After'. It seemed like a (perhaps sneaky?) way of doing it would be to start B at -1 and increment 'Before' by 1 every time a [ ]-valued sublist is encountered (since encountering [ ] means that the the head has been removed and now we're starting over with just the tail), and once you have 'Before', 'After' would just be ([the length of the input list] - 'Before' - [the length of the sublist]). Unfortunately, I am at a complete loss as to how I might go about incrementing 'Before'. Any thoughts? Thanks so much! :)

aioobe aioobe · Accepted Answer · 2012-03-13T19:08:59

So far I can output the sublists properly, and output their lengths, like so [...]

You almost got it.

Just bind the prefix and suffix to variables, and make sure the length of the prefix is Before and the length of the suffix is After:

sublist_lengths(L, SubList, Before, Len, After) :-
    append(PrefSub, Suffix, L),
    append(Prefix, SubList, PrefSub),
    length(SubList, Len),
    length(Prefix, Before),
    length(Suffix, After).

Enumerating a sublist with prolog

1 Answers