24

Prolog で遅延リストを使用することは可能ですか? 次のようなもの：

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

これは明らかに書かれているようには機能しませんが。

4

6 に答える 6

11

これは、「ジェネレータイディオム」を使用した Prolog のハミング数の遅延リストです。

考えれば考えるほど、Haskell の遅延リストは Prolog の制限のない (別名"difference" ) リストであり、corecursionは末尾再帰 modulo consのトップダウン リスト構築の派手な名前にすぎないように思えます。 . また、Haskell は暗黙的に 1 回言語に設定されますが、Prolog (の非バックトラッキング サブセット) は明示的に 1 回設定されます。

心を揺さぶる「結び目を結ぶ」手法は、実際には、後になって変数のインスタンス化をぎこちなく実装したにすぎません。そして、すべてがHaskell のジェネレーターであり、メモ化ストレージはユニバーサル アクセス メディエーターです。とにかく、

以下は、( SICPの種類の) head-forcedストリームを実装します。要素が強制された場合、リスト内のその前のすべての要素も既に強制されています。

:- 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、内部ストレージを公開する代わりに、その答えのために新しいストレージを構築する理由です。

于 2012-01-16T16:07:23.690 に答える
10

Markus Triskaは、ここでパブリック ドメインにいくつかのコードを配置しました。

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

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

ドキュメントのタイトル ( Prolog ストリームのprost ) は、ドキュメントを見つけるのを少し難しくしているかもしれませんが、意味があります。上記から引用：

ここで、「ストリーム」は、「シーケンス」、「遅延リスト」、「レイジー リスト」などの意味で使用されます。Prolog の入出力ストリームの意味ではなく、コンピュータ プログラムの構造と解釈の場合と同様です。

于 2012-01-15T17:00:30.933 に答える
9

はい、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 用) を楽しむこともできます。

于 2013-01-25T02:16:39.027 に答える
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の遅延リストはとても良い機能です) .

于 2012-01-15T12:19:47.270 に答える
3

これは、一時停止を使用する遅延リストの少し異なる見方です。これは ECLiPSe で書かれていますが、Prolog の他のフレーバーでも複製できるはずです。

属性付き変数を使用して遅延リストの現在の長さを記録し、変数のドメインの下限が引き上げられたときにリストの新しいメンバーを構築します。

リスト メンバーを構築するために実行される述語はアリティ 3 を持ち、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 番目の要素がストアから取得されます。

例として、上記のコードで使用されている in-state と out-state を持つフィボナッチ数述語のバージョンを次に示します。

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 では単純なバックトラッキングによって実装できる動作を実現するために、他の言語でよく使用されることに注意してください。

于 2012-01-16T13:48:00.933 に答える