3

ウィキペディアでは、 call/cc を使用すると、非決定論的な選択のために amb 演算子を実装できると書かれています。私の質問は、継続の唯一のサポートが継続渡しスタイルで記述することである言語で、amb 演算子をどのように実装するかです。アーラン？

4

1 に答える 1

3

成功する解決策または選択を構成する制約をガードとしてエンコードできれば、リスト内包表記を使用して解決策を生成できます。たとえば、リスト内包表記のドキュメントでは、ピタゴラスのトリプルを解く例が示されています。これは、よく使用される問題ambです (たとえば、SICP 第 2 版の演習 4.35 を参照してください)。pyth1/1リスト内包表記ページに示されている、より効率的なソリューションは次のとおりです。

pyth1(N) ->
    [ {A,B,C} ||
        A <- lists:seq(1,N-2),
        B <- lists:seq(A+1,N-1),
        C <- lists:seq(B+1,N),
        A+B+C =< N,
        A*A+B*B == C*C 
    ].

の重要な側面の 1 つambは、解空間を効率的に検索することです。これはA、 、B、およびの可能な値を生成Cしlists:seq/2、ガードを使用してそれらの値を制約およびテストすることによって行われます。このページには、 pyth/1where A、B、およびという名前の効率の悪いソリューションも示されていることに注意してください。そのアプローチはすべての順列を生成しますが、よりも遅くなります(たとえば、私のマシンでは、よりも 5-6 倍遅くなります)。Clists:seq(1,N)pyth1/1pyth(50)pyth1(50)

制約をガードとして表現できない場合は、パターン マッチングと try/catch を使用して、失敗したソリューションに対処できます。たとえば、通常の関数と recursivepyth/1として書き直された同じアルゴリズムは次のとおりです。triples/1triples/5

-module(pyth).
-export([triples/1]).

triples(N) ->
    triples(1,1,1,N,[]).
triples(N,N,N,N,Acc) ->
    lists:reverse(Acc);
triples(N,N,C,N,Acc) ->
    triples(1,1,C+1,N,Acc);
triples(N,B,C,N,Acc) ->
    triples(1,B+1,C,N,Acc);
triples(A,B,C,N,Acc) ->
    NewAcc = try
                 true = A+B+C =< N,
                 true = A*A+B*B == C*C,
                 [{A,B,C}|Acc]
             catch
                 error:{badmatch,false} ->
                     Acc
             end,
    triples(A+1,B,C,N,NewAcc).

パターン マッチングは次の 2 つの目的で使用します。

  • 関数の先頭で、 の値を制御AしB、Cに関して 、Nいつ終了したかを知る
  • の最終節の本文で、その条件と一致triples/5をアサートするA+B+C =< NA*A+B*B == C*Ctrue

trueの最後の句で両方の条件が一致する場合triples/5、解をアキュムレータ リストに挿入しますが、どちらかが一致しない場合は、badmatchエラーをキャッチして元のアキュムレータ値を保持します。

を呼び出すと、およびでtriples/1使用されるリスト内包表記アプローチと同じ結果が得られますが、の半分の速度でもあります。それでも、このアプローチでは、制約を通常の関数としてエンコードし、try/catch 式内で成功するかどうかをテストできます。pyth/1pyth1/1pyth/1

于 2015-07-08T16:15:17.627 に答える