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.
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.
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 brains-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.
Simple, eh? For
ones
we just defineas there is no (change in) state there, and then call it as e.g.
For Haskell-like integer enumerations we define
and call
take(8, fromBy(3,2), A-[], _)
to getA = [3, 5, 7, 9, 11, 13, 15, 17].
Fibonacci sequence is simplyWith
take(20, fib(0,1), FS-[], _)
, a 20-elements listFS
of Fibonacci numbers is defined.Memoizing Fibonacci sequence is
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.well, you could define an infinite list of ones (or anything else) as:
use:
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).
Markus Triska placed here in public domain some code worth to study:
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:
Yes, it's possible to have lazy lists in Prolog. Here's an infinite, lazy list of ones using
freeze/2
.Using it at the top-level looks like this:
You might also enjoy the list_util pack (for SWI-Prolog) which contains several lazy list predicates.
Here's a slightly different take on lazy lists, which uses suspensions. It's written in ECLiPSe, but you should be able to replicate it in other flavours of Prolog.
It uses an attributed variable to record the current length of the lazy list, and constructs new members of the list when the lower bound of the variable's domain is raised.
I assume that the predicate that is executed to construct list members has arity 3, and the three arguments are: in-state, out-state, and result. It's easy to adapt the example to general goals, though.
I also used a "store", which is a non-logical hash storage, in order to quickly retrieve the n-th element of the list by avoiding to iterate over the list. Using a store is not essential, but iterating over a long list again and again can be expensive.
Here's the predicate that makes the lazy list:
List
is the new list,Store
is a handle of a store,Pred
the functor of the predicate that generates the list members,InitState
the initial state, andE
the variable that is used to trigger the list creation.New list members are created when the lower bound of
E
is raised. In that case,generate_nth_el/6
is woken:The predicate
generate_nth_el/6
is purely for internal use, and should not be called by the user.Finally, here's a predicate to retrieve the n-th element:
It adds a constraint that
E
must be at least as large asN
. If this increases the lower bound, the list is extended. The n-th element is then retrieved from the store.As an example, here's a version of the fibonacci number predicate with in- and out-states as used in the code above:
And here's how it works:
Note, though, that lazy lists are often used in other languages to achieve behaviour that in Prolog can be implemented through simple backtracking.