Prolog Practice Predicates
Fall 2011, David Matuszek

Write and test the following Prolog predicates. Do not turn them in. These are practice for an upcoming Prolog quiz.

member(Thing, List)

Succeeds if the Thing occurs in the List, fails otherwise.
Remember the declarative nature of Prolog. What will member(X, [a, b, c]) do? or member(abc, X)?

last(NonemptyList, Thing)

Thing is the last value in the NonemptyList.

last([1, 2, 3], X). should unify X with 3, and last([1, 2, 3], 3). should succeed without unifying anything. However, what do you think last(X, 3). would or should do? (Hint: There are multiple answers.)  

extend(List, Value, LongerList)

LongerList is like List, but with one extra Value at the end. Or: List is like LongerList, but is missing the last Value.

atomsof(List, ShorterList)

ShorterList is like List, except that it has no sublists, only "atoms." (You can check if X is an atom with atomic(X)).

setof(List, Set)

Set is a set of all the things in List--that is, Set has no duplicated values.

reverse(List1, List2)

List1 and List2 have the same top-level elements, but in the reverse order. Note: Sublists are not reversed, so reverse([a,[b,c,d],e], [e,[b,c,d],a]).

reverseall(List1, List2)

List1 and List2 are complete reversals of each other. Sublists B reversed, so reverseall([a,[b,cat,dog],e], [e,[dog,cat,b],a]).

remove(Thing, List,ShorterList)

ShorterList is like List, except that it has no top-level occurences of Thing in it.

removeall(Thing, List,ShorterList)

ShorterList is like List, except that it has no occurences of Thing anywhere at all inside it, at any level.

collapse(List, FlatList)

FlatList contains all of the atoms of List, but the division into sublists has been discarded. That is, [a,[b,c],d] becomes [a,b,c,d] .

These predicates are roughly in order of increasing difficulty. Once you have written a predicate, use it in other predicates as appropriate--if you don't, some predicates will be very difficult!

I wrote member, last, extend, and reverse in two lines (two clauses) each. The other predicates each took three lines.

Hints:

1. Use unification in the argument list ( before the :- )! For example, member(H, [H | T]). is simpler than something like member(X, [H | T]) :- X = H. That's not a big deal in this example, but if you get into the habit of using "pattern matching" to select which clause to use, that will make this kind of programming a lot simpler. In fact, any time you are tempted to use =, you are probably making the predicate more difficult than it needs to be.
2. Don't forget to handle the simplest cases--empty lists and (for some predicates) plain atoms.
3. Prolog does backtracking, and most of these predicates, when backtracked into, will produce additional answers. The error is probably not in the predicate, but in something after it.
4. extend. You extend a list by extending the tail of the list, right? But don't forget about the empty list.
5. reverse. Don't forget that you can use functions you have already written (like extend).
6. reverseall. Atoms aren't reversible. The reverse of an atom is the same atom.
7. setof. Don't forget about the empty list.
8. removeall. You need a case for ordinary atoms.
9. collapse. Use append.
10. When all else fails, use trace and notrace.