Lists from scratch

Lists in Prolog

Lists are defined via two constructors:

• nil, the empty list, containing no elements;
• cons, the constructor taking an element H and a list T, and generating the list cons(H, T).

For instance cons(a, cons(b, cons(c, nil))) represents the list a, b, c. Lists are typical recursive data structures, used to represent sequences of any sort.

Prolog lists

In Prolog, lists are defined via two analogous constructors:

• [] represents the empty list, containing no elements (a constant);
• . stands for cons: it takes an element H and a list T, and generates the list .(H, T) (a functor of arity 2).

The sequence notation simplifies writing lists: .(H, T) can be written as [H|T], and .(H, .(H', T')) as [H, H'|T']. There, the empty list can be omitted. For example [a, b, c] represents the list a, b, c in Prolog, where a is the head of the list and [b, c] is the tail:

mgu([a, b, c], [H|T]) = {H/a, T/[b, c]}

Built-in list syntax

Libraries have list functions that assume you actually use these functors, and the ad-hoc syntax avoids the verbose right-associative construction: write [H1, H2, ..., Hn|T] instead of '.'(H1, '.'(H2, ..., '.'(Hn, T)...)), and [H1, H2, ..., Hn] instead of [H1, H2, ..., Hn|[]]. The forms [H|T], [], [E1, E2], [_|T] and [E1, _|_] are special cases. This is standard syntax we should always use!

Other list predicates exist in the Prolog library: member(Element, List) (similar to our find/element), reverse(List, ReversedList), and many others. Since append/3 is a relation, it also tells you about the shape of its result (file list-syntax.pl):

Computing with lists: recursion

Being recursive data structures, lists are typically handled by recursive rules, which incidentally is also the only way to handle repeated operations over sequences in Prolog, where there is nothing like a cycle programming construct.

The recursion scheme: since Prolog's search strategy is depth-first, in particular with clauses used orderly, top-down, termination is handled with a fact, typically coming before the recursive rule, as already seen for nat/1 and sum/3.

Typical example: member

File lists-member.pl. member/2 checks whether the first argument is a term that is a member of the list in the second argument:

Remarks:

• the search strategy is left to right through the list;
• it finds out all the members of the list (member(X, [a, b, c]));
• conditional membership: given a certain computed substitution (blue(X) only selects the blue elements);
• generation of lists: member(z, X) enumerates every list that has z in it, with the position of z growing one by one.

Lists with cons and nil

File element.pl. Now the same ideas with the cons/nil construction: functors cons/2 (with head and tail as arguments) and nil/0 for the empty list, e.g. cons(a, nil) and cons(a, cons(b, nil)). Note that they are trees. Functions and predicates are generally implemented by matching, through different clauses: recursive functions have their base cases as facts, followed by the recursive rules.

How to read the specification in the relational interpretation: E is found in a list with head E; E is found in a list with tail T provided E is found in T.

The resolution tree of element(b, cons(a, cons(b, cons(c, nil)))):

element(b, cons(a, cons(b, cons(c, nil))))
└── element(b, cons(b, cons(c, nil)))
    ├── Yes
    └── element(b, cons(c, nil))
        └── element(b, nil)
            └── No

The first branch gives the solution; the exploration then continues (backtracking) and ends in a failure at nil.

Programming find, position, concat and count

File lists.pl:

Expressiveness so far. The language is now conceptually complete: we can implement a variety of algorithms to search, clone and modify algebraic-like data structures. The next features to add: more convenient ways to work with numbers (primitive values) and with lists, library functions to manipulate terms, and library functions to tweak resolution.

The same predicates over [H|T] lists

File find-position.pl. With the standard syntax, find, position and join read much better. (join is similar to append.)