との位置にある要素が等しいposAt(List1,P,List2)かどうかをテストする Prolog 述語を作成しました。PList1List2
posAt([X|Z], 1, [Y|W]) :-
X = Y.
posAt([Z|X], K, [W|Y]) :-
K > 1,
Kr is K - 1,
posAt(X, Kr, Y).
テスト時:
?- posAt([1,2,3], X, [a,2,b]).
の出力を期待してX = 2いましたが、代わりに次のエラーが発生しました。
ERROR: >/2: Arguments are not sufficiently instantiated
このエラーが発生するのはなぜですか?
プロローグ述語は、引数とステートメントの間の関係です
List1 と List2 の位置 P の要素が等しい
明らかに、複数のソリューションが可能な例です。
?- posAt([1,2,3],X,[1,5,3,7]).
X = 1.
したがって、sharky からの回答は、技術的なエラーが発生する理由を明確に説明していますが、小さな修正が必要です。
posAt([X0|_], Pos, Pos, [X1|_]) :-
X0 == X1.
今では期待どおりに動作します。
?- posAt([1,2,3],X,[1,5,3,7]).
X = 1 ;
X = 3 ;
false.
リスト処理のための単純な述語を書くことは、非常に価値のある見習いの練習であり、言語を効果的に学ぶ主な方法です。利用可能なライブラリの述語も調べたい場合は、library( lists )の nth1/3 を使用したバージョンを次に示します。
posAt(L0, P, L1) :-
nth1(P, L0, E),
nth1(P, L1, E).
これは以下を出力します:
?- posAt([1,2,3],X,[1,5,3,7]).
X = 1 ;
X = 3.
この場合、SWI-Prolog の「トップレベル」インタープリターが解の決定性を推測できる理由を理解しようとするのは興味深いことです。
これは、サブゴールK > 1が Prolog によって評価されるときに、Kまだバインドされていない変数であり、数値ではないために発生します。標準の Prolog は、このような数値範囲の制限の true/false 値が接地されていない場合、評価できません (しません) (これを許可するが動作が異なる CLP のような制約ソルバーとは対照的です)。
この解決策を検討してください。
posAt(L0, Pos, L1) :-
posAt(L0, 1, Pos, L1).
posAt([X0|_], Pos, Pos, [X1|_]) :-
X0 == X1.
posAt([_|X0s], CurrPos, Pos, [_|X1s]) :-
NextPos is CurrPos + 1,
posAt(X0s, NextPos, Pos, X1s).
最初の述語posAt/3は、初期条件を設定します。つまり、リストを位置 1 として設定し、リストposAt/4を反復処理するように呼び出します。
の最初の節posAt/4は一致条件です。両方のリストの同じ位置にある要素は等しいです。この場合、現在の位置変数はPos、結果である と統合されます。
X0リストの要素とX1が等しくないために上記の節が失敗した場合、リストの位置が 1 つ増加し、次の項目のペアで のCurrPos再帰呼び出しが処理を再開します。posAt/4
編集: の最初の句の誤ったカットを削除posAt/4しました (ピックアップの @chac に感謝)
（これは私のダッシュボードにポップアップしただけなので、遅い答えです...）
質問を見て、元の質問に近い解決策を提供できないかと考えていました。すでに説明したように、問題はリレーション>がインスタンス化された引数を必要とすることです。についても同様ですis。ただし、これは目標を並べ替えることで簡単に修正できます。
posAt([X|_], 1, [X|_]).
posAt([_|X], K, [_|Y]) :-
posAt(X, Kr, Y),
K is Kr+1,
K > 1.
この解決策は、ランタイムが両方のリストの長さで線形であるということKです。ただし、最初の要素がリスト内で一致する場合、繰り返しによる回答にうまく示されている場合、問題があります。
実際、最後の要素は余分なので、等価です。
posAt([X|_], 1, [X|_]).
posAt([_|X], K, [_|Y]) :-
posAt(X, Kr, Y),
K is Kr+1.
ただし、@repeat で証明されているように、このコードは恐ろしく遅いです。これはおそらく、コードが末尾再帰を壊しているという事実によるものです。
論理的にクリーンなソリューションは、この問題を解決します。ここで、ペアノの公理 (s/1 の後継者または関係) を使用して自然数を表すと、解は次のようになります。
posAt([X|_], zero, [X|_]).
posAt([_|X], s(K), [_|Y]) :-
posAt(X, K, Y).
ただし、これは時間を計るのが難しいため、ハック的なソリューションはほぼ同等です
posAt([X|_], [a], [X|_]).
posAt([_|X], [a|L], [_|Y]) :-
posAt(X, L, Y).
このソリューションが提供するタイミング
N=8000,numlist(1,N,_Zs), length(_LN,N),time(posAt(_Zs,_LN,_Zs)).
7,999 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 7342035 Lips)
N = 8000
TL;DR: @CAFEBABE、@CapelliC、@mat、および@sharky による回答はすべて不十分です!
それで...以前に提案された答えの欠点は正確には何ですか?
@CAFEBABE は次のように述べています。
このソリューションの優れた点は、ランタイムが両方のリストの長さに対して線形であることです。
その声明をテストしてみましょう！
?- numlist(1,1000,Zs), time(posAt__CAFEBABE1(Zs,1000,Zs))。 % 999,001推論、0.091 秒で 0.090 CPU (100% CPU、11066910 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 4 つの推論、0.000 秒で 0.000 CPU (97% CPU、66738 リップ) 間違い。
残念！他のものはうまくいきます：
?- numlist(1,1000,Zs), time(posAt__CapelliC1(Zs,1000,Zs))。 % 671推論、0.000 秒で 0.000 CPU (98% CPU、3492100 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]. ?- numlist(1,1000,Zs), time(posAt__mat1(Zs,1000,Zs))。 % 3,996推論、0.001 秒で 0.001 CPU (99% CPU、3619841 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 5 つの推論、0.000 秒で 0.000 CPU (89% CPU、154703 リップ) 間違い。 ?- numlist(1,1000,Zs), time(posAt__sharky1(Zs,1000,Zs))。 % 1,000推論、0.000 秒で 0.000 CPU (100% CPU、2627562 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 4 つの推論、0.000 秒で 0.000 CPU (82% CPU、97109 リップ) 間違い。
@CapelliC used nth1/3、これはユニバーサルターミネーションで問題を引き起こす可能性があります（実際に発生します）：
?- time((posAt__CapelliC1(_,N,[a,b,c]), false))。 **ループ**
ああ！他のすべてはうまくいきます：
?- time((posAt__CAFEBABE1(_,_,[a,b,c]), false))。 % 14 の推論、0.000 秒で 0.000 CPU (88% CPU、1098470 リップ) 偽。 ?- time((posAt__mat1(_,_,[a,b,c]), false))。 % 2,364 推論、0.001 秒で 0.001 CPU (100% CPU、2764075 リップ) 偽。 ?- time((posAt__sharky1(_,_,[a,b,c]), false))。 % 6 推論、0.000 秒で 0.000 CPU (89% CPU、207247 リップ) 偽。
@mat のコードには複雑な問題があります。@CAFEBABE と @CapelliC は「少し優れています」 — 低レベルのプリミティブ(is)/2とnth1/3.
?- numlist(1,1000,Zs), time((posAt__mat1(Zs,_,_), false))。 % 33,365,972推論、1.643 秒で 1.643 CPU (100% CPU、20304661 リップ) 間違い。 ?- numlist(1,1000,Zs), time((posAt__CAFEBABE1(Zs,_,_), false))。 % 1,001,002推論、0.083 秒で 0.083 CPU (100% CPU、12006557 リップ) 間違い。 ?- numlist(1,1000,Zs), time((posAt__CapelliC1(Zs,_,_), false))。 % 171,673推論、0.030 秒で 0.030 CPU (100% CPU、5810159 リップ) 間違い。
@sharky によるコードは、この点で明らかに最適です。
?- numlist(1,1000,Zs), time((posAt__sharky1(Zs,_,_), false))。 % 1,003推論、0.001 秒で 0.001 CPU (100% CPU、1605658 リップ) 間違い。
@sharky のコードはメタ論理組み込み述語(==)/2を使用しているため、インスタンス化が不十分な用語で使用すると論理的な健全性が失われます。このクエリは成功するはずです:
?- posAt__sharky1([a], 1, Xs). 偽。
他のコードはすべて論理的に正しい答えを与えます:
?- posAt__CAFEBABE1([a], 1, Xs). Xs = [a|_G235] ; 間違い。 ?- posAt__CapelliC1([a], 1, Xs). Xs = [a|_G235] . ?- posAt__mat1([a], 1, Xs). Xs = [a|_G235] ; 間違い。
最初の答えを過ぎると、@ CAFEBABEのコードは少し効率が悪くなります。
?- numlist(1,1000,Zs), time(posAt__CAFEBABE1(Zs,1,Zs))。 % 0 推論、0.000 秒で 0.000 CPU (93% CPU、0 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 999,004推論、0.076 秒で 0.076 CPU (100% CPU、13121058 リップ) 間違い。
@sharky のコードでは、同様の (ただし、1 桁小さい) 問題が発生しています。
?- numlist(1,1000,Zs), time(posAt__sharky1(Zs,1,Zs))。 % 1 推論、0.000 秒で 0.000 CPU (75% CPU、31492 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 1,003推論、0.001 秒で 0.001 CPU (100% CPU、1078556 リップ) 間違い。
@CapelliC と @mat によるコードはどちらも問題なく動作しています。
?- numlist(1,1000,Zs), time(posAt__CapelliC1(Zs,1,Zs))。 % 7推論、0.000 秒で 0.000 CPU (85% CPU、306802 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]. ?- numlist(1,1000,Zs), time(posAt__mat1(Zs,1,Zs))。 % 0 推論、0.000 秒で 0.000 CPU (80% CPU、0 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 5 つの推論、0.000 秒で 0.000 CPU (84% CPU、345662 リップ) 間違い。
どうしようか？このアプローチに従って、@mat と @sharky のコードを組み合わせてみませんか?
:- use_module(ライブラリ(clpfd) )。 posAt__NEW(L0, 位置, L1) :- posAt__NEW_(L0, 1, 位置, L1). posAt__NEW_([ X |_], 位置, 位置, [ X |_])。 posAt__NEW_([_|X0s], CurrPos, Pos, [_|X1s]) :- CurrPos #< Pos, NextPos #= CurrPos + 1, posAt__NEW_(X0s、NextPos、Pos、X1s)。
posAt__NEW/3上記のサンプル クエリを次のように再実行してみましょう。
?- numlist(1,1000,Zs), time(posAt__NEW(Zs,1000,Zs))。 % 4,997推論、0.000 秒で 0.000 CPU (100% CPU、18141619 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 9 つの推論、0.000 秒で 0.000 CPU (71% CPU、122877 リップ) 間違い。 ?- time((posAt__NEW(_,_,[a,b,c]), false))。 % 440 推論、0.001 秒で 0.001 CPU (98% CPU、803836 リップ) 偽。 ?- numlist(1,1000,Zs), time((posAt__NEW(Zs,_,_), false))。 % 154,955推論、0.014 秒で 0.014 CPU (100% CPU、11067900 リップ) 間違い。 ?- posAt__NEW([a], 1, Xs). Xs = [a|_G229] ; 間違い。 ?- numlist(1,1000,Zs), time(posAt__NEW(Zs,1,Zs))。 % 1 推論、0.000 秒で 0.000 CPU (93% CPU、121818 リップ) Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; % 7推論、0.000 秒で 0.000 CPU (86% CPU、266748 リップ) 間違い。
大丈夫！最後に、上記の 3番目のクエリで使用されるゴールが線形複雑性を持つことを確認します。
?- numlist(1,100,Zs), time((posAt__NEW(Zs,_,_), false))。 % 15,455の推論、0.004 秒で 0.004 CPU (100% CPU、3545396 リップ) 間違い。 ?- numlist(1,1000,Zs), time((posAt__NEW(Zs,_,_), false))。 % 154,955推論、0.017 秒で 0.016 CPU (98% CPU、9456629 リップ) 間違い。 ?- numlist(1,10000,Zs), time((posAt__NEW(Zs,_,_), false))。 % 1,549,955推論、0.099 秒で 0.098 CPU (99% CPU、15790369 リップ) 間違い。 ?- numlist(1,100000,Zs), time((posAt__NEW(Zs,_,_), false))。 % 15,499,955推論、1.007 秒で 1.003 CPU (100% CPU、15446075 リップ) 間違い。