2

この質問はすでに聞かれていることは知っていますが、私の具体的な実装について聞きたいだけです。Prolog を練習し、Prolog をよりよく理解するために、この関数を作成しています。ここに私が持っているものがあります:

del(Ele, [H], [H]) :- Ele \= H.
del(Ele, [H|T], [H|New]) :-
    Ele \= H,
    del(Ele, T, [New]).

アイデアは、New削除したい要素が と等しくない場合に呼び出される新しいリストに要素を追加するというものHです。私が理解していることから、要素 where に到達するとコードが停止するため、コードが機能していませんEle \= H。これを修正する方法はありますか？

たとえば、del(5, [3,4,5,6,7], X)false を返します。

また、より良い解決策はありますか？リスト内のすべての要素を新しいリストに追加し続けるのは、悪い解決策のように思えます。これは、大きなリストの場合は遅くなるからです。現在リストにある要素を保持し、一致する要素を見つけ、Eleその要素を削除してから、リストを返すだけです。

4

2 に答える 2

3

保持する必要があるいくつかのケースについて説明del/3しました。ただし、これらはEleリスト内の要素と等しくない/単一化できない場合のみです。不足しているものがいくつかあります。

空のリストはどうですか？

Ele要素と等しい場合はどうなりますか?

したがって、さらに句を追加する必要があります。(後で、冗長性の理由から、一部を削除することもできます)。

SWI、B、SICStus、または YAP を使用している場合dif/2は、 の代わりに使用することを検討して(\=)/2ください。

dif/2この場合に が非常に役立つ理由は次のとおりです。dif/2純粋に単調なプログラムになります。そして、あなたはそれを直接試すことができます：

?- del(5, [3,4,5,6,7], X)。
偽。

あなたが抱えていたのと同じ問題。問題が何であるかをもう一度述べさせてください。何かが成り立つはずだと期待していますが、そうではありません。したがって、関係の定義が狭すぎます。クエリを一般化すると、より良い答えが得られる可能性があります。もう一度試してみてdel(E, [3,4,5,6,7], X).くださいfalse。そこで、さらに一般的なクエリを試してみます。

?- del(E、Xs、Ys)。
Xs = Ys、Ys = [_G1076]、
dif(E, _G1076) ...

私には完璧に見えます！多分別の答え：

?- del(E、Xs、Ys)。
Xs = Ys、Ys = [_G1076]、
dif(E, _G1076) ;
Xs = [_G1133、_G1136]、
Ys = [_G1133|_G1136]、
dif(E, _G1136),
dif(E, _G1133) ...

今、私たちは間違った答えを得ました。読みやすくするために、少しインスタンス化します。

?- del(e, [a,b], Ys)。
Ys = [a|b] ;
間違い。

[a|b]はリストではないため、この回答は明らかに正しくありません。そして、それはおそらく最小の不正解です...

ここでお見せしたいのは、ほとんどの場合、段階を踏まずに問題を特定できるということです。より複雑な制御フロー (同時実行など) を取得すると、ステップバイステップのデバッグは命令型言語でも機能しません。Prologではまったくスケーリングしません。

于 2013-03-19T21:06:43.393 に答える
2

トレースしましょう:

?- trace, del(5, [3,4,5,6,7], X).
   Call: (7) del(5, [3, 4, 5, 6, 7], _G218) ? creep
   Call: (8) 5\=3 ? creep
   Exit: (8) 5\=3 ? creep
   Call: (8) del(5, [4, 5, 6, 7], [_G344]) ? creep
   Call: (9) 5\=4 ? creep
   Exit: (9) 5\=4 ? creep
   Call: (9) del(5, [5, 6, 7], [[]]) ? creep
   Fail: (9) del(5, [5, 6, 7], [[]]) ? creep
   Fail: (8) del(5, [4, 5, 6, 7], [_G344]) ? creep
   Fail: (7) del(5, [3, 4, 5, 6, 7], _G218) ? creep
false.

したがって、コードが 5 になると実際には失敗していることがわかります5 \= 5。リストに複数の項目があるため、最初のルールは一致しません。5 \= 32 番目のルールはandを見つけた後に「正しく」繰り返され5 \= 4ますが、どのルールにもケースがない5 = 5ため、そこで失敗が発生します。

ちなみに、リストに 5 がない場合はどうなるか見てみましょう。

?- trace, del(5, [3,4,6,7], X).
   Call: (7) del(5, [3, 4, 6, 7], _G350) ? creep
   Call: (8) 5\=3 ? creep
   Exit: (8) 5\=3 ? creep
   Call: (8) del(5, [4, 6, 7], [_G473]) ? creep
   Call: (9) 5\=4 ? creep
   Exit: (9) 5\=4 ? creep
   Call: (9) del(5, [6, 7], [[]]) ? creep
   Fail: (9) del(5, [6, 7], [[]]) ? creep
   Fail: (8) del(5, [4, 6, 7], [_G473]) ? creep
   Fail: (7) del(5, [3, 4, 6, 7], _G350) ? creep
false.

これが、前に「正しく」と言った理由です。あなたの帰納的なケースも正しくありません。1つには、del(Ele, T, [New])持っているのに上にあるdel(Ele, [H|T], [H|New])ので、右側で余分な時間をかけてリストをアンラップしています (これが私たちのトレースが含ま[[]]れている理由です)。しかし、@false は、削除しようとしているものを実際に見つけた場合をまったく考慮しないという、より大きな問題に直面します。:)リストが空の場合も処理しません。

データ構造をたどって各項目を調べることが O(N) になるというのは、残念なことです。もう 1 つの残念な事実は、関数型言語と宣言型言語 ( 「代入可能言語」がない言語) では、リストを変更することはリストの少なくとも一部をコピーすることを意味します。Prolog でこれを行うには、より効率的な方法があります (たとえば、差分リストを使用できます) が、基本的な問題は同じです。Prolog の効率性はかなり大きなトピックです。前もってあまり心配しないように言っておきますが、すぐに気になることがあります。しかし、この場合、いいえ、破壊的な更新を使用した実質的により効率的なアプローチは実際にはありません。

于 2013-03-19T21:14:47.193 に答える