list - Prolog中的惰性列表？

Question

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

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

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

Answer 1

这是 Prolog 中使用“生成器习语”的惰性列表汉明数。

我想得越多，在我看来，Haskell 的惰性列表只是 Prolog 的开放式（又名“差异”）列表，而corecursion只是尾递归模缺点的自上而下列表构建的一个花哨名称. 此外，Haskell 被隐式设置一次语言，而 Prolog（非回溯子集）被显式设置一次。

令人费解的“打结”技术实际上只不过是笨拙地实现了后期变量实例化。而且，一切都是Haskell 中的生成器，记忆存储是通用访问中介。但无论如何，

以下实现了head-forced流（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为其答案构建新存储而不是暴露内部存储的原因。

Answer 2

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

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

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

文档的标题（prost，用于 Prolog 流）可能会使文档有点难找，但很有意义。从上面引用：

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

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）。

Answer 4

好吧，您可以将一个（或其他任何内容）的无限列表定义为：

H = [1|H].

采用：

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

当然，如果你想要一个素数/斐波那契/任何不那么微不足道的东西的列表，这将不起作用。

您可以编写一些谓词来模拟惰性列表的行为，但我认为没有任何库/标准化方法可以做到这一点（至少在 swi-prolog 中）（:(haskell 的惰性列表是一个很好的功能） .

Answer 5

这是对使用暂停的惰性列表的稍微不同的看法。它是用 ECLiPSe 编写的，但您应该能够在其他风格的 Prolog 中复制它。

它使用属性变量来记录惰性列表的当前长度，并在提高变量域的下限时构造列表的新成员。

我假设为构造列表成员而执行的谓词具有 3 个参数，三个参数是：状态内、状态外和结果。不过，很容易使示例适应一般目标。

我还使用了“存储”，它是一种非逻辑哈希存储，以便通过避免遍历列表来快速检索列表的第 n 个元素。使用商店不是必需的，但一次又一次地迭代一个长列表可能会很昂贵。

这是创建惰性列表的谓词：

:- lib(ic). % load IC library (constraints over intervals)

% make new lazy list
% lazy_list(-,-,-,++,++)
lazy_list(List, Store, E, Pred, InitState) :-
    store_create(Store),
    E #>= 0,
    suspend(generate_nth_el(E, 0, List, Store, Pred, InitState), 3, E->ic:min).

List是新列表，Store是存储的句柄Pred，生成列表成员的谓词的函子，InitState初始状态以及E用于触发列表创建的变量。

提高的下限时会创建新的列表成员E。在这种情况下，generate_nth_el/6被唤醒：

generate_nth_el(E, Last, List, Store, Pred, LastState) :-
    This is Last+1,
    List = [NextVal|Tail],
    Goal =.. [Pred, LastState, NextState, NextVal],
    call(Goal),  % create next element
    store_set(Store, This, NextVal), % add next element to store
    get_min(E, MinE),
    (
        This == MinE
    ->
        % when reached the lower bound, suspend again
        suspend(generate_nth_el(E, This, Tail, Store, Pred, NextState), 3, E->ic:min)
    ;
        % else continue with extending the list
        generate_nth_el(E, This, Tail, Store, Pred, NextState)
    ).

谓词generate_nth_el/6纯粹供内部使用，不应由用户调用。

最后，这是一个检索第 n 个元素的谓词：

% nth_el(++,+,++,-)
nth_el(N, E, Store, V) :-
    N > 0,
    E #>= N,                % force creation of new elements
    store_get(Store, N, V). % get nth element from store.

E它添加了一个必须至少与 一样大的约束N。如果这增加了下限，则扩展列表。然后从存储中检索第 n 个元素。

例如，下面是上面代码中使用的带有输入和输出状态的斐波那契数谓词的一个版本：

fib((0,0), (0,1), 0) :- !.
fib(StateIn, StateOut, B) :-
    StateIn  = (A, B),
    StateOut = (B, C),
    C is A+B.

它是这样工作的：

?- lazy_list(List, Store, E, fib, (0,0)),
   nth_el(5, E, Store, F5),
   nth_el(3, E, Store, F3),
   nth_el(10, E, Store, F10).
List = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34|_1179]
Store = 'STORE'(16'8ee279a0)
E = E{10 .. 1.0Inf}
F5 = 3
F3 = 1
F10 = 34
There is 1 delayed goal.
Yes (0.00s cpu)

但是请注意，惰性列表通常在其他语言中用于实现在 Prolog 中可以通过简单的回溯来实现的行为。

Answer 6

% A simple generic solution using SWI-Prolog 

% Returns a prefix of a lazy sequence

prefix(Prefix,PrefixLength,LazySequenceName) :-
    apply(LazySequenceName,[LazySequence]),
    length(Prefix,PrefixLength),
    append(Prefix,_,LazySequence).

% Lazy sequence of natural numbers

nat(LazySequence) :- 
    nat(0,LazySequence).
nat(Item,LazySequence) :-
    freeze(LazySequence,
      (LazySequence=[Item|Rest], Next is Item+1, nat(Next,Rest)) ).

% Lazy sequence of Fibonacci numbers

fib(LazySequence) :- 
    fib(1,0,LazySequence).
fib(A,B,LazySequence) :-
    freeze(LazySequence,
       (LazySequence=[C|Rest], C is A+B, fib(B,C,Rest))).

% Examples

test :-
    prefix(N,10,nat), format('Ten first natural numbers: ~w~n',[N]),
    prefix(F,10,fib), format('Ten first Fibonacci numbers: ~w~n',[F]),
    fib(S), nth1(100,S,X), format('The hundredth Fibonacci number: ~w~n',[X]).