Relations

Membership (has more procedural meaning)
Membership (has more declarative meaning)
Concatenation (or append)
Delete the last three emelemts
Delete the first three and the last three elements
Last
Add
Delete
Insert
Sublist
Permutation
Evenlength and Oddlength
Reverse
Palindrome
Shift
Translate
Subset
Dividelist
Canget
Flatten
Kth
Quicksort

Membership

1
2
3

member(X, [X | Tail]).
member(X, [Head | Tail]) :-
    member(X, Tail).

Relation: member(X, L)

Where X is an object and L is a list

Goal: member(X, L) is true if X occurs in L

For example:

?- member(b, [a,b,c]).
true.

?- member(b, [a,[b,c]]).
false.

?- member([b,c], [a,b,c]).
true.

How to approach:

The program for the membership relation can be based on the following observation:

X is a member of L if either

X is the head of L, or

X is a member of the tail of L.

Concatenation (or append)

1
2
3

conc( [], L, L).
conc( [X | L1], L2, [X | L3]) :-
    conc(L1, L2, L3).

Relation: conc(L1, L2, L3)

here L1 and L2 are two lists, and L3 is their concatenation

Goal: conc(L1, L2, L3) is true if L3 is the concatenation of list L1 and list L2

For example:

?- conc([a,b],[c,d],[a,b,c,d]).
true.

?- conc([a,b],[c,d],[a,b,a,c,d]).
false.

How to approach:

In the definition of conc we will have two cases, depending on the first argument, L1:

If the first argument is the empty list then the second and the third arguments must be the same list

If the first argument of conc is a non-empty list then it has a head and a tail and must look like this: [X | L1]

Using conc, the membership relation could be programmed by the following clause:

1 2	member(X, L) :- conc(L1, [X \| L2], L).

or

1 2	member(X, L) :- conc(_, [X \| _], L).

Exercise 3.1 (a)

Write a goal, using conc, to delete the last three elements from a list L producing another list L1.

1	conc(L1, [_,_,_], L).

Exercise 3.1 (b)

Write a sequence of goals to delete the first three elements and the last three elements from a list L producing list L2.

1 2	conc([_,_,_], L1, L), conc(L2, [_,_,_], L1).

Exercise 3.2

Define the relation, last(Item, List), so that Item is the last element of a list List. Write two versions:
(a) using the conc relation
(b) without using the conc relation

% using the conc relation
last_with_conc([], []). % this line is actually not necessary
last_with_conc(Item, List) :-
    conc(_, [Item], L).

% without using conc relation
last_without_conc(Item, [Item]).
last_without_conc(Item, [_ | Tail]) :-
    last_without_conc(Item, Tail).

Add

If X is the new item and the list to which X is added is L then the resulting list is simply [X | L].

If we want to define such a procedure explicitly, it can be written as the fact- add(X, L, [X| L]).

Delete

1
2
3

del(X, [X | Tail], Tail).
del(X, [Y | Tail], [Y | Tail1]) :-
    del(X, Tail, Tail1).

Relation: del(X, L, L1)

Where X is an item and L and L1 are lists

Goal: del(X, L, L1) is true if L1 equal to the list L with the item X removed

For example:

?- del(a, [a,b,a,a], L).
L = [b,a,a];
L = [a,b,a];
L = [a,b,a];
false.

How to approach:

The program for the del relation can be based on the following observation:

If X is the head of the list then the result after the deletion is the tail of the list

If X is in the tail then it is deleted from there.

Insert

1 2	insert(X, List, BiggerList): del(X, BiggerList, List).

Sublist

1
2
3

sublist(S, L) :-
    conc(L1, L2, L),
    conc(S, L3, L2).

Relation: sublist(S, L)

where S and L are lists

Goal: sublist(S, L) is true if S is the sublist of list L

For example:

?- sublist([c,d,e], [a,b,c,d,e,f]).

true.

?- sublist([c,e], [a,b,c,d,e,f]).

false.

How to approach:

S is a sublist of L if:

L can be decomposed into two lists, L1 and L2, and

L2 can be decomposed into two lists, S and some L3.

Permutation

permutation([], []).
permutation([X|L], P) :-
    permutation(L, L1),
    insert(X, L1, P).

Relation: permutation(L, P)

Where L and P are lists

Goal:

For example:

?- permutation([a,b,c], P).

P = [a,b,c];

P = [a,c,b];

P = [b,a,c];

…

How to approach:

The program for permutation can be based on the consideration of two cases:

if the first list is empty then the second list must be empty too

if the first list is not empty then it has the form [X|L], and a permutation of such a list can be constructed as:

first permute L obtaining L1 and then insert X at any position into L1.

or using delete to generate permutation as follows:

permutation2([], []).
permutation2(L, [X|P]) :-
    del(X, L, L1),
    permutation2(L1, P).

Permutation might get into an infinite loop. Be careful.

Exercise 3.3

Define two predicates evenlength(List) and oddlength(List) so that they are true if their argument is a list of even or odd length respectively.

evenlength([]).
evenlength([X|L]) :-
    oddlength(L).
oddlength([_]).
oddlength([X|L]) :-
    evenlength(L).

Exercise 3.4

Define the relation reverse(List, ReversedList) that reverses lists.

reverse([], []).

reverse([H|T],L) :-
    reverse(T, L2),
    append(L2, [H], L).

% T(N) = T(N - 1)         + N - 1
       = T(N - 2) + N - 2 + N - 1
       = 1 + 2 + 3 + ...  + N - 1
       = N * (N - 1) / 2
       = O(N^2)

reverse(L, Res) :-
    reverse_helper(L, [], Res).

reverse_helper([], L, L).

reverse_helper([X|Y], Accumulater, Res) :-
    reverse(Y, [X|Accumulater], Res).

Exercise 3.5

Define the predicate palindrome(List).

1 2	Palindrome(List) :- reverse(List, List).

Exercise 3.6

Define the relation shift(List1, List2) so that List 2 is List1 shifted rotationally’ by one element to the left.

For example,

?- shift([1,2,3,4,5], L1),

shift(L1, L2).

L1 = [2,3,4,5,1]

L2 = [3,4,5,1,2]

1
2
3

shift([],[]).
shift([X|L], Res) :-
    conc(L, [X], Res).

Exercise 3.7

Define the relation translate(List1, List2) to translate a list of numbers between 0 and 9 to a list of the corresponding words. For example:

translate([3,5,1,3], [three, five, one, three]).

Use the following as an auxiliary relation:

means(0, zero). means(1, one). means(2, two). …

means(1, one).
means(2, two).
means(3, three).
means(4, four).
means(5, five).
means(6, six).
means(7, seven).
means(8, eight).
means(9, nine).
means(0, zero).

translate([], []).
translate([X|Xs], [Y|Ys]) :-
    means(X, Y),
    translate(Xs, Ys).

Exercise 3.8

Define the relation subset(Set, Subset) where Set and Subset are two lists representing two sets. We would like to be able to use this relation not only to check for the subset relation, but also to generate all possible subsets of a given set. For example:

?- subset([a,b,c], S).

S = [a,b,c];

S = [b,c];

S = [c];

S = [];

S = [a,c];

S = [a];

…

subset([], []).
subset([First|Rest], [First|Sub]) :- % Retain First in subset
    subset(Rest, Sub).
subset([First|Rest], Sub) :-         % Remove First
    subset(Rest, Sub).

Exercise 3.9

Define the relation dividelist(List, List1, List2) so that the elements of List are partitioned between List1 and List2, and List1 and List2 are of approximately the same length. For example, dividelist([a,b,c,d,e], [a,c,e], [b,d])

dividelist([], [], []).   % Nothing to divide
dividelist([X], [X], []). % Divide one-element list
dividelist([X, Y| List], [X|List1], [Y|List2]) :-
    dividelist(List, List1, List2).

Exercise 3.10

Rewrite the monkey and banana program of Chapter 2 as the relation canget(State, Actions) to answer not just ‘yes’ or ‘no’, but to produce a sequence of monkey’s actions that lead to success. Let Actions be such a sequence represented as a list of moves:

Actions = [walk(door, window), push(window, middle), climb, grasp]

Original algorithm:

% Legal moves
% Grasp banana
move(state(middle, onbox, middle, hasnot),
     grasp,
     state(middle, onbox, middle, has)).

% Climb box
move(state(P, onfloor, P, H),
     climb,
     state(P, onbox, P, H)).

% Push box
move(state(P1, onfloor, P1, H),
     push(P1, P2),
     state(P2, onfloor, P2, H)).

% Walk around
move(state(P1, onfloor, B, H),
     walk(P1, P2),
     state(P2, onfloor, B, H)).

% canget(State): monkey can get banana in State
canget(state(_, _, _, has)).
canget(State1) :-
    move(Statel, Move, State2),
    canget(State2).

New algorithm:

% Legal moves

% Grasp banana
move(state(middle, onbox, middle, hasnot),
     grasp,
     state(middle, onbox, middle, has)).

% Climb box
move(state(P, onfloor, P, H),
     climb,
     state(P, onbox, P, H)).

% Push box
move(state(P1, onfloor, P1, H),
     push(P1, P2),
     state(P2, onfloor, P2, H)).

% Walk around
move(state(P1, onfloor, B, H),
     walk(P1, P2),
     state(P2, onfloor, B, H)).

% canget(State): monkey can get banana in State
canget(state(_, _, _, has)).
canget(State1) :-
    move(State1, _, State2),
    canget(State2).

% Get plan
canget(state(_, _, _, has), []).
canget(State, [Action|Actions]) :-
    move(State, Action, New_State),
    canget(New_State, Actions).

Exercise 3.11

Define the relation flatten(List, FlatList) where List can be a list of lists, and FlatList is List ‘flattened’ so that the elements of List’s sublists (or sub-sublists) are reorganized as one plain list. For example:

?- flatten([a,b,[c,d],[],[[[e]]],f], L).

L = [a,b,c,d,e,f]

flatten([], []).
flatten([X|L], Flatten) :-
    flatten(X, Flatten_Head),
    flatten(L, Flatten_Tail),
    conc(Flatten_Head, Flatten_Tail, Flatten).
flatten(X, [X]) :-
    atomic(X);
    var(X).

Don’t backtrack this program.

Kth

kth(N, _, 0):-
	N=<0.
kth(_, [], 0).
kth(1, [H|_], H).
kth(N, [_|T], Y) :-
    atomic(N),
    N > 0,
    N2 is N - 1,
    kth(N2, T, Y).

Quicksort

kth(N, _, 0):-
	N=<0.
kth(_, [], 0).
kth(1, [H|_], H).
kth(N, [_|T], Y) :-
    atomic(N),
    N > 0,
    N2 is N - 1,
    kth(N2, T, Y).