9

これは、この質問に対する既に削除された回答によって引き起こされた質問です。この問題は次のように要約できます。

折りたたみ中に生成されたリストの末尾を使用して、リストを折りたたむことは可能ですか?

これが私の言いたいことです。階乗を計算したいとします (これはばかげた例ですが、デモンストレーション用です)。次のようにすることにします。

fac_a(N, F) :-
        must_be(nonneg, N),
        (       N =< 1
        ->      F = 1
        ;       numlist(2, N, [H|T]),
                foldl(multiplication, T, H, F)
        ).

multiplication(X, Y, Z) :-
        Z is Y * X.

ここで、 に与えるリストを生成する必要がありfoldlます。ただし、定数メモリで同じことを行うことができます (リストを生成せず、 を使用せずにfoldl):

fac_b(N, F) :-
        must_be(nonneg, N),
        (       N =< 1
        ->      F = 1
        ;       fac_b_1(2, N, 2, F)
        ).

fac_b_1(X, N, Acc, F) :-
        (       X < N
        ->      succ(X, X1),
                Acc1 is X1 * Acc,
                fac_b_1(X1, N, Acc1, F)
        ;       Acc = F
        ).

ここでのポイントは、 を使用するソリューションとは異なりfoldl、これは定数メモリを使用することです。すべての値を含むリストを生成する必要はありません!

階乗の計算は最良の例ではありませんが、次に来るばかげたことを理解するのは簡単です。

私がループ (および再帰) を本当に恐れているとしましょう。それでもリストは必要です。だからここに私が試すかもしれないものがあります：

fac_c(N, F) :-
        must_be(nonneg, N),
        (       N =< 1
        ->      F = 1
        ;       foldl(fac_foldl(N), [2|Back], 2-Back, F-[])
        ).

fac_foldl(N, X, Acc-Back, F-Rest) :-
        (       X < N
        ->      succ(X, X1),
                F is Acc * X1,
                Back = [X1|Rest]
        ;       Acc = F,
                Back = []
        ).

驚いたことに、これは意図したとおりに機能します。部分リストの先頭にある初期値で折り畳みを「シード」し、現在の先頭を消費しながら次の要素を追加し続けることができます。の定義は、上記fac_foldl/4の定義とほとんど同じですfac_b_1/4。唯一の違いは、状態の維持方法が異なることです。ここでの私の仮定は、これは定数メモリを使用する必要があるということです:その仮定は間違っていますか?

これがばかげていることはわかっていますが、折り畳みがいつ開始されるかがわからないリストを折り畳むのに役立つ可能性があります。元の質問では、xy 座標のリストを指定して、接続された領域を見つける必要がありました。xy 座標のリストを 1 回折りたたむだけでは十分ではありません (ただし、2 つのパスで実行できます。同じウィキペディアの記事で参照されているより良い方法が少なくとも 1 つあることに注意してください。ただし、これも複数のパスを使用します。全体として、マルチパス アルゴリズムは、隣接するピクセルへの一定時間のアクセスを前提としています!)。

元の「地域」の質問に対する私自身の解決策は次のようになります。

set_region_rest([A|As], Region, Rest) :-
        sort([A|As], [B|Bs]),
        open_set_closed_rest([B], Bs, Region0, Rest),
        sort(Region0, Region).

open_set_closed_rest([], Rest, [], Rest).
open_set_closed_rest([X-Y|As], Set, [X-Y|Closed0], Rest) :-
        X0 is X-1, X1 is X + 1,
        Y0 is Y-1, Y1 is Y + 1,
        ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
        append(New, As, Open),
        open_set_closed_rest(Open, Set0, Closed0, Rest).

上記と同じ「テクニック」を使用して、これをひねって折り畳むことができます。

set_region_rest_foldl([A|As], Region, Rest) :-
        sort([A|As], [B|Bs]),
        foldl(region_foldl, [B|Back],
                            closed_rest(Region0, Bs)-Back,
                            closed_rest([], Rest)-[]),
        !,
        sort(Region0, Region).

region_foldl(X-Y,
             closed_rest([X-Y|Closed0], Set)-Back,
             closed_rest(Closed0, Set0)-Back0) :-
        X0 is X-1, X1 is X + 1,
        Y0 is Y-1, Y1 is Y + 1,
        ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
        append(New, Back0, Back).

これも「効く」。上記のように終了条件を明示していないため、折り目は選択ポイントを残します。そのfac_foldl/4ため、その直後にカットが必要です (醜い)。

質問

  • リストを閉じてカットを削除するきれいな方法はありますか? 階乗の例では、追加情報があるため、いつ停止するかがわかります。しかし、2 番目の例では、リストの後ろが空のリストであることをどのように確認すればよいでしょうか?
  • 私が見逃している隠れた問題はありますか？
  • これは、DCG を使用した Implicit State とどこか似ているように見えますが、それがどのように機能するのかまったく理解できなかったことを認めなければなりません。これらは接続されていますか？
4

3 に答える 3

0

