Skip to content

Instantly share code, notes, and snippets.

@mndrix
Created January 26, 2013 21:33
Show Gist options
  • Save mndrix/4644762 to your computer and use it in GitHub Desktop.
Save mndrix/4644762 to your computer and use it in GitHub Desktop.
Prolog definition of infinite Fibonacci sequence
?- fibs(F), take(F, 20, _).
F = [0, 1, 1, 2, 3, 5, 8, 13, 21|...],
freeze(_G2395, zip_with(plus, [2584, 4181|_G2395], [4181|_G2395], _G2395)).
zip_with(_, [], []).
zip_with(Goal, [A|As], [B|Bs], [C|Cs]) :-
call(Goal, A, B, C),
freeze(Cs, zip_with(Goal, As, Bs, Cs)).
% implementation from SWI pack list_util
take([], N, []) :-
N > 0,
!.
take(_, 0, []) :-
!.
take([H|T], N1, [H|Rest]) :-
N1 > 0,
succ(N0, N1),
take(T, N0, Rest).
% infinite, lazy Fibonacci sequence
fibs([0,1|T]) :-
F = [0,1|T],
F1 = [1|T],
freeze(T, zip_with(plus, F, F1, T)).
@mndrix
Copy link
Author

mndrix commented Feb 20, 2013

@WillNess nicely done

@WillNess
Copy link

WillNess commented Apr 9, 2013

thx! and thank you for showing it to me first. :)

@mndrix
Copy link
Author

mndrix commented Apr 30, 2014

For anyone finding this later, list_util's iterate/3 makes it quite natural to create infinite, lazy lists:

:- use_module(library(list_util), [iterate/3]).
fib(X) :- iterate(fib,0-1,X).
fib(A-B,B-C,A) :- C is A+B.

Can be used like this:

?- fib(X), length(A,15),append(A,B,X), writeln(A).
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment