Prolog problem help

Question

I am trying to learn prolog and have come across a problem that I can't figure out. The problem is to write a prolog predicate that takes all the numbers of a list that are less than a given number and put them into a list that will be returned. For example:

input: findNum(5, [5, 3, 5, 6, 4, 5], Y)

output: Y = [3, 4]

Everything I've tried seems to fail. So any help would be much appreciated. Thanks.

Heath Hunnicutt Heath Hunnicutt · Accepted Answer · 2010-03-04T03:16:44

To solve this, you will use a typical Prolog pattern of examining the elements from your input list one-at-a-time. Prolog includes a syntax for selecting the head element from a list, by unifying the list with [A | B] , the first element of the list is unified with A and the remainder of the list (or emptiness if no elements remain) is unified with B.

You should consider first how many clauses you will need. You will need one clause to handle the case of an empty list, which is also the termination condition for your recursion. Each time you examine one item of the list, you recursively examine the remainder of the list. On the final examination, the 'remainder of the list' is empty.

For the clauses which examine the head element of the list, you have two possible conditions: the element satisfies your search criterion (less than 'num'), or it does not. To represent this, implement two clauses, both of which iterate over the list, but only the first of which matches your search criteria. The clause which detects "matching" elements must be written first in your Prolog file so that it will be considered first.

% This clause is for the "empty input" case which is also used to
% discontinue the recursion when finished.

findNum( _, [], []).

% This clause completes only if the first input element is less than
% 'M'.  If the clause completes, the first input element ('X') is unified
% with the output list ([X | Y]).

findNum( M, [X | L], [X | Y]) :-
    X < M,
    findNum(M, L, Y).

% This clause completes if the above clauses do not.  Much like an "else"
% case, this clause simply removes the first input element from the list,
% the element must not match in the search clause above and so we will now
% discard it.  Thus, it is unified with the "throw away" variable named "_"

findNum( M, [_ | L], Y) :-
    findNum(M, L, Y).

Prolog problem help

1 Answers