ボリスの要求に従って、フリーズを使用して実装された 2 番目の例。正直なところ、コード（およびIMO、問題）がかなり不自然であるため、これが質問に答えるかどうかはよくわかりませんが、ここにあります. 少なくとも、これが他の人にフリーズが役立つ可能性があるという考えを与えることを願っています. 簡単にするために、2D ではなく 1D の問題を使用していますが、2 座標を使用するようにコードを変更するのは簡単です。

一般的な考え方は、(1) 新しい Open/Closed/Rest/etc を生成する関数を持つことです。前のものに基づく状態、(2) 「外側」からの新しい要素の生成を「停止」するように指示できる「無限」リストジェネレーター、および (3) 「無限」リストを折りたたみ、それぞれに新しい状態を生成する fold_step 関数リスト項目であり、その状態が最後の状態であると見なされる場合は、ジェネレーターに停止するように指示します。

リストの要素は、ジェネレーターに停止を通知する以外の理由で使用されないことに注意してください。すべての計算状態はアキュムレータ内に保存されます。

ボリス、これで問題が解決するかどうかを明確にしてください。より正確には、フォールド ステップ ハンドラ (アイテム、アキュムレータ、次のアキュムレータ) に渡そうとしたデータの種類は何ですか?

adjacent(X, Y) :-
    succ(X, Y) ;
    succ(Y, X).

state_seq(State, L) :-
    (State == halt -> L = [], !)
    ;
    freeze(L, (
        L = [H|T],
        freeze(H, state_seq(H, T))
    )).

fold_step(Item, Acc, NewAcc) :-
    next_state(Acc, NewAcc),
    NewAcc = _:_:_:NewRest,
    (var(NewRest) ->
        Item = next ;
        Item = halt
    ).

next_state(Open:Set:Region:_Rest, NewOpen:NewSet:NewRegion:NewRest) :-
    Open = [],
    NewOpen = Open,
    NewSet = Set,
    NewRegion = Region,
    NewRest = Set.

next_state(Open:Set:Region:Rest, NewOpen:NewSet:NewRegion:NewRest) :-
    Open = [H|T],
    partition(adjacent(H), Set, Adjacent, NotAdjacent),
    append(Adjacent, T, NewOpen),
    NewSet = NotAdjacent,
    NewRegion = [H|Region],
    NewRest = Rest.

set_region_rest(Ns, Region, Rest) :-
    Ns = [H|T],
    state_seq(next, L),
    foldl(fold_step, L, [H]:T:[]:_, _:_:Region:Rest).

上記のコードに対する改善点の 1 つは、fold_step を高階関数にして、最初の引数として next_state を渡すことです。

于 2016-09-18T09:43:29.713 に答える
0

Prolog 実装がfreeze/2または同様の述語 (Swi-Prolog など) をサポートしている場合は、次のアプローチを使用できます。

fac_list(L, N, Max) :-
    (N >= Max, L = [Max], !)
    ;
    freeze(L, (
        L = [N|Rest],
        N2 is N + 1,
        fac_list(Rest, N2, Max)
    )).

multiplication(X, Y, Z) :-
    Z is Y * X.

factorial(N, Factorial) :-
    fac_list(L, 1, N),
    foldl(multiplication, L, 1, Factorial).

上記の例では、最初に、N から最大値 (Max) まで増加する整数値の「遅延」リストを作成する述語 ( fac_list ) を定義します。次のリスト要素は、前のリスト要素が「アクセス」された後にのみ生成されます (詳細は以下で説明します)。 ）。次に、factorialは遅延リストで乗算を折りたたむだけで、一定のメモリ使用量になります。

この例がどのように機能するかを理解するための鍵は、Prolog リストが、実際には名前が '.' のアリティ 2 の用語であることを思い出すことです。(実際、Swi-Prolog 7 では名前が変更されましたが、これはこの議論では重要ではありません)。ここで、最初の要素はリスト項目を表し、2 番目の要素は末尾 (または終端要素 - 空のリスト、[]) を表します。例えば。[1, 2, 3] は次のように表すことができます。

.(1, .(2, .(3, [])))

次に、フリーズは次のように定義されます。

freeze(+Var, :Goal)
    Delay the execution of Goal until Var is bound

これは、次を呼び出す場合を意味します。

freeze(L, L=[1|Tail]), L = [A|Rest].

その後、次の手順が行われます。

  1. freeze(L, L=[1|Tail])が呼び出されます
  2. プロローグは、L が「何か」と統合される場合、 L =[1|Tail]を呼び出す必要があることを「覚えています」 。
  3. L = [A|Rest]が呼び出されます
  4. Prolog はLを.(A, Rest) と統合します
  5. この統合により、L=[1|Tail]の実行がトリガーされます。
  6. これは、明らかに、この時点で.(A, Rest)にバインドされているLを.(1, Tail) と統合します。
  7. その結果、Aは 1 に統一されます。

この例を次のように拡張できます。

freeze(L1, L1=[1|L2]),
freeze(L2, L2=[2|L3]),
freeze(L3, L3=[3]),
L1 = [A|R2], % L1=[1|L2] is called at this point
R2 = [B|R3], % L2=[2|L3] is called at this point
R3 = [C].    % L3=[3] is called at this point

これは、1 つではなく 3 つの要素を徐々に生成することを除いて、前の例とまったく同じように機能します。

于 2016-09-17T18:53:42.693 に答える