Here's a lazy-list Hamming numbers in Prolog using a "generator idiom".
The more I think about it the more it seems to me the lazy lists of Haskell are just open-ended (a.k.a. "difference") lists of Prolog, and corecursion just a fancy name for the top-down list building of tail recursion modulo cons. Also, Haskell is implicitly set once language, while (non-backtracking subset of) Prolog is explicitly set once.
The mind-mangling "tying-the-knot" technique is actually nothing more than awkwardly implemented late variable instantiation. And, everything is a generator in Haskell, with memoizing storage a universal access mediator. But anyway,
The following implements the head-forced streams (of SICP variety), where if an element is forced, all the elements preceding it in the list are already forced as well.
:- dynamic( next/3 ).
/* collect N elements produced by a generator in a row: */
take( 0, Next, Z-Z, Next) :- !.
take( N, Next, [A|B]-Z, NextZ) :- N > 0, !, next( Next, A, Next1),
N1 is N-1,
take( N1, Next1, B-Z, NextZ).
/* a "generator" provides a specific `next/3` implementation */
next( hamm( A2,B,C3,D,E5,F,[H|G] ), H, hamm(X,U,Y,V,Z,W,G) ) :-
H is min(A2, min(C3, E5)),
( A2 =:= H -> B=[N2|U], X is N2*2 ; (X,U)=(A2,B) ),
( C3 =:= H -> D=[N3|V], Y is N3*3 ; (Y,V)=(C3,D) ),
( E5 =:= H -> F=[N5|W], Z is N5*5 ; (Z,W)=(E5,F) ).
/* Hamming numbers generator init state: */
mkHamm( hamm( 1,X, 1,X, 1,X, X) ).
/* A calling example: main( +Number) */
main(N) :-
mkHamm(G), take(20,G,A-[],_), write(A), nl,
take(N-1,G,_,G2), take(2,G2,B-[],_), write(B), nl.
/* testing ... */
2 ?- main(1000).
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
[51200000,51840000]
true.
Simple, eh? For ones
we just define
next( ones, 1, ones).
as there is no (change in) state there, and then call it as e.g.
take( N, ones, A-[], _), writeln(A).
For Haskell-like integer enumerations we define
next( fromBy(F,B), F, fromBy(F2,B)) :- F2 is F+B.
and call take(8, fromBy(3,2), A-[], _)
to get A = [3, 5, 7, 9, 11, 13, 15, 17].
Fibonacci sequence is simply
next( fib(A,B), A, fib(B,C)) :- C is A+B.
With take(20, fib(0,1), FS-[], _)
, a 20-elements list FS
of Fibonacci numbers is defined.
Memoizing Fibonacci sequence is
mkFibs( fibs([0|L], L) ) :- L = [1|_].
next( fibs([A|L], L), A, fibs(L, L2) ) :-
L = [B|L2], L2 = [C|_], (var(C) -> C is A+B ; true).
Now restarting from a previously used generator won't recalculate the numbers but instead will re-fetch the previously calculated members of the sequence, where available. This internal shared open-ended storage is fragile to misuse i.e. wrongful instantiation (edit: of its not-yet-set last tail pointer variable). This is the reason for take
building new storage for its answer, instead of exposing the internal one.