CHAPTER 7    Lists and Recursion

 

List processing--handling objects that contain an arbitrary number of elements--is a powerful technique in Prolog. In this chapter, we explain what lists are and how to declare them, then give several examples that show how you might use list processing in your own applications. We also define two well-known Prolog predicates--member and append--while looking at list processing from both a recursive and a procedural standpoint.

After that, we introduce findall, a Visual Prolog standard predicate that enables you to find and collect all solutions to a single internal goal. We round out this chapter with a discussion of compound lists--combinations of different types of elements--and an example of parsing by difference lists.

 

What Is a List?

In Prolog, a list is an object that contains an arbitrary number of other objects within it. Lists correspond roughly to arrays in other languages, but, unlike an array, a list does not require you to declare how big it will be before you use it.

There are other ways to combine several objects into one, of course. If the number of objects to be combined is known in advance, you can make them the arguments of a single compound data structure. And even if the number of objects is unpredictable, you can use a recursive compound data structure, such as a tree. But lists are usually easier to use because the language provides a concise notation for them.

A list that contains the numbers 1, 2, and 3 is written as

    [ 1, 2, 3 ]

Each item contained in the list is known as an element. To form a list data structure, you separate the elements of a list with commas and then enclose them in square brackets. Here are some examples:

    [dog, cat, canary]
    ["valerie ann", "jennifer caitlin", "benjamin thomas"]

1. Declaring Lists

To declare the domain for a list of integers, you use the domains declaration, like this:

    DOMAINS
        integerlist = integer*

The asterisk means "list of"; that is, integer* means "list of integers."

Note that the word list has no special meaning in Visual Prolog. You could equally well have called your list domain zanzibar. It's the asterisk, not the name, that signifies a list domain.

The elements in a list can be anything, including other lists. However, all elements in a list must belong to the same domain, and in addition to the declaration of the list domain there must be a domains declaration for the elements:

    DOMAINS
        elementlist = elements*
        elements    = ....

Here elements must be equated to a single domain type (for example: integer, real, or symbol) or to a set of alternatives marked with different functors. Visual Prolog does not allow you to mix standard types in a list. For example, the following declarations would not properly indicate a list made up of integers, reals, and symbols:

    elementlist = elements*
    elements =  integer; real; symbol                 /* Incorrect */

The way to declare a list made up of integers, reals, and symbols is to define a single domain comprising all three types, with functors to show which type a particular element belongs to. For example:

    elementlist = elements*
    elements = i(integer); r(real); s(symbol)
                                   /* the functors are i, r, and s */

(For more information about this, refer to "Compound Lists" later in this chapter.)

(1) Heads and Tails

A list is really a recursive compound object. It consists of two parts: the head, of list which is the first element, and the tail, which is a list comprising all the subsequent elements. The tail of a list is always a list; the head of a list is an element. For example,

the head of [a, b, c] is a
the tail of [a, b, c] is [b, c]

What happens when you get down to a one-element list? The answer is that

the head of [c] is c
the tail of [c] is []

If you take the first element from the tail of a list enough times, you'll eventually get down to the empty list ([ ]).

The empty list can't be broken into head and tail.

This means that, conceptually, lists have a tree structure just like other compound objects. The tree structure of [a, b, c, d] is

Further, a one-element list such as [a] is not the same as the element that it contains because, simple as it looks, [a] is really the compound data structure shown here: