Getting the second element of a list in Prolog

11,867

Solution 1

You can move unification into the head of the clause and simply write:

second([_, Second| _], Second).

The notation for lists is to write the initial elements separated by commas and then a vertical bar to separate the list tail, i.e. the list containing the rest of the elements. Some examples that you can try at the Prolog top-level interpreter should make it more clear:

?- [1, 2, 3] = [Head| Tail].
Head = 1,
Tail = [2, 3].

?- [1, 2, 3] = [First, Second| Tail].
First = 1,
Second = 2,
Tail = [3].

?- [1, 2, 3] = [First, Second, Third| Tail].
First = 1,
Second = 2,
Third = 3,
Tail = [].

Solution 2

[verbose mode ON]

A list in Prolog is either the empty list [] or a head and a tail, which is technically represented by the "dot" functor, '.'(H,T) in Prolog, but Prolog offers a syntactically friendlier representation, [H|T]. The head, H is an element, and the tail, T is itself a list. If you look at LISP, these are the car and the cdr, respectively, of the list. In Prolog, the vertical bar | separates the head from the tail.

At the Prolog prompt, you can enter X = '.'(H,T). and see what you get:

| ?- X ='.'(H,T).

X = [H|T]

yes
| ?-

If you have a list of one element, it would be [X], but technically is [X|[]] or '.'(X,[]). If you have a list of two elements, it could be written:

[X,Y]
[X|[Y]]
'.'(X,[Y])
[X|'.'(Y,[])]
'.'(X,'.'(Y,[]))

All of these forms work, but the most common form would be [X,Y] or, depending upon context, [X|[Y]] if you needed head/tail representation. It would be rare that you would need to use the dot notation.

In the syntactically friendly (non-dot) form, a non-empty list can be represented by one or more discrete head elements, followed, optionally, by a tail (the tail being designated after the vertical bar, |), which itself could be a list or the empty list []. A list of many elements, E1, E2, ..., En could be written in many ways, generalizing the above idea:

[E1,E2,...,En]
[E1|T]                   % T = [E2,E3,...,En]
[E1,E2|T]                % T = [E3,E4,...,En]
[E1,...,Ek|T]            % T = [Ek+1,Ek+2,...,En]
[E1|[E2|T]]              % T = [E3,E4,...,En]
[E1|[E2|...[Ek|T]]...]]  % T = [Ek+1,Ek+2,...,En]

So two vertical bars (|) don't make sense in the form [X|Y|T] but they do in the form, [X|[Y|T]]. Since the tail, T is itself a list (or []), it follows all the same rules of representation as the original list. So the list is, by nature, a structure that lends itself to recursion. Many predicates in Prolog that operate on lists do so recursively by operating on the head, and then calling itself on the tail, and ending when it sees the empty list, [].

If I unify two lists, L1 = L2, and I want it to succeed, then (1) the lists would need to be the same length, and (2) each element in L1 must be unifiable with it's corresponding element in L2. So if I do this at the Prolog prompt:

| ?- [X,2,Z] = [1,Y,3].

X = 1
Y = 2
Z = 3

yes
| ?-

I have successful unification with the values shown for the variables. I could also do this:

| ?- [X|T] = [1,2,3,4].

T = [2,3,4]
X = 1

yes
| ?-

Prolog can unify the two lists if X is instantiated with 1 and the tail, T is instantiated with [2,3]. I can also do this:

| ?- [X,Y|T] = [1,2,3,4].

T = [3,4]
X = 1
Y = 2

yes
| ?-

As Paolo points out, this shows how you can get at the second element. You could also do it this way:

| ?- [X|[Y|T]] = [1,2,3,4].

T = [3,4]
X = 1
Y = 2

yes
| ?-

It really means the same thing, just looked at with a different syntax: the second element is the head of the tail of the list (or, in LISP, "the car of the cdr").

Share:
11,867
Eigenvalue
Author by

Eigenvalue

Updated on June 04, 2022

Comments

  • Eigenvalue
    Eigenvalue over 1 year

    Having some trouble with this task.

    Currently I have tried this, which I know is wrong because I'm not sure how to divide L into its head and tail, however this is sort of the idea im going for.

    second(L,E) :- [H | E | T]
    

    Which I think of that E has to be after the head which would make it the second element. However I'm new to this language and would like some insight. How do I get this head and tail from L the way the predicate is written. Some insight of this problem would be much appreciated. Thank you.