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