5. Lists

Lists

A very important type of recursive structure is the list. The recursive definition of a list is: a list may be empty or it may be a term which has a head, which can be any term, and a tail which is another list. We write the empty list as [].

Let's define a predicate, is_a_list, which succeeds if its argument is a list:

is_a_list([]).
is_a_list(list(Head, Tail)) :-
    is_a_list(Tail).

All we have done here is to write a predicate which tests whether a particular term is a list or not.

Using our definition, a list of numbers [a, b, c] would be written using the notation:

list(a, list(b, list(c, [])))

How would the following lists be represented using the list(_,_) notation?

[a] 
[]
[[a, b], c]

Create a new Prolog program called lists.pl and add the predicate is_a_list. Try the following queries...

?- is_a_list([]).
?- is_a_list(list(a, [])).
?- is_a_list(list(a, b)).
?- is_a_list(a).

Explain how Prolog arrived at the results for each query.

Although this notation is consistent with the way Prolog treats all other data structures, it can be rather clumsy at times. Because lists are used so often, standard Prolog implementations use the alternative, more convenient notation, [1, 2, 3]. Internally, Prolog still stores the list as if it were entered in the prefix form. To get some idea of how the compact list notation works we'll look at some queries and their responses. First try this one:

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

This query asks Prolog to match (or unify) the two terms on either side of the equals sign. If a variable appears in a position corresponding to an element in the second list then that variable is unified with the element.

Prolog also has a convenient notation for extracting the head and tail from a list. The vertical bar (|) is used to separate the head from the tail. Try the following query:

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

Try the following queries and explain the results.

 ?- [1, 2, 3, 4, 5, 6] = [Head | Tail].
 ?- [1, 2] = [Head | Tail].
 ?- [1] = [Head | Tail].
 ?- [] = [Head | Tail].
 ?- [Head | Tail] = [[1, 2], [3, 4, [5, 6]], [7, 8], 9].
 ?- What = [a | [b, c, d]].
 ?- What = [a | [b]].
 ?- What = [[a] | [b]].
 ?- What = [a | b].

Standard Prolog has a built-in predicate , member, which operates in a way similar to is_member above. However (depending on which version of SWI-Prolog you are using) member might only work on [...]-style lists (just as is_member only works on list(...)-style lists). Repeat the membership queries using member:

?- member(1, [1, 2, 3]).
 ?- member(3, [1, 2, 3]).
 ?- member(5, [1, 2, 3]).
 ?- member([], [1, 2, 3]).

Write a recursive predicate, cons, to concatenate two lists.

?- cons([1, 2, 3], [4, 5, 6], Result)?
 Result = [1, 2, 3, 4, 5, 6]

n an earlier exercise we wrote a predicate, descendant, in the family.pl program. Reload that program and test the predicate to remind yourself how it works.

% swipl -s family.pl
?- descendant(Albert, Descendant).

This query shows all the descendants of Albert.

Prolog provides a predicate, findall, to put all the responses from such a query into a Prolog list. Try the following:

 ?- findall(D, descendant(Albert, D), List).

The first argument is a variable which is used temporarily to indicate what should be put in the list (third argument) when solutions are found to the goal (second argument).

Use findall to write a new predicate, children(Parent, ChildList), where ChildList is the list of children of Parent. Then test the new predicate. For example:

?- children(irene, Children).
Children = [jim, peter]

?- children(peter, Children).
Children = [lee, sandra, james, kate, kyle]

?- children(lee, Children).
Children = []

Advanced Exercise

In an earlier advanced exercise we wrote a predicate, siblings(Child1, Child2), to return whether two people are brothers or sisters. Write a new predicate, sibling_list(Child, Siblings), which returns a list of the Child's siblings. Test the new predicate...

?- sibling_list(sandra, Siblings).
Siblings = [lee, james, kate, kyle]

?- sibling_list(jim, Siblings).
Siblings = [peter]

?- sibling_list(brian, Siblings).
Siblings = [darren]

You will need to deal with the problem of duplicated siblings!