Structured Data: Lists

Matching Lists
Predicates Over Lists

There is one form of structure that has its own special syntax. It is the list. The list is usually used where some data value or argument to a predicate has a variable number of components. The special functor is ``.'' and it takes 2 arguments:

      .(1, .(2, .(3, .(4, []))))

It can be pictured as a tree structure:

$\psfig{figure=struct2.eps}$

If the second argument of the functor is another ``.'' functor or [] then the list can be written as a sequence of terms of any length enclosed in [...].

      [1, 2, 3, 4]

other examples are:

      [ apple, pear, banana, plum] 
      [1,3,5,7,9] 
      ['fred bloggs', 'jim white', 'tom cobbley'] 
      [[1],[1,2],'hello']

A list with no elements in it is called the empty list and is written as:

[]

Matching Lists

If the list is an argument of a predicate the whole list can be matched by a variable or any element of the list can be matched by variables or constants. (The equal predicate forces a match of both its arguments):

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

      | ?- [A,B,3] = [1,2,3].
      A = 1       B = 2

There is a special pattern that allows the initial element(s) and the remaining elements of the list to be matched:

      | ?- [H|T] = [a, b, c, d].
      H = a 
      T = [b, c, d]

      | ?- [44|REST] = [X,10,11,12,13].
      X = 44 
      REST = [10,11,12,13]

This operator or pattern is useful as it allows lists to be processed element by element using recursive rules by repeatedly matching the head item of a list, processing it and then applying the rule to the tail of the list.

Predicates Over Lists

For example a predicate to describe that the result of joining 2 lists together is a third list:

      | ?- append([1,2],[3,4,5],[1,2,3,4,5]).
      yes

      | ?- append([fir,pine,spruce],[cypress,yew],X).
      X = [fir,pine,spruce,cypress,yew]
      | ?-append([],[a,b,c],Y).
      Y = [a,b,c]

      | ?-append(A,B,[1,2,3]).
      A = [] 
      B = [1,2,3];

      A = [1]
      B = [2,3];

      A = [1,2] 
      B = [3] ;

      A = [1,2,3] 
      B = []

There are two rules that define this relationship, the first states that the result of adding the empty list to any list is the same as that list. The second rule states that if lists A and B when appended give R then appending [X|A] to B will be [X|R].

      append([],L,L).  
      append([X|A],B,[X|R]) :- append(A,B,R).

Another simple predicate over lists is remove which gives as third argument the list that results from removing all occurrences of its first argument from the second argument list:

      | ?- remove(3,[1,2,3,1,2,3],[1,2,1,2]).
      yes
      | ?- remove(dick,[tom,dick,harry],L).
      L = [tom,harry]

This can be defined by the 3 rules:

      remove(X,[],[]).  
      remove(X,[X|L1],L2) :- remove(X,L1,L2).  
      remove(X,[Y|L1],[Y|L2]) :- 
                    not X=Y, remove(X,L1,L2).

A further predicate over lists of numeric values is ``ordered'' which is true if the list is in ascending order and fails otherwise. Note the of one element is ordered and all longer lists are ordered if the first 2 elements are in order and the tail of the list (all but the first element) are in order.

      ordered([X]).  
      ordered([A,B|T]) :- A <= B, ordered([B|T]).

Another example involving simple arithmetic aswell is the relationship between a list and its length:

      length([],0).  
      length([_|T],N) :- length(T,N1), N is N1 + 1.

Next: An Example Up: A goal directed programming Previous: Arithmetic

Page generated: 2002-11-04 by Bob Dickerson

Disclaimer