24
क्या प्रोलॉग में आलसी सूचियां संभव है? निम्नलिखित की तरह कुछ:प्रोलॉग में आलसी सूचियां?
ones([1 | Y]) :- ones(Y).
हालांकि यह स्पष्ट रूप से लिखा नहीं है जैसा कि यह लिखा गया है।
A
उत्तर
9
मार्कस Triska placed here सार्वजनिक क्षेत्र में some code लायक अध्ययन करने के लिए:
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Prolog stream/lazy list demonstration
Written 2005 by Markus Triska ([email protected])
Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
दस्तावेज़ (prost के शीर्षक, Prolog धाराओं के लिए) हो सकता है दस्तावेज़ थोड़ा मुश्किल लगता है, लेकिन समझ में आता है। उपर्युक्त से उद्धरण:
यहाँ, "धारा", "देरी सूची", "अनुक्रम" के अर्थ में "आलसी सूची" आदि संरचना और कंप्यूटर कार्यक्रम की व्याख्या के रूप में प्रयोग किया जाता है एक Prolog के अर्थ में नहीं इनपुट/आउटपुट स्ट्रीम।
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|**].
, इस करता है, तो आप एक सूची चाहते हैं काम नहीं करेगा primes/fibonacci/कुछ भी तुच्छ नहीं है।
आप कुछ भविष्यवाणियों को लिख सकते हैं जो आलसी सूची के व्यवहार का अनुकरण करेंगे लेकिन मुझे नहीं लगता कि ऐसा करने के लिए कोई पुस्तकालय/मानकीकृत तरीका है (कम से कम स्वि-प्रोलॉग में) (:(हैकेल की आलसी सूची ऐसी है । एक अच्छी सुविधा)
+1
+1। अपूर्ण डेटा संरचनाएं आलसी सूचियों के निकटतम हैं जो प्रोलॉग को पेश करती हैं। –
+2
क्या आपको नहीं लगता कि जब/2, फ्रीज/2, dif/2 आलसी अनुकरण करने के लिए उपयोग किया जा सकता है? – joel76
+0
@ joel76 yup, मुझे लगता है कि वे आलसी अनुकरण करने के लिए वास्तव में उपयोगी बिल्डिंग ब्लॉक हैं –
4
यहां आलसी सूचियों पर थोड़ा अलग लेना है, जो निलंबन का उपयोग करता है। यह ईसीएलपीएस में लिखा गया है, लेकिन आप इसे प्रोलॉग के अन्य स्वादों में दोहराने में सक्षम होना चाहिए।
यह आलसी सूची की वर्तमान लंबाई रिकॉर्ड करने के लिए एक जिम्मेदार चर का उपयोग करता है, और चर के डोमेन के निचले बाउंड को उठाए जाने पर सूची के नए सदस्यों को बनाता है।
मुझे लगता है कि सूची सदस्यों के निर्माण के लिए निष्पादित की गई वास्तविकता में 3 है, और तीन तर्क हैं: राज्य, राज्य, और परिणाम। यद्यपि सामान्य लक्ष्यों के लिए उदाहरण को अनुकूलित करना आसान है।
मैंने सूची में पुन: प्रयास करने से बचकर सूची के एन-वें तत्व को तुरंत पुनर्प्राप्त करने के लिए एक "स्टोर" का उपयोग किया, जो एक गैर-लॉजिकल हैश स्टोरेज है। एक स्टोर का उपयोग करना आवश्यक नहीं है, लेकिन एक लंबी सूची में फिर से चलना महंगा हो सकता है।
यहाँ विधेय कि आलसी सूची बनाता है:
:- 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 प्रारंभिक अवस्था के functor है , और 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 आंतरिक उपयोग के लिए विशुद्ध रूप से है, और उपयोगकर्ता द्वारा नहीं कहा जाना चाहिए।
% 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 के रूप में होना चाहिए कहते हैं:
अंत में, यहाँ एन-वें तत्व प्राप्त करने के लिए विधेय है। यदि यह निचला बाउंड बढ़ाता है, तो सूची विस्तारित होती है। एन-वें तत्व को तब स्टोर से पुनर्प्राप्त किया जाता है।
एक उदाहरण के रूप में, यहाँ in- और बाहर राज्यों के साथ फिबोनैकी संख्या विधेय के एक संस्करण के रूप में उपरोक्त कोड में इस्तेमाल किया:
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)
नोट, हालांकि, आलसी सूचियां अक्सर अन्य भाषाओं में व्यवहार को प्राप्त करने के लिए उपयोग की जाती हैं जो प्रोलॉग में सरल बैकट्रैकिंग के माध्यम से लागू की जा सकती है।
8
यहां "जनरेटर मुहावरे" का उपयोग करके प्रोलॉग में एक आलसी सूची हैमिंग संख्या है।
अधिक मैं इसके बारे में सोचते अधिक मुझे लगता है हास्केल के आलसी सूचियों सिर्फ मुक्त हैं (उर्फ "अंतर") Prolog सूची बनाई है और corecursion सिर्फ एक फैंसी नाम के शीर्ष-डाउन सूची के निर्माण के लिए tail recursion modulo cons। इसके अलावा, हास्केल निश्चित रूप से एक बार भाषा सेट करता है, जबकि (गैर-बैकट्रैकिंग सबसेट) प्रोलॉग स्पष्ट रूप से एक बार सेट होता है।
मस्तिष्क-उलझन "टाईंग-द-गाँठ" तकनीक वास्तव में देर से परिवर्तनीय त्वरण को अजीब रूप से कार्यान्वित करने से कहीं ज्यादा कुछ नहीं है। और, सब कुछ एक जनरेटर हैस्केल में, एक सार्वभौमिक पहुंच मध्यस्थ भंडारण को याद करने के साथ। लेकिन वैसे भी,
निम्नलिखित हेड-मजबूर स्ट्रीम (एसआईसीपी किस्म का) लागू करता है, जहां एक तत्व को मजबूर किया जाता है, तो सूची में इससे पहले के सभी तत्व पहले ही मजबूर हो चुके हैं।
:- 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.
सरल, एह? ones के लिए हम बस के रूप में वहाँ कोई राज्य (में परिवर्तन)
next(ones, 1, ones).
को परिभाषित है, और फिर जैसे के रूप में यह फोन
take(N, ones, A-[], _), writeln(A).
हास्केल की तरह के लिए पूर्णांक enumerations हम
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 है संख्या परिभाषित की गई है।
Memoizing फाइबोनैचि अनुक्रम
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 के उत्तर के लिए नए संग्रहण का कारण है।
8
हां, प्रोलॉग में आलसी सूचियां संभव है। freeze/2 का उपयोग कर लोगों की एक अनंत, आलसी सूची यहां दी गई है।
ones(L) :-
freeze(L, (L=[1|T],ones(T))).
शीर्ष-स्तर पर इसका इस्तेमाल करते हुए इस तरह दिखता है:
?- ones(Ones), [A,B,C|_] = Ones.
A = B = C = 1.
तुम भी आनंद ले सकते हैं list_util pack (के लिए SWI-Prolog) जो कई आलसी सूची विधेय में शामिल है।
+1
अनंत फाइबोनैकी अनुक्रम कैसे होगा हमशक्ल? –
+0
@WillNess मैंने आपके लिए एक अनंत, आलसी Fibonacci अनुक्रम एक साथ रखा https://gist.github.com/4644762 यह हास्केल के रूप में संक्षिप्त नहीं है, लेकिन फिर भी मजेदार है। उदाहरण के लिए – mndrix
+1
आपको बहुत बहुत धन्यवाद। ... मैं व्यक्तिगत रूप से 'फ्रीज' के स्थान पर 'देरी' नाम पसंद करूंगा। उत्तरार्द्ध इतना अंतिम है, और इसका मतलब है - मेरे लिए - एक ठंडे var पर 'thaw' को स्पष्ट रूप से कॉल करने की आवश्यकता। जबकि पूर्व अधिक सहज है। मुझे योजना के 'देरी' के लिए उपयोग किया जाता है, इसलिए यह मेरे लिए अधिक समझ में आता है। :) –
3
% 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]).
जो आपने लिखा है उसके लिए एक चिमटा नौकरी करता है: 'वाले ([1 | वाई]): - फ्रीज (वाई, वाले (वाई))। –