| The combination of the list data structure and the ability to define recursive rules allows you to create several highly reusable algorithms. All the Logikus programs in this chapter are included in this book's CD in .txt files. You can open these files with any editor and copy and paste them into your own programs. 13.10.1 Member The member program is probably the most fundamental and most reused algorithm in logic programming. The program (from file member.txt ) is member(X, [X Rest]); member(X, [Y Rest]) :- member(X, Rest); Figure 13.7 shows this program in use. Figure 13.7. The member program. The query uses the classic logic program member to extract chess champs of the late 20th century from a list.  A high-level description of the member program is that an element is a member of a list if it heads the list or if it is a member of the tail of the list. A closer analysis of the logic of the member program is as follows . The first rule states that a variable is a member of a list if it heads the list. When the query in the example proves itself, it unifies with the first rule of the program. This results in success, with the variable in the query unifying with the first element of the list, spassky . When the query tries to find another proof, it asks the first rule for another proof, but there is none. The query then unifies with the second rule and tries to prove it by proving its second structure, which is member(X, Rest) . This structure proves itself in exactly the same way the query structure did. It uses the first rule to find the head of Rest and the second rule to find members of the list after its head. This recurses until the list is empty, and both rules fail. 13.10.2 Prefix A prefix of a list is another list whose elements equal the initial elements of the first list. For example, [] and [merlin] are two prefixes of [merlin, prospero, gandalf, harry] The following program finds all the prefixes of a list: prefix([], List); prefix([X Rest1], [X Rest2]) :- prefix(Rest1, Rest2); Figure 13.8 shows a query that applies this program to a list of wizards. Figure 13.8. The prefix program. The query asks for all prefixes of a list of wizards.  The second rule of prefix declares that one list is a prefix of another if their heads are the same ( X ) and the first list's tail is a prefix of the second list's tail. 13.10.3 Suffix The suffix algorithm uses the same concepts as the prefix algorithm. /* usage: suffix(SuffixList, LongerList) */ suffix(List, List); suffix(List1, [X Rest]) :- suffix(List1, Rest); 13.10.4 Permutation One list is a permutation of another list if it contains the same elements in any order. Figure 13.9 shows a permutation algorithm applied to a list of errands. Figure 13.9. A permutation algorithm. The query uses the permutation algorithm to find possible sequences for completing a list of errands.  The file permutation.txt includes the select algorithm, whose rules are select(X, [X Rest], Rest); select(X, [Y Rest1], [Y Rest2]) :- select(X, Rest1, Rest2); These rules separate a list into two parts : an element extracted from the list, and the remainder of the list. The select algorithm works by declaring that X is a selectable element of a list if X heads the list or if X is selectable from the tail of the list. Here is the permutation algorithm: permutation(InList, [H OutRest]) :- select(H, InList, InOther), permutation(InOther, OutRest); permutation([], []); This algorithm declares that an output list is a permutation of an input list if the output is an element of the input, followed by a permutation of the remainder of the input. This rule recurses, finding permutations of an ever-smaller list, until finally it asks whether an empty list is a permutation of itself, which the second rule supports. | 
