Lazy lists in Prolog?

Question

Is it possible to have lazy lists in Prolog? Something like the following:

ones([1 | Y]) :- ones(Y).

Although this obviously doesn't work as it's written.

Answer 1

Markus Triska placed here in public domain some code worth to study:

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Prolog stream/lazy list demonstration

   Written 2005 by Markus Triska ([email protected])
   Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

The title of the document (prost, for Prolog streams) maybe make the document a bit difficult to find, but make sense. Quoting from the above:

Here, "stream" is used in the sense of "sequence", "delayed list", "lazy list" etc. as in Structure and Interpretation of Computer Programs, not in the sense of a Prolog input/output stream.

Answer 2

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.

Answer 3

Yes, it's possible to have lazy lists in Prolog. Here's an infinite, lazy list of ones using freeze/2.

ones(L) :-
  freeze(L, (L=[1|T],ones(T)) ).

Using it at the top-level looks like this:

?- ones(Ones), [A,B,C|_] = Ones.
A = B = C = 1.

You might also enjoy the list_util pack (for SWI-Prolog) which contains several lazy list predicates.

Answer 4

well, you could define an infinite list of ones (or anything else) as:

H = [1|H].

use:

4 ?- H=[1|H], [A1|T1] = H, [A2|T2] = T1, T1=T2.
H = [1|**],
A1 = 1,
T1 = [1|**],
A2 = 1,
T2 = [1|**].

Of course, this won't work if you want a list of primes/fibonacci/anything not so trivial.

You could write some predicates that would emulate the behavior of a lazy list but I do not think that there are any libraries/standardized way to do it (at least in swi-prolog) (:( haskell's lazy list is such a nice feature).