1

I have to write a Prolog program to compute:

 f(0) = 2, f(1) = 0, f(2) = 3, f(n) = 3f(n-3) + 2f(n-2) - f(n-1) for n≥3.

I need to make an iterative version, as well as a recursive version. I was able to write that recursive version in SML:

fun myFunc 0 = 2 | myFunc 1 = 0 | myFunc 2 = 3 | myFunc x = 3* myFunc(x-3) + 2* myFunc(x-2) - myFunc(x-1)

But am having trouble transferring it to Prolog as i'm very new to the language. Also, I was never able to figure out how to do an iterative approach. Any help would be greatly appreciated!

Here is my attempt at the Prolog recursive version. It doesn't compile and probably isn't even close to right:

my_Fun(0, 2). my_Fun(1, 0). my_Fun(2, 3). my_Fun(X, F) :- X>=3, NewX is X-3, NewF is 3 * F, my_fun(NewX,NewF), NewX2 is X-2, NewF2 is 2 * F, my_fun(NewX2, NewF2), NewX3 is X-1, NewF3 is F, myFun(NewX3,NewF3).
Improve this question
3
  • first check the spelling:) you have my_Fun,myFun and my_fun. keep in mind prolog is case-sensitive. maybe reason why it won't compile Commented Nov 16, 2013 at 0:30
  • Oops! Well, i'm sure there are lot's of other problems with it, too. It was more just to show my approach towards the solution. Commented Nov 16, 2013 at 0:37
  • iterative approach: count up (not down): f(n) depends on three previous values of f, so just maintain them: step (n,a,b,c) = (n+1,b,c,3a+2b-c). Commented Nov 16, 2013 at 7:59

2 Answers 2

Reset to default
2

Ok here is the correct code:) Your biggest mistake is making variables NewF,NewF2,NewF3 dependent on something that doesn't have value yet (example: NewF is 3*F... we don't know F yet). Check the code below and notice the difference.`

my_fun(0, 2). my_fun(1, 0). my_fun(2, 3). my_fun(X, F) :- X>=3, NewX is X-3, my_fun(NewX,NewF), NewX2 is X-2, my_fun(NewX2, NewF2), NewX3 is X-1, my_fun(NewX3,NewF3), F is 3*NewF+2*NewF2-NewF3.

Here is the code when using iterative approach. We use accumulators to store the values we need and then use those values to get the result.

my_fun_iterative(0,2) :- !. my_fun_iterative(1,0) :- !. my_fun_iterative(2,3) :- !. my_fun_iterative(X,F) :- X > 2, my_fun_iterative(0,ZeroV), my_fun_iterative(1,OneV), my_fun_iterative(2,TwoV), V is 3*ZeroV+2*OneV-TwoV, my_fun_iterative(X,3,OneV,TwoV,V,F),!. my_fun_iterative(X,X,_,_,F,False) :- not(F=False),!,false. my_fun_iterative(X,X,_,_,F,F). my_fun_iterative(X,N,SecondV,ThirdV,Acc,F) :- X > 3, AccNew is 3*SecondV+2*ThirdV-Acc, NNew is N+1, my_fun_iterative(X,NNew,ThirdV,Acc,AccNew,F).
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Awesome! Thank you so much for your reply. I do see where I went wrong. I don't suppose you'd be willing to help me with an iterative approach to this problem?
I placed the iterative approach check it out
my_fun_iterative(0,0) loops.
Thanks for the feedback false, it improved the answer once again.
my_fun_iterative(3,0) still loops. All these cuts serve nothing
|
2

Here's a recursive version that avoids multiple recalculations by saving the last 3 calculations on each iteration:

my_fun(N, F) :- my_fun(N, F, _, _). my_fun(N, F, F2, F1) :- N >= 3, N1 is N-1, my_fun(N1, F2, F1, F0), F is 3*F0 + 2*F1 - F2. my_fun(0, 2, 0, 0). % 3rd and 4th terms are "dummies" my_fun(1, 0, 2, 0). % 4th term is "dummy" my_fun(2, 3, 0, 2).

An example of an iterative (tail recursive) version:

my_fun_it(N, F) :- N >= 3, my_fun_it(0, F0), my_fun_it(1, F1), my_fun_it(2, F2), my_fun_it(N, 3, F, F2, F1, F0). my_fun_it(0, 2). my_fun_it(1, 0). my_fun_it(2, 3). my_fun_it(N, C, F, F2, F1, F0) :- C < N, my_fun_calc(F0, F1, F2, F3), C1 is C + 1, my_fun_it(N, C1, F, F3, F2, F1). my_fun_it(N, N, F, F2, F1, F0) :- my_fun_calc(F0, F1, F2, F). my_fun_calc(F0, F1, F2, F) :- F is 3*F0 + 2*F1 - F2.

I decided to pull the calculation into its own predicate since I didn't like the same thing in two different places.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.