4 ms·
Example, now that I'm at a terminal: fib(X, X) :- between(0, 1, X). fib(X, Y) :- (var(Y) -> between(2, infinite, X); MaxX is Y + 1, betwe
by colanderman 10y ago
Example, now that I'm at a terminal:
fib(X, X) :- between(0, 1, X).
fib(X, Y) :-
(var(Y) -> between(2, infinite, X);
MaxX is Y + 1, between(2, MaxX, X)),
X1 is X - 1, X2 is X - 2,
fib(X1, Y1), fib(X2, Y2),
Y is Y1 + Y2.
The trick with var/1 allows the fib(-, +) instantiation to terminate (albeit very slowly). Otherwise it's not necessary.
What's even cooler is SWI-Prolog's CLP support. You can write fib/2 in the obvious manner and support all instantiations:
?- use_module(library(clpfd)).
fib(X, X) :- X #>= 0, X #=< 1, indomain(X).
fib(X, Y) :-
X #>= 2, X #=< Y + 1,
X1 #= X - 1, X2 #= X - 2,
Y #= Y1 + Y2,
fib(X1, Y1), fib(X2, Y2).