6.8 - Example - Linked lists - Relational logic - [introduction to logic] by michael genesereth

A list is a finite sequence of objects. This can be flat like the first list shown here. This can also be nested within other lists, as in our second example. A linked list is a way of representing nested lists of variable length. Each element is represented by a cell containing two items. First item is either an object or a nested list, The second item is either empty or is the remainder of the list. For example, the structure shown here is a linked list representation of our nested list. Our goal in this example is to formalize linked lists and to define some useful relations on such structures. First step, is representation. To talk about linked lists, we use the binary function constant, cons, and we use the object constant, nil, to refer it to the empty list. With this function constant and the object constant, we can encode the list a, b, c, d as shown here. Cons of a on two, Cons of b on two, Cons of c on two, Cons of d on two nil. Where signature for this example consists of some object constants, let's say, a, b, c, and d to denote atomic elements and a single object constant nil to represent the empty list. We have a single binary function constant, cons, and we define three relation constants, member, among, and opend. Start with a number relation. This holds an object in a list if an object is a top level member of the list. For example, ,, is a member of the list consisting of a, and b, and c. Using the function constant cons, we can define the member relation as shown here. The first sentence states that an object is a member of a list if it's the first member. Okay, That's obvious. The second sentence states that an object is a member of the list if it's a member of re-, lest, rest of the list. Good. Now, let's look at concatenation. Result of concatenating or pending the lists ab and cd would be the single list a, B, c, d. Once again, our definition consists of two sentences. The first sentence says that appending empty list to any list results in that list. Second sentence says that appending list with x as first element and y as a remainder to a list z, results in the list with x as first element and a remainder being the result of appending y to z. But noting that there is a similarity to in this that definition and the definition plus in Peano arithmetic. Here we have an identity nil, instead of zero, and here we have cons instead of s, whatever the definitions are structurally very similar. You can also define relations that depend on the structure of the elements of a list. For example, the among relation is true of an object and a list, if the object is the list itself, if it's a member of the list, if it's a member of a member of the list, and so forth. The example shown here, c is not a member of the list itself supplied the ones that will tied the second argument but it is among that list because it is a member of the second element of that list. The main lesson to be learned from this example is the use of binary functions in defining complex data structures. Also, unless they're an extremely versatile representational device. And it's good to become familiar as possible with the techniques of writing definitions for functions and relations on lists. That's as true of many tasks, practice is the best approach to gaining this skill.