Taking out the 2nd to last element - Prolog

Question

I'm very new to Prolog and am trying to figure out exactly what is happening with this (function?) that takes out the 2nd to last element in a list.

remove([],[]).
remove([X],[X]).
remove([_,X],[X]).
remove([X|Xs], [X|Ys]) :-
   Xs = [_,_|_],
   remove(Xs,Ys).

I'm familiar with pattern matching, as I've done a little work in SML. The first one is clearly the base case, returning the empty list when we break it down. The second returns the same variable when there is only one left. The third looks as if it returns the last element, disregarding the 2nd to last? As for the inductive case, it will attach the head of the list to the new list if ...... (This is where I get completely lost). Could anyone explain what's happening in this function so I can have a better understanding of the language?

score 3 · Answer 1 · answered Nov 04 '13 at 11:54

Elaborating on CapelliC's explanation:

remove([],[]).

An empty list is an empty list with the second-to-last element removed.

remove([X],[X]).

A single-element list is itself with the second-to-last element removed.

remove([_,X],[X]).

A two-element list with the second to last element removed is a list of one element consisting of the last element of the two-element list.

remove([X|Xs], [X|Ys]) :-
   Xs = [_,_|_],
   remove(Xs,Ys).

The second list is the first list with the second element removed, and share the same first element, IF:

The tail of the first list consists of at least two elements, AND
The tail of the second list is the tail of the first list with the second to last element removed

score 2 · Accepted Answer · answered Nov 04 '13 at 07:09

2

A set of clauses is a predicate, or procedure.

All first three are base cases, and the recursive one copies while there are at least 3 elements in the first list.

I would describe the behaviour like 'removes pre-last element'.

answered Nov 04 '13 at 07:09

CapelliC

59,646
5
47
90

false · Answer 3 · 2022-08-20T08:05:49.537

So, how to declaratively read

remove([X|Xs], [X|Ys]) :-
   Xs = [_,_|_],
   remove(Xs,Ys).

Most important is that you first realize what the :- actually means.

Head :- Body.

It means: Whenever Body holds, we can conclude that also Head holds. Note the rather unintuitive direction of the arrow. It goes right-to-left. And not left-to-right, as often written informally when you conclude something. However, the error points into the direction of what we get "out of it".

To better see this, you can enter Body as a query!

?- Xs = [_,_|_], remove(Xs,Ys).
   Xs = [A, B], Ys = [B]
;  Xs = [A, B, C], Ys = [A, C]
;  ... .

So we get all answers, except those where Xs has less than two elements.

Please note that procedurally, things happen exactly in the other direction - and that is very confusing to beginners. Even more so, since Prolog uses two "non-traditional" features: chronological backtracking, and variables - I mean real variables, meaning all possible terms - not these compile time constructs you know from imperative and functional languages. In those languages variables are holders for runtime values. Concrete values. In Prolog, variables are there at runtime, too. For more to this, see Difference between logic programming and functional programming

There is also another issue, I am not sure you understood. Think of:

?- remove(Xs, [1,2]).
   Xs = [1, A, 2]
;  false.

What is removed here? Nothing! Quite the contrary, we are adding a further element into the list. For this reason, the name remove/2 is not ideal in Prolog - it reminds us of command oriented programming languages that enforce that some arguments are given and others are computed. You might at first believe that this does not matter much, after all it's only a name. But don't forget that when programming you often do not have the time to think through all of it. So a good relational name might be preferable.

To find one, start with just the types: list_list/2, and then refine list_removed/2 or list__without_2nd_last/2.

score 0 · Answer 4 · answered Nov 05 '13 at 00:14

Annotated:

remove( []     , []     ) .  % removing the 2nd last element from the empty list yields the empty list
remove( [X]    , [X]    ) .  % removing the 2nd last element from a 1-element list yields the 1-element list.
remove( [_,X]  , [X]    ) .  % removing the 2nd last element from a 2-element list yields the tail of the 2-element list
remove( [X|Xs] , [X|Ys] ) :- % for any other case...
  Xs = [_,_|_],              % * if the tail contains 2 or more elements, the list is 3 elements or more in length
  remove(Xs,Ys).             % we simply prepend the head of the list to the result and recurse down.

It should be noted that the last clause could re-written a tad more clearly (and a little more succinctly) as:

remove( [X1,X2,X3|Xs] , [X1|Ys] ) :- % for any other case (a list of length 3 or more)
  remove([X2,X3|Xs],Ys).             % we simply prepend the head of the list to the result and recurse down.

Or as

remove( [X1|[X2,X3|Xs]] , [X1|Ys] ) :- % for any other case (a list of length 3 or more)
  remove([X2,X3|Xs],Ys).               % we simply prepend the head of the list to the result and recurse down.

Taking out the 2nd to last element - Prolog

4 Answers4