Prolog中的惰性列表？

Question

Prolog中是否有惰性列表的特性？例如以下代码：

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

虽然显然它写错了，但这并不起作用。

- Peteris

---

你写的内容只需要进行微调即可实现所需功能：ones([1|Y]):- freeze(Y, ones(Y))。 - Will Ness

Answer 1

这是一个使用“生成器范式”在Prolog中实现的懒惰列表 Hamming 数。

我越想越觉得，Haskell 的懒惰列表只是 Prolog 中开放式（也称“差集”）列表的一种，而 核心递归 只是尾递归模除 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”为其答案构建新存储而不是暴露内部存储的原因。

- Will Ness

Answer 2

Markus Triska在这里发布了一些代码，值得学习，这些代码已在公共领域发布。

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

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

文档的标题（用于 Prolog 流的 prost）可能会使得文档有点难以找到，但这样做是有意义的。 引用上述内容： “在这里，“流”是指“序列”、“延迟列表”、“惰性列表”等，就像《计算机程序的构造和解释》一书中所说的那样，而不是指 Prolog 输入/输出流的意思。”

- CapelliC

Answer 3

是的，在Prolog中可以使用“freeze/2”实现惰性列表。以下是一个无限惰性的1的列表示例。

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

在顶层使用它的样子如下：

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

您可能还会喜欢list_util pack（用于SWI-Prolog），其中包含多个惰性列表谓词。

- mndrix

---

无限斐波那契数列会是什么样子？ - Will Ness

非常感谢您的示例。就个人而言，我更喜欢使用delay代替freeze作为名称。后者过于终极，对我来说意味着需要在冻结变量上显式调用thaw。前者更具直观性。我习惯于Scheme的delay，因此对我来说更有意义。 :) - Will Ness

@WillNess：我有点怀疑你指的是freeze(Term, Frozen)和melt(Frozed, Thawed)，它们具有非常棘手的语义属性。 - false

@false 是TAoP中的freeze和melt_new吗？它们与此处使用的延迟freeze有关吗？我没有从书中完全理解它们在哪里以及为什么需要。是否有任何关于它们及其相关问题的讨论链接？谷歌搜索没有带来太多结果。...我曾经尝试阅读Boizumault，但那里使用的freeze对我来说很困惑，因为我刚刚读了TAoP。将不胜感激地接受任何指针。 :) - Will Ness

@WillNess: TAoP的结构允许将变量与相应的原子相关联（反之亦然）。这本身在语义上就存在着相当大的问题，并且没有被其他系统采用。这是为了使元编程更加清晰的一种尝试。我认为它是失败了的。Boizumault的freeze/2与SICStus、SWI、YAP、B等系统中的freeze/2是相同的。 - false

Answer 4

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

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的延迟列表是一个很好的功能）。

- Thanos Tintinidis

---

+1. 不完整的数据结构是 Prolog 提供的最接近惰性列表的东西。 - Fred Foo

你不觉得当/2、freeze/2和dif/2可以用来模拟惰性吗？ - joel76

@joel76 是的，我认为它们确实是用来模拟延迟执行的有用构建块。 - Thanos Tintinidis

@joel76：是的，请看我的答案，它使用了挂起（ECLiPSe中相当于SWI的when/2和freeze/2） - twinterer

Answer 5

这里介绍一种利用悬挂变量实现的懒列表方法，使用 ECLiPSe 编写，但是你应该能够在其他 Prolog 版本中复制它。这个方法使用属性变量来记录懒列表的当前长度，并在变量域的下限提高时构造新的列表成员。

我假设被执行来构造列表成员的谓词具有 3 个参数：in-state、out-state 和 result。但是很容易将此示例适配到通用目标上。

为了快速检索列表的第 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.

And here's how it works:

?- 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中可以通过简单回溯实现的行为。

- twinterer

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

- silvio lago