9  Recursive Programming in Prolog

What's in This Set of Notes ?

• Examples
• Transforming Recursion to Iteration
• Recursive Comparison
• Joining Structures
• Accumulators
• Mapping
• Problems

select_first(X,Xs,Ys) :- Ys is the list obtained by removing the
first occurrence of X from the list Xs

select_first(X, [X|Tail], Tail).
select_first(X,[Y | Tail], [Y | Zs]) :-
        X \= Y,
        select_first(X,Tail,Zs).

select(X, HasXs, OneLessXs) :- The list OneLess X is the result
of removing one occurrence of X from the list HasXs

select(X, [X|Xs], Xs).
select(X, [Y|Ys], [Y|Zs]) :- select(X,Ys,Zs).

selects(Xs, Ys) :- This list Xs is a subset of list Ys

selects([], Ys).
selects([X|Xs], Ys) :-
        select(X, Ys, Ys1),
        selects(Xs, Ys1).

sort(Xs, Ys) :- The list Ys is a sorted (ascending) list of Xs

sort([], []).
sort([X|X], Ys) :-
        sort (Xs, Zs),
        insert (X, Zs, Ys).

insert (X, Ys, Zs) :- Insert X into the list Ys at the appropriate
location giving the list Zs

insert(X,[],[X]).
insert(X, [Y|Ys], [Y|Zs]) :-
        X > Y,
        insert(X,Ys,Zs).
insert(X, [Y|Ys], [X,Y | Ys]):-
        X <= Y.

maximum(Xs, N) :- N is the maximum of a list of integers Xs

maximum([Head|Tail], M) :-
        maximum (Tail, Head, M).
maximum([], M, M).
maximum([Head|Tail], Y, M) :-
        Head <= Y,
        maximum(Tail, Y, M).
maximum([Head|Tail], Y, M) :-
        Head > Y,
        maximum(Tail, Head, M).

• Using linear recursive process

factorial(N, F) := F is the integer Factorial of N

factorial (0,1).
factorial(N,F) :-
        N > 0,
        N1 is N - 1,
        factorial (N1, F1),
        F is N * F1.

• Using linear iterative process

factorial(N, F) := F is the integer Factorial of N

factorial (N,N,F,F).
factorial(N,F) :-
        factorial(0,N,1,F).
factorial(I,N,T,F) :-
        I < N,
        I1 is I + 1,
        T1 is T * I1,
        factorial(I1,N,T1,F).
 

• OR

factorial (0,F,F).
factorial(N,F) :-
        factorial(N,1,F).
factorial(N,T,F) :-
        N > 0,
        T1 is T * N,
        N1 is N - 1,
        factorial(N1, T1, F).

between(I, J, K) :- K is an integer between I and J

between(I,J,I) :-
        I = J.
between(I,J,K) :-
        I < J,
        I1 is I + 1,
        between(I1, J, K).

aless(X,Y) :- X is less then Y

?aless(avacodo, clergyman) -> yes
?aless(window, motorcar) -> fail
?aless(pictures, picture) -> fail.

Algorithm: check each letter and compare

Conditions:

1. reach end of first word before second -> yes e.g., ?aless(book, bookbinder)
2. find letter in first word less than second -> yes, e.g., ?aless(elephant, elevator).
3. find letter in each word is equal, try aless on remaining letters, e.g., ?aless(lazy, leather) -> ?aless(azy, eather).
4. reach end of words at same time -> fail, e.g., ?aless(apple, apple).
5. run out of characters in second word -> fail, e.g., ?aless(alphabet, alp).

Question: How do we do this in Prolog? We need a list of characters from a symbol.

Answer: Use a built-in predicate in Prolog that converts a symbol to a list of characters

name(X,Y) :- Y is a list of integers representing the characters in the symbol X.

?name(X, [97,108,112]).
        X = alp

?name(alp, X).
        X = [97,108,112]

Solution

aless(X,Y) :-
        name(X,L),
        name(Y,M),
        aless(L,M).

//first condition
aless([],[_|_]).

//second condition
aless([X|_], [Y|_]) :-
        X < Y.

//third condition
aless([A|X], [B|Y]) :-                OR   aless([A|X], [A|Y]) :-
        A = B,                                                    aless(X,Y).
        aless(X,Y).

//fourth and fifth condition
//don't need to write anything, these are failures. When
//we don't write facts or rules, goals will fail automatically.

append([a,b,c], [3, 2, 1], [a, b, c, 3, 2, 1]).

append(L1,L2,L3) :- the list L3 is the result of appending list L1 and L2.

Conditions:

    If the first list is empty
            append([], L, L).

1. The first element of the first list is always the first element of the third list.
2. The tail of the first list will always have list two appended to it to form the tail of list three.
3. You must use the append in  condition 2
4. As you continually take the head of L1 it will eventually be empty, reaching the boundary condition.

Solution

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

• Accumulators are used for traversing a structure and computing a result
• Technique is to use predicate arguments to represent current result.

 

 
 
 
 
 

length_of_list(X, Y) :- Y is the length of list X

length_of_list([],0).
length_of_list([H|T], N) :-
            length_of_list(T,N1),
            N is N1 + 1.
 

OR

length_of_list(L,N ) :-
        length_accumulator(L, 0, N).

length_accumulator([], A, A).

length_accumulator([H|T], A, N) :-
        A1 is A + 1.
        length_accumulator(T, A1, N).

• Mapping is a technique to traverse a structure component by component

 
change(you, i).
change(are, [am, not]).
change(french, german).
change(do, no).
change(X, X).

?alter([do, you, know, french]).
        X = [no, i, know, german]

alter([],[]).
alter([H|T], [X|Y]) :-
        change(H,X),
        alter(T,Y).

Consider

isList(X) :- Is X a list

isList([A|B]) :-
    isList(B).
isList([]).

This is ok ?isList([1,3, 5]).

?isList(X) loops forever.
 

Similarly.
 

person(X) :- Is X a person.

person(X) :-
        person(Y),
        mother(X,Y).
person(adam).

?person(Z). will loop forever

Problem: Prolog searchers clauses in the order they are declared

Solution: In general, move facts before rules in a relation
 

parent(X,Y) :- child(Y,X).
child(A,B) :- parent(B,A).

weak_isList([]).
weak_isList([_|_]).

This version just tests the first part of the list, rather than checking whether the tail is []. This will not loop when matching against a variable.

?weak_isList(X).