Prolog Predicate Solution

Question

I am going through some past exam questions for my prolog exam that is coming up.

Here is the question:

(a) Write a predicate insert(Xs, Y, Zs) that holds when Zs is the list obtained by inserting Y into the list Xs. A query such as:
```
? - insert([1,2,3], 4, Zs).
```

should succeed four times and give the following answers:

Zs = [4, 1, 2, 3]

Zs = [1, 4, 2, 3]

Zs = [1, 2, 4, 3]

Zs = [1, 2, 3, 4].

I'm a bit concerned because I have no idea where to start. Would anyone be able to help out as I need example solutions to practice for my exam.

Would really appreciate any help with this.

insert(Xs, Y, Zs) should define what it looks like when Zs is the list Xs with Y inserted somewhere. To define the rule, you break it into logical cases. Your main definition will be recursive. But a simple base case is that Z just looks like Xs with Y as its first element ([Y|Xs]). — lurker

mat mat · Accepted Answer · 2016-04-14T11:07:51

We start by changing the terrible name of this predicate: The predicate should describe what holds, not what to do. The name should reflect that. I suggest list_with_element/3, and encourage you to try finding even better names, ideally making clear what each argument stands for.

Then, we do what we set out to do: Describe the cases that make this relation hold.

For example:

list_with_element([], E, [E]).
list_with_element([L|Ls], E, [E,L|Ls]).
list_with_element([L|Ls0], E, [L|Ls]) :-
        ...

I leave filling in the ... as an easy exercise. State the condition that is necessary for the clause head to be true!

EDIT: I would like to say a bit more about the pattern above. In my experience, a good way—and definitely in the beginning—to reason about predicates that describe lists is to consider two basic cases:

the atom [], denoting the empty list
terms of the form '.'(E, Es), also written as [E|Es], where E is the first element of the list and Es is again a list.

This follows the inductive definition of lists.

The drawback in this specific case is that this approach leads to a situation where case (2) again needs to be divided into two subcases, and somehow unexpectedly necessitates three clauses to handle the two basic cases. This obviously runs counter to our intuitive expectation that two clauses should suffice. Indeed they do, but we need to be careful not to accidentally lose solutions. In this case, the first two clauses above are both subsumed by the fact:

list_with_element(Ls, E, [E|Ls]).

Every experienced Prolog coder will write such predicates in this way, or just, as in this case, use select/3 directly. This is what @lurker sensed and hinted at, and @tas correctly shows that a different clause (which is easy to come up with accidentally) does not fully subsume all cases we want to express.

Thus, I still find it a lot easier to think first about the empty list explicitly, make sure to get that case correct, then continue with more complex cases, and then see if you can write the existing program more compactly. This is the way I also used for this sample code, but I did not make it as short as possible. Note that with monotonic code, it is completely OK to have redundant facts!

Note that is is specifically not OK to just replace the first two clauses by:

list_with_element([L|Ls], E, [E|Ls]).

because this clause does not subsume case (1) above.

Prolog Predicate Solution

3 Answers