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`.