Lists and Sequence in Prolog
In Prolog, the list builder uses brackets[…]. A list is referred by the notation [A | B] in which, A is the first element, and whose tail is B. The following example shows the three definitions, where the first element of the list is refereed by the ‘car’, the tail of the list is referred by ‘cdr’, list constructor is referred by the ‘cons’.
Where,
- A is the head(car) of [A | B].
- B is the tail(car) of [A | B].
- Put A at the head and B as the tail constructs the list [A | S].
However, the definitions of the above explicit are unneeded. The Prolog team [A|B] refers that A is the head of list and B is its tail. A will bound to the first element of the list, and B will bound to the tail of list if the list can be unified with the team of prolog ‘[A|B]’.
In this section, many of the predicates are built-in for many interpreters of Prolog.
The predicate ‘member/2’ definition is described as follows:
The clauses can be read as follows:
- A is a list member whose first element is A.
- A is a list member whose tail is S if A is a member of S.
We can use this program in many ways. We can also test the membership as follows:
We can also generate the list member as follows:
Here, the following derivation tree is used to show how all of the answers are generated by this last goal.
Each left branch corresponds to a match against the first clause for ‘member’. Each right branch corresponds to a match against the second clause. On the lowest right branch, the subgoal ‘member(A, [])’ will not match any ‘member’ clause head.
Members have many other uses. This example query is as follows:
In the above query, we intend to search to find the elements which are paired with a specified element. In a list, we can find elements in another way, and these elements will satisfy some constraints:
The member definition is written as follows:
The “don’t care” variable is shown by ‘_’ (underscore). The “don’t care” variable is also known as an anonymous variable. In general, anonymous variables have names in which underscore is the first character.
The following definition for ‘takeout’ is related to ‘member’ as follows:
In English, we can paraphrase these clauses as follows:
- The result will be S if A is taken out of [A | S].
- The result will be [A | S] if A is taken out of the tail of [A | S].
For example,
In the definition of ‘takeout’, using any anonymous variables is not appropriate. The consequence of the definition is ‘takeout(3, [1, 2, 3], [1, 2])’ which is shown by following clause tree.
We will get the following goal:
The above example explains that ‘takeout(A, C, X)’ can also be interpreted as “insert A into X to produce C”. We can also define:
The following definition shows the concatenating or appending of two Prolog lists:
Various possible goals are as follows: