ansaurus

Question

Prolog problem help.

Answer 1

+2 A:

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

Heath Hunnicutt 2010-03-04 03:16:44

Thanks for the explaination, it allowed me to understand what's going on. I'm terrible with prolog, I guess I just don't understand syntax. I actually have another question if you don't mind helping.Suppose the problem is take a list of binary values and convert it to a decimal value.Input: valueOf([1,1,0,1],X).Output: X = 13.I thought of reversing the list and have like...testfunc([H|T], X, Count) :- X2 = X + (H*2^Count), Count2 = Count + 1, testFunc(T,X2,Count2).**if you need me to put this as a question on here it's no problem, and sorry if im asking to much. Thanks

poorStudent 2010-03-04 06:09:38

Prolog is a lot different from a procedural language such as C or Java. In Prolog, you are writing _clauses_ rather than _statements_ and the difference is that clauses don't "do anything" unless they are satisfied (evaluate to 'true'). In the second clause I gave, unless the X<M subclause is satisfied, the entire second clause has no effect. About asking a 2nd question, the tradition here is to ask it in a new post. This helps people use this site as a searchable answer repository. But to hint you toward an answer you are on the right track introducing an intermediate function and using

Heath Hunnicutt 2010-03-04 06:33:36

...using this intermediate function to calculate a 'count'. You will also want to introduce an 'accumulator' which is in each step multiplied by two, then possibly incremented. Ultimately, the clause which discontinues the recursion will have to propagate this accumulated value to some output binding. The recursion and clause which discontinues it often have a lot of the action in Prolog.

Heath Hunnicutt 2010-03-04 06:38:01

Actually, you don't need the count, nor do you need to reverse the list. Since this must be homework, I will give you the boiler-plate and you have to spark the fire. ;) First, create an "interface" to your accumulator-using implementation. "binary_value(B, X) :- binary_value_acc(B, 0, X)." Then, implement the 'base case' of recursion, which is "binary_value_acc([], A, A)." That clause has the effect of discontinuing the recursion and unifying the accumulated value received as the 2nd parameter at the base case (A) with the output parameter called (X) in the interface, the 3rd parameter.

Heath Hunnicutt 2010-03-04 06:57:46

Now what you would need to implement is "binary_value([B|L], A, X) :- %two lines go here. since you know this is recursive, you can guess most of one of the two lines. the other lines uses the prolog 'is' operator to do a little math, creating a new accumulator to pass along in the recursion.

Heath Hunnicutt 2010-03-04 06:58:57

Yea I know I should have put it in a new question, sorry. Your right, it is homework, however the language was not really taught, it was a more figure it out yourself. So me and some friends have been really struggling with it. And I know what your saying about the statements versus clauses, I just cannot seem to break from thinking in statements. I'll probably post this question so that everyone can see it so others will be able to look and possibly learn, once again thanks.

poorStudent 2010-03-04 07:03:47

No worries, I will answer it there, too. You should add the "homework" tag so you will get more explanation than just solution. People here like to give Prolog "solutions" that are bad homework answers, as a way to trip up students who come here. It's a Prolog-ego thing that comes from the bad ole' days of the Internet. Be sure to check the check-mark for me on this one and I'll see you at the next question.

Heath Hunnicutt 2010-03-04 07:53:23

Actually, you really need to go back to your previous questions and click the 'accept answer' check mark on one answer for each.

Heath Hunnicutt 2010-03-04 07:54:13

I would also add an explicit check to the third clause that makes sure the number you are throwing away is greater than or equal to M (or you could add a cut). Otherwise you leave choice points where prolog could backtrack and use the third clause instead of the second clause. In other words, currently, some of the solutions the the program yields are lists where numbers which are less than M have been thrown away. You can force prolog to backtrack by pressing ';' after it has presented you with an answer (providing that there is at least one choice point).

humble coffee 2010-03-04 13:33:20

+1: Very good answer, why rated that low?

gorsky 2010-03-24 17:31:27

ansaurus

tags:

views:

answers:

Prolog problem help.

related questions