Prolog中的懒惰列表？

Question

是否可以在Prolog中使用惰性列表？类似于以下内容:

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

虽然这显然不起作用.

Answer 1

Markus Triska 在公共领域放置了一些值得研究的代码:

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

   Written 2005 by Markus Triska (triska@gmx.at)
   Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

文档的标题(prost,对于Prolog流)可能使文档有点难以找到,但有意义.引用上述内容:

这里,"流"在"序列","延迟列表","惰性列表"等意义上使用,如在计算机程序的结构和解释中,而不是在Prolog输入/输出流的意义上.

Answer 2

这是使用"生成器成语"的Prolog中的懒汉列汉明数字.

我越想它就越多,我认为Haskell的懒惰列表只是Prolog的开放式(又名"差异")列表,而corecursion只是一个奇怪的名称,用于自上而下的列表构建尾递归模数缺点.此外,Haskell隐式设置一次语言,而(非回溯子集)Prolog 明确设置一次.

绞尽脑汁的"绑结"技术实际上只是笨拙地实现了后期变量实例化.而且,一切都是 Haskell中的生成器,memoizing存储是一个通用的访问中介.但无论如何,

下面实现了头强制流(SICP种类),其中如果一个元素被强制,那么列表中它前面的所有元素也已被强制.

:- 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 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's 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.

简单,嗯？对于ones我们刚刚定义

next( ones, 1, ones).

因为那里没有(改变)状态,然后将其称为例如

take(N, ones, A-[], _), writeln(A).

对于我们定义的类似Haskell的整数枚举

next( fromBy(F,B), F, fromBy(F2,B)):- F2 is F+B.

并致电take(8, fromBy(3,2), A-[], _)获得A = [3, 5, 7, 9, 11, 13, 15, 17].斐波纳契序列很简单

next( fib(A,B), A, fib(B,C)):- C is A+B.

使用take(20, fib(0,1), FS-[], _),定义了20个元素FS的Fibonacci数列表.

记住 Fibonacci序列是

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).

现在从以前使用的生成器重新启动将不会重新计算数字,而是重新获取先前计算的序列成员(如果可用).这个内部共享开放式存储很容易被滥用,即错误的实例化(编辑: 其尚未设置的最后尾部指针变量).这就是take为其答案构建新存储的原因,而不是暴露内部存储.

Answer 3

是的,可以在Prolog中使用懒惰列表.这是一个使用的无限,懒惰列表freeze/2.

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

在顶层使用它看起来像这样:

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

您可能还喜欢list_util包(对于SWI-Prolog),它包含几个惰性列表谓词.