CODEWITHSUNDEEP
prologfibonaccidcg
ggplot2
ggplot2

Reputation: 51

Fibonacci using DCG

I am in the process of trying to create the fibonacci series using DCG in prolog. I have this for starters, however I have no idea why the code is not being carried out.

Here is the code below:

fib --> [0], [1].
fib --> [X, Y], {Z is X + Y}, [Z].

I get an error that the variables are not sufficiently instantiated. I know that this solution is far from the final one, however I am just struggling to comprehend why this is not possible. Any advice and input would be greatly appreciated!

Upvotes: 3

Views: 370

Answers (2)

TessellatingHeckler
TessellatingHeckler

Reputation: 29048

I agree with @brebs that doing it without args to the DCG is difficult; if the [0,1] is consumed from the list by the first call, the next call with no arguments and no inputs has nothing to add, and breaks.

The closest I can get is with pushback notation:

nextFib, [B,C] --> [A,B], { C is A+B }.

fib --> nextFib, ([] | fib).

which behaves as:

?- phrase(fib, [0,1|Fs], Rest).
Rest = [1, 1|Fs] ;
Rest = [1, 2|Fs] ;
Rest = [2, 3|Fs] ;
Rest = [3, 5|Fs] ;
Rest = [5, 8|Fs] ;
Rest = [8, 13|Fs] ;
Rest = [13, 21|Fs] ;
Rest = [21, 34|Fs] ;
...

Which is not a correct output, it is consuming the first two numbers [A,B] and dropping them, pushing [B,C] back onto the front of the list, and we're looking at them un-consumed. But is going through the Fibonacci sequence in some way.

To gather them up instead of dropping them, we're back to needing an argument:

nextFib(A), [B,C] --> [A,B], { C is A+B }.

fib([F|Fs]) --> nextFib(F), ([] | fib(Fs)).

Then:

?- phrase(fib(Fibs), [0,1|Fs], _).
Fibs = [0|_1682] ;
Fibs = [0, 1|_1360] ;
Fibs = [0, 1, 1|_1366] ;
Fibs = [0, 1, 1, 2|_1372] ;
Fibs = [0, 1, 1, 2, 3|_1378] ;
Fibs = [0, 1, 1, 2, 3, 5|_1384] ;
Fibs = [0, 1, 1, 2, 3, 5, 8|_1390] ;
Fibs = [0, 1, 1, 2, 3, 5, 8, 13|_1396] ;
Fibs = [0, 1, 1, 2, 3, 5, 8, 13, 21|_1402] ;

Upvotes: 3

brebs
brebs

Reputation: 4456

Not efficient, but short:

% Seed with initial 2 values
fib(1, 0) --> [0, 1].
% Get previous 2 values, then sum them
fib(S, P1) --> fib(P1, P2), { S is P1 + P2 }, [S].

Results in swi-prolog:

?- phrase(fib(F, _), L).
F = 1,
L = [0, 1] ;
F = 1,
L = [0, 1, 1] ;
F = 2,
L = [0, 1, 1, 2] ;
F = 3,
L = [0, 1, 1, 2, 3] ;
F = 5,
L = [0, 1, 1, 2, 3, 5] ;
F = 8,
L = [0, 1, 1, 2, 3, 5, 8] ;
F = 13,
L = [0, 1, 1, 2, 3, 5, 8, 13]
...

Upvotes: 3

Related Questions