Prolog中是否有惰性列表的特性?例如以下代码:
ones([1 | Y]) :- ones(Y).
虽然显然它写错了,但这并不起作用。
Prolog中是否有惰性列表的特性?例如以下代码:
ones([1 | Y]) :- ones(Y).
虽然显然它写错了,但这并不起作用。
这是一个使用“生成器范式”在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.
next( ones, 1, ones).
take( N, ones, A-[], _), writeln(A).
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).
Markus Triska在这里发布了一些代码,值得学习,这些代码已在公共领域发布。
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Prolog stream/lazy list demonstration
Written 2005 by Markus Triska (triska@gmx.at)
Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
文档的标题(用于 Prolog 流的 prost)可能会使得文档有点难以找到,但这样做是有意义的。
引用上述内容:
“在这里,“流”是指“序列”、“延迟列表”、“惰性列表”等,就像《计算机程序的构造和解释》一书中所说的那样,而不是指 Prolog 输入/输出流的意思。”是的,在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),其中包含多个惰性列表谓词。
delay
代替freeze
作为名称。后者过于终极,对我来说意味着需要在冻结变量上显式调用thaw
。前者更具直观性。我习惯于Scheme的delay
,因此对我来说更有意义。 :) - Will Nessfreeze(Term, Frozen)
和melt(Frozed, Thawed)
,它们具有非常棘手的语义属性。 - falsefreeze
和melt_new
吗?它们与此处使用的延迟freeze
有关吗?我没有从书中完全理解它们在哪里以及为什么需要。是否有任何关于它们及其相关问题的讨论链接?谷歌搜索没有带来太多结果。...我曾经尝试阅读Boizumault,但那里使用的freeze
对我来说很困惑,因为我刚刚读了TAoP。将不胜感激地接受任何指针。 :) - Will Ness好的,您可以将一个无限的 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|**].
:- 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)
% 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]).
ones([1|Y]):- freeze(Y, ones(Y))
。 - Will Ness