list - Prolog中的惰性列表？

Question

Prolog中可以有惰性列表吗？类似于以下内容:

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

尽管这显然不像它所写的那样工作。

Answer 1

这是 Prolog 中使用“生成器习语”的惰性列表汉明数。
我越想越觉得 Haskell 的惰性列表只是 Prolog 的开放式列表(又名 "difference")和 corecursion只是 tail recursion modulo cons 自上而下列表构建的一个花哨名称.此外，Haskell 被隐式设置一次语言，而 Prolog(非回溯子集)被显式设置一次。
令人费解的“打结”技术实际上只不过是笨拙地实现了后期变量实例化。而且，一切都是 Haskell 中的生成器，内存存储是通用访问中介。但无论如何，
下面实现了头部强制流(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 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.

很简单吧？对于 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定义了斐波那契数。
内存斐波那契数列是

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 的原因为其答案构建新的存储，而不是暴露内部存储。