Danh sách lười biếng trong Prolog?

Question

Có thể có danh sách lười biếng trong Prolog không? Một cái gì đó như sau:

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

Mặc dù điều này rõ ràng không hoạt động như được viết.

Answer 1

Markus Triska placed here trong phạm vi công cộng some code giá trị để nghiên cứu:

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

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

Tiêu đề của tài liệu (prost, cho Prolog suối) có thể làm cho các tài liệu một chút khó khăn để tìm kiếm, nhưng Trích dẫn từ phía trên:

Ở đây, "dòng" được dùng theo nghĩa của "chuỗi", "danh sách trì hoãn", "danh sách lười biếng" vv như trong Cấu trúc và Giải thích từ máy tính Chương, không phải trong ý nghĩa của một Prolog luồng đầu vào/đầu ra.

Answer 2

tốt, bạn có thể xác định một danh sách vô hạn của những người thân (hoặc bất cứ điều gì khác) như:

H = [1|H]. 

sử dụng:

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

Tất nhiên, điều này sẽ không hoạt động nếu bạn muốn có một danh sách của primes/fibonacci/bất cứ điều gì không quá tầm thường.

Bạn có thể viết một số biến vị ngữ mô phỏng hành vi của danh sách lười nhưng tôi không nghĩ rằng có bất kỳ thư viện/cách chuẩn hóa nào để làm điều đó (ít nhất là trong swi-prolog) (: danh sách lười biếng của haskell là như vậy . một tính năng tuyệt vời)

Answer 3

Dưới đây là một sự khác biệt đôi chút về danh sách lười biếng, sử dụng tính năng tạm ngưng. Nó được viết bằng ECLiPSe, nhưng bạn sẽ có thể tái tạo nó trong các hương vị khác của Prolog.

Nó sử dụng biến được gán để ghi lại độ dài hiện tại của danh sách lười và xây dựng thành viên mới của danh sách khi giới hạn dưới của miền biến được nâng lên.

Tôi giả định rằng biến vị ngữ được thực hiện để xây dựng thành viên danh sách có số 3 và ba đối số là: trạng thái, trạng thái ngoài và kết quả. Thật dễ dàng để thích ứng với ví dụ về mục tiêu chung.

Tôi cũng đã sử dụng "cửa hàng", bộ nhớ băm không hợp lý, để nhanh chóng truy xuất phần tử thứ n của danh sách bằng cách tránh lặp qua danh sách. Sử dụng một cửa hàng là không cần thiết, nhưng lặp lại trong một danh sách dài một lần nữa và một lần nữa có thể tốn kém.

Dưới đây là vị mà làm cho danh sách lười biếng:

:- 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 là danh sách mới, Store là một handle của một cửa hàng, Pred các functor của vị mà tạo ra danh sách thành viên, InitState tình trạng ban đầu và E biến được sử dụng để kích hoạt tạo danh sách.

Thành viên danh sách mới được tạo khi giới hạn dưới của E được nâng lên.Trong trường hợp đó, generate_nth_el/6 được đánh thức:

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

Các vị generate_nth_el/6 là hoàn toàn cho sử dụng nội bộ, và không nên được gọi bởi người sử dụng.

Cuối cùng, đây là một vị để lấy các yếu tố n-thứ:

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

Nó cho biết thêm một ràng buộc E phải có ít nhất lớn như N. Nếu điều này làm tăng giới hạn dưới, danh sách sẽ được mở rộng. Phần tử thứ n sau đó được lấy ra từ cửa hàng.

Như một ví dụ, đây là một phiên bản của vị số fibonacci với các quốc gia ngoài trong và được sử dụng trong đoạn code trên:

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

Và đây là cách hoạt động:

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

Lưu ý, mặc dù, danh sách lười biếng thường được sử dụng trong các ngôn ngữ khác để đạt được hành vi mà trong Prolog có thể được thực hiện thông qua backtracking đơn giản.

Answer 4

Dưới đây là danh sách lười biếng Hamming trong Prolog bằng cách sử dụng "thành ngữ trình tạo".

Tôi càng nghĩ về nó, có vẻ như với tôi những danh sách lười biếng của Haskell chỉ là danh sách mở (hay còn gọi là "khác biệt"), và corecursion chỉ là một cái tên ưa thích cho việc xây dựng danh sách từ trên xuống tail recursion modulo cons. Ngoài ra, Haskell được ẩn hoàn toàn đặt một lần ngôn ngữ, trong khi (tập hợp con không quay lại) Prolog là rõ ràng đặt một lần.

Kỹ thuật "buộc liên kết" của bộ não-mangling thực sự không có gì khác hơn là sự diễn giải biến trễ muộn. Và, tất cả mọi thứ là một máy phát điện trong Haskell, với lưu trữ ghi nhớ một trung gian truy cập phổ quát. Nhưng dù sao,

Sau đây thực hiện các dòng bắt buộc đầu tiên (của SICP), nếu một phần tử bị ép buộc, tất cả các phần tử trước đó trong danh sách cũng đã bị buộc.

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

Đơn giản, eh? Đối với ones chúng tôi chỉ xác định

next(ones, 1, ones). 

như không có (thay đổi trong) nhà nước ở đó, và sau đó gọi nó như là ví dụ

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

Đối Haskell giống như kiểu liệt kê số nguyên chúng ta định nghĩa

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

và gọi take(8, fromBy(3,2), A-[], _) để có được A = [3, 5, 7, 9, 11, 13, 15, 17]. Fibonacci sequence chỉ đơn giản là

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

Với take(20, fib(0,1), FS-[], _), một danh sách 20 yếu tố FS của Fibonacci số được xác định.

Memoizing Fibonacci sequence là

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

Bây giờ khởi động lại từ một máy phát điện sử dụng trước đó sẽ không tính toán lại các con số mà thay vào đó sẽ tái nạp các thành viên tính toán trước đó của dãy, nếu có. Bộ nhớ mở được chia sẻ nội bộ được chia sẻ này dễ vỡ để sử dụng sai sự tức thời sai (chỉnh sửa:của biến con trỏ đuôi cuối cùng chưa được đặt). Đây là lý do để xây dựng kho lưu trữ mới cho câu trả lời của mình, thay vì hiển thị nội bộ bên trong.

Answer 5

Có, có thể có danh sách lười trong Prolog. Dưới đây là danh sách vô hạn, lười biếng của những người sử dụng freeze/2.

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

Sử dụng nó ở cấp cao nhất trông như thế này:

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

Bạn cũng có thể tận hưởng những list_util pack (ví SWI-Prolog), trong đó có nhiều vị từ danh sách lười biếng.

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