Instantly share code, notes, and snippets.

mndrix/example.txt Created Jan 26, 2013

What would you like to do?
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)).

WillNess commented Jan 27, 2013

 Thank you very much! Here's my take on it: ``````fib(X):- X=[0,1|Z], ffib(Z,X). ffib(Z,X):- X=[A|Y], Y=[B|_], N is A+B, freeze(Z, (Z=[N|W],ffib(W,Y)) ). `````` Seems to work too: ``````13 ?- 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] `````` This a translation of ``````fib = 0:1:ffib fib where ffib (a: y@(b:_)) = (a+b):ffib y ``````
Owner

mndrix commented Feb 20, 2013

 @WillNess nicely done

WillNess commented Apr 9, 2013

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

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]```
to join this conversation on GitHub. Already have an account? Sign in to comment