10.1 Introduction

In this chapter, we begin our look at view definitions involving constructors and compound terms. The examples here concern the representation of information about lists and trees and sets. In the chapters that follow, we look at the representation of information about dynamic systems and the representation of metaknowledge (i.e. information about information).

10.2 Lists

A list is a finite sequence of objects. Lists can be flat, e.g. [a, b, f(c), d]. Lists can also be nested within other lists, e.g. [a, [b, f(c)], d].

To talk about lists of arbitrary length, we use the binary constructor cons, and we use the symbol nil to refer to the empty list. In particular, a term of the form cons(τ₁, τ₂) designates a list in which τ₁ denotes the first element and τ₂ denotes the rest of the list.

For example, using this approach, we can represent the list [a, b, c] with the compound term shown below.

Rules defining primitives and lists.

The advantage of this representation is that it allows us to describe relations on lists without regard to length or depth.

As an example, consider the definition of the binary relation mem, which holds of an object and a list if the object is a top-level mem of the list. Using the constructor cons, we can characterize the mem relation as shown below. Obviously, an object is a mem of a list if it is the first element; however, it is also a mem if it is mem of the rest of the list.

In similar fashion, we can define other relations on lists. For example, the following rules define a relation called app. The value of app (its last argument) is a list consisting of the elements in the list supplied as its first argument followed by the elements in the list supplied as its second. For example, we would have app(cons(a,nil), cons(b, cons(c, nil)), cons(a, cons(b, cons(c, nil)))).

Finally, a note on syntax. There are three ways to write lists - using square brackets, using cons, and using the ! operator.

If we know all of the elements of a list, we can write the list by wrapping the elements in square brackets and separating them with commas, as in the example shown below.

This list can also be represented using the cons constructor, as shown below.

In order to abbreviate the representation of lists, we can alternatively use the ! operator in place of cons. For example, we would write the list just discussed as shown below.

All three of these representations are equivalent. In fact, they typically parse into the same internal representation. However, they each have value in different circumstances, and so all three are permitted.

Lists are an extremely versatile representational device, and the reader is encouraged to become as familiar as possible with the techniques of writing definitions for relations on lists. As is true of many tasks, practice is the best approach to gaining skill.

10.3 Example - Sorted Lists

A sorted list is a list in which successive elements satisfy a given ordering relation. For example, the list [1,2,3] is a sorted list with "less than" as the ordering relation, while [1,3,2] is not.

Note that it is common for objects to appear more than once in a sorted list. For example, [1,2,2,3] is a sorted list with "less than or equal" as the ordering relation. However, this cannot happen if the ordering relation is not reflexive. For example, [1,2,2,3] is not a sorted list with "less than" as the ordering relation.

Given an ordering relation (e.g. the "less than or equal" relation leq), we can easily define a predicate sorted that is true of sorted lists and false of everything else. See below. The empty list is sorted. Any list of one element is sorted. A list of two or more elements is sorted if the first element is less than or equal to the second and the tail of the list is sorted.

As with unsorted lists, we can define relations on sorted lists as well. However, in doing so we must ensure that the resulting lists are sorted. Although the app relation defined earlier can be applied to sorted lists, the result may not be sorted.

One way to deal with this is to apply a sorter to a list to ensure that it is sorted. For example, the following view definition defines a sorting relation sortappend in terms of app and sort.

This approach works, and it yields the correct answer (even when the input lists are not sorted). However, if we know that the input lists are sorted, it is possible to define a sorting relation in another way.

For many people, this version is more appropriate than the version above. Moreover, as we shall see when we get to program execution, it may execute more efficiently than the preceding version.

10.4 Example - Sets

A set is a collection of objects. A set differs from a list in two ways. (1) Objects can appear in lists more than once whereas this cannot happen in a set. (2) The order of elements in a list is essential whereas order is irrelevant for sets.

In what follows, we represent sets as ordered lists. Since order is irrelevant in a set, it does not matter which order we choose, and keeping things ordered makes it easier to define certain relations on sets; and, as we shall see in later lessons, it makes query answering more efficient.

If we represent sets as lists, we can see whether an object is a member of the set using the mem relation defined earlier. However, if we represent sets as ordered lists, there is a better way. See below.

As with the definition of list membership, this version loops through the elements of the set. Also, if we get to a subset with the object as the first element, then we terminate successfully. The main difference here is that we can sometimes stop early if an object is not an element of the set. In particular, if, in looping through sublists of the sublist, we get to a sublist in which the specified object is less than the first element, then we can stop searching since we know that all subsequent objects in the list are greater than that element.

One set is a subset of another if and only if every element of the first set is an element of the second. We can define the subset relation as shown below.

The intersection two sets is the set consisting of all objects that appear in both sets.

The union of two sets is the set consisting of all elements in either set. If we represent sets as sorted lists, then union is identical to the merge relation defined earlier.

10.5 Example - Trees

The cons relation can also be used to represent arbitrary trees. For example, cons(cons(a,b),cons(c,d)) represents a binary tree with a, b, c, and d as leaves.

The among relation is true of an object and a tree if the object is appears somewhere in the tree.

Note that, if the specified object is itself a tree, this relation is the same as the subtree relation on trees.

Exercises

Exercise 10.1: Say whether each of the following sentences is in the extension of the app relation defined in Section 10.2.

Exercise 10.2: last is a binary relation that holds of an object and a list if and only if the specified object is the last element of the specified list. For example, last(c,[a,b,c]) is true. Write a logic program that defines the last relation.

Exercise 10.3: rev is a binary relation on lists. The relation holds of two lists if and only if the second contains the same elements as the first except in the opposite order. For example, rev([a,b,c],[c,b,a]) is true. Write a logic program that defines the rev relation. Hint: It helps to define a variation on app and then use that variation in defining rev.

Exercise 10.4: delete is a ternary relation that holds of an object and two lists if and only if the second list is a copy of the first list with all occurrences of the given object deleted. For example, delete(b,[a,b,c,b,d],[a,c,d]) is true. Write a logic program that defines the delete relation.

Exercise 10.5: substitute is a 4-ary relation that holds of two objects and two lists if and only if the second list is a copy of the first list with all occurrences of the second object replaced by the first object. For example, substitute(b,d,[a,d,d,c],[a,b,b,c]) is true. Write a logic program that defines the substitute relation.

Exercise 10.6: adjacent is a ternary relation that holds of two objects and a list if and only if the first object and the second object are adjacent to each other in the specified list. For example, adjacent(b,c,[a,b,c,d]) is true. Write a logic program that defines the adjacent relation.

Exercise 10.7: sublist is a binary relation that holds of two lists if and only if the first list is a contiguous sublist of the second. For example, sublist([b,c],[a,b,c,d]) is true while sublist([b,d],[a,b,c,d]) is not. Write a logic program that defines the sublist relation.

Exercise 10.8: sort is a binary relation that holds of two lists if and only if the second list is a version of the first in sorted order. For example, sort([2,1,3,2],[1,2,2,3]) is true. Write a logic program that defines the sort relation in terms of min.

Exercise 10.9: powerset is a binary relation that holds of two sets if and only if the second set is the powerset of the first set, i.e. the second is the set of all subsets of the first set. For example, powerset([a,b],[[],[a],[b],[a,b]]) is true. Write a logic program that defines the powerset relation.