CODEWITHSUNDEEP
listprologelement
Pervy Sage
Pervy Sage

Reputation: 37

Is there a way to select only the first and last element of a list in PROLOG?

I am trying to write a predicate that will be true if X is a sublist of Y, without taking into account the first term and the last term of Y. For example, query listWithinList([b,c,d],[a,b,c,d,e]) would return True, but query listWithinList([b,c,d,e],[a,b,c,d,e]) would yield False because e, the last element of Y, should not be part of X.

Currently I have listWithinList(X,Y):-append(_,Y2,Y), append(X,_,Y2). but I am not sure how to change the code so that it does the same trick but without taking into account the first and last term of Y.

Upvotes: 3

Views: 1124

Answers (4)

false
false

Reputation: 10102

Grammars are very intuitive for such tasks. Just describe what we have:

list_within(Xs, Ys) :-
   phrase(( [_First], seq(Ys), [_Last] ), Xs).

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

That is, first the element _First, then the sequence Ys, and finally the element _Last.

Upvotes: 2

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

When you write _ in an argument to append, it refers to an arbitrary list. So arbitrary that its length is arbitrary too.

For example:

?- append(_, Suffix, [a, b, c]).
Suffix = [a, b, c] ;
Suffix = [b, c] ;
Suffix = [c] ;
Suffix = [] ;
false.

Here _ can stand for any of the lists [], [a], [a, b], [a, b, c]. But I don't need to tell you this. Prolog can tell you this if you give the anonymous variable _ a proper name instead:

?- append(Prefix, Suffix, [a, b, c]).
Prefix = [],
Suffix = [a, b, c] ;
Prefix = [a],
Suffix = [b, c] ;
Prefix = [a, b],
Suffix = [c] ;
Prefix = [a, b, c],
Suffix = [] ;
false.

In contrast, the term [_] stands not for an abitrary list. It stands for a list that definitely has exactly one element. That element (denoted _) is arbitrary.

For example:

?- append([_], Suffix, [a, b, c]).
Suffix = [b, c].

Or, again, with a proper variable name so we can see the binding:

?- append([X], Suffix, [a, b, c]).
X = a,
Suffix = [b, c].

All this is to say that the definition from the question:

listWithinList(X,Y):-append(_,Y2,Y), append(X,_,Y2).

Is close to being correct. But the two uses of _ don't "remove" one element each. They "remove" an arbitrary number of elements each. So you don't just get the middle of the list:

?- listWithinList(Middle, [a, b, c, d, e]).
Middle = [] ;
Middle = [a] ;
Middle = [a, b] ;
Middle = [a, b, c] ;
Middle = [a, b, c, d] ;
Middle = [a, b, c, d, e] ;
Middle = [] ;
Middle = [b] ;
Middle = [b, c] ;
Middle = [b, c, d] ;
Middle = [b, c, d, e] ;
Middle = [] ;
Middle = [c] ;
Middle = [c, d] ;
Middle = [c, d, e] ;
Middle = [] ;
Middle = [d] ;
Middle = [d, e] ;
Middle = [] ;
Middle = [e] ;
Middle = [] ;
false.

If we want to "remove" lists of exactly one element from the front and the back, we must write [_]:

listWithinList(X, Y) :-
    append([_], Y2, Y),
    append(X, [_], Y2).

This now behaves like this:

?- listWithinList(Middle, [a, b, c, d, e]).
Middle = [b, c, d] ;
false.

Additionally, note the difference between [_] and [_|_]. The former stands for a list of exactly one element. The latter stands for a list of one or more elements. In this case you don't want to "remove" more than one element, so using [_|_], like one of the other answers suggests, is absolute nonsense.

Finally, Prolog can suggest a further simplification to us:

?- append([X], Xs, Ys).
Ys = [X|Xs].

Appending a one-element list [X] and an arbitrary list Xs gives a list that we can also write as [X | Xs] without using append. So one of the append calls is not needed. I might write this predicate like this:

list_middle(List, Middle) :-
    append([_First | Middle], [_Last], List).

And use it like this:

?- list_middle([a, b, c, d, e], Middle).
Middle = [b, c, d] ;
false.

Or like this:

?- list_middle(List, [1, 2, 3]).
List = [_2658, 1, 2, 3, _2664].

Upvotes: 6

Reema Q Khan
Reema Q Khan

Reputation: 878

Here is my approach:

First: Create all combinations of the List that are acceptable when the first letter is removed and last letter is removed.

listWithinList(M,L):-
    append([_|_],L2,L),
    append(S,[_|_],L2),

The first append removes the first element from the list, and the second append removes the last element from the list. The combinations of List are stored in S.

Second: We use the same predicate to check if M is same as any of the combinations in S.

same(L1,L2):-
    L1==L2.

Putting the code together:

listWithinList(M,L):-
        append([_|_],L2,L),
        append(S,[_|_],L2),
        ( same(M,S)->write(S),
        write('This combination is correct.') ).   
    same(L1,L2):-
        L1==L2.

Examples:

    ?-listWithinList([b,c,d],[a,b,c,d,e]).
    [b, c, d]This combination is correct.
    1true
    false

    ?-listWithinList([b,c,d,e],[a,b,c,d,e]).
    false
    
    ?-listWithinList([a,b,c,d,e],[a,b,c,d,e]).
    false

Upvotes: -2

coredump
coredump

Reputation: 38799

Due to how lists are represented in Prolog, you can easily remove the first element by destructuring it as its head and tail, and unifying the result with tail, as follows:

tail([_|L], L).

On success, the predicates unifies the second parameter with the tail of the first.

To remove the last element, you can say that your input list is the result of appending a prefix to a list of one element (whose value is not important):

butlast(List, Prefix) :-
  append(Prefix, [_LastValue], List).

You can combine them both to remove both extremities:

chop(List, Middle):
  tail(List, Tail),
  butlast(Tail, Middle).

Upvotes: 0

Related Questions