3

次の問題があります。

リストに、長さの昇順でソートされた他のリストが含まれているsorted(LL)場合に満たされるpredicate を定義します。LL例えば:

?- sorted([[],[1],[1,1],[1,1,1]]) -> yes.
?- sorted([[],[1],[1,1]]) -> yes.
?- sorted([[1],[],[1,1],[1,1,1]]) -> no.

そして、私はこれまでのところこのコードを持っています:

% shorter/2

shorter([],_).
shorter([_|T1], [_|T2]) :- shorter(T1,T2).

% sorted/1

sorted([]).
sorted([_]).
sorted([L1,L2 | T]) :- shorter2(L1, L2), sorted([L2,T]).

問題は上記の行に含まれています: sorted([L2,T]). リストのリストに 1 つの要素しか残っていない場合、その呼び出しは空のリストを追加する[]ため、short/2 は失敗します。これは、次の SWIPL トレースに示されています。

[trace]  ?- sorted([[1],[2,3]]).
   Call: (6) sorted([[1], [2, 3]]) ? creep
   Call: (7) shorter2([1], [2, 3]) ? creep
   Call: (8) shorter2([], [3]) ? creep
   Exit: (8) shorter2([], [3]) ? creep
   Exit: (7) shorter2([1], [2, 3]) ? creep
   Call: (7) sorted([[2, 3], []]) ? creep <-- empty list appended
   Call: (8) shorter2([2, 3], []) ? creep
   Fail: (8) shorter2([2, 3], []) ? creep
   Fail: (7) sorted([[2, 3], []]) ? creep
   Fail: (6) sorted([[1], [2, 3]]) ? creep
4

2 に答える 2

3

@PauloMoura はすでに正しい答えを出しています。これについて学ぶことはありますか?どのようにその問題に遭遇しましたか? また、そのような問題を体系的に特定するにはどうすればよいでしょうか。まったくの好奇心と、アニメーション GIF の供給不足のために、これらすべてのトレースを調べるためにデバッガーにジャンプしなかったと思います。

むしろ問題が発生しました。つまり、sorted([[1],[2,3]]).成功すると期待していた目標がありましたが、そうではありませんでした。ここで予期しない障害が発生しました。不十分または不完全と呼ばれることもあります。これは、 の定義sorted/1が特殊すぎて、小さすぎる解のセットを記述していることを意味します — 少なくとも、 を見逃していsorted([[1],[2,3]])ます。

多くの場合、最初に問題を最小限に抑えることが役立ちます。またsorted([[],[3]])、成功すると予想されますが、失敗します。そしてsorted([[],[]])ループも。

非終了について

ループ?多くの場合、純粋な Prolog プログラムでローカライズするのはさらに簡単です。falseプログラムに目標と目標を追加T = []します。結果として生じるプログラムの断片 (障害スライスと呼ばれる) は、確実に完全に機能不全になります。しかし、それは非常に優れた特性を保持します。For: この新しいフラグメントがループすると、元のプログラムもループします。まだループしているプログラムは次のとおりです。

?- sorted([[],[]]), false .

sorted([]) :- false .
sorted([_]) :- false .
sorted([L1,L2 | T]) :- T = [], L1 = [], L2 = [] ,
   短い(L1、L2)、
   ソート済み([L2,T])。

短い([],_)。
short([_|T1], [_|T2]) :- false ,
    short(T1,T2) .

言い換えると:

sorted([[],[]]) :-
   shorter([],[]),
   sorted([[],[]]).

したがって、手続き的に言えば、そのルールは (常に) リストの長さを短縮しません。

まとめ読み

問題を理解する別の方法は、再帰規則を矢印が指している方向に右から左に読むことです。実は、:-←まあ、1970 年代のスタイルを象徴するためのものです (このフランスの 1972 年のサマーヒットを理解 するまで聞いてください)。それでは、これを試してみましょう。私は読みます:

sorted([L1,L2 | T]) :- shorter2(L1, L2), sorted([L2,T]).
                                         ^^^^^^^^^^^^^^ starting here

右側から始めて、これを次のように解釈します。

与えられた、sorted([L2,T])真です。

多分いくつかの余分な発言: さて、あなたはかなり不安になるかもしれません. あなたは言うかもしれません:誰がこれを知っていますか?たぶん、それはまったく真実ではありません!しかし、要点は、それは条件付きであるということです。わかった?

提供されたshorter(L1, L2)ものは真です


そうすれば、それは真実であると結論付けることができsorted([L1, L2|T])ます。

したがって、長さ 2 のリストを許可されたものとして取り、長さ 2 以上のリストも同様に成り立つと結論付けます。

しかし、長さ 2 のリストが成り立つと実際にどこで述べているのでしょうか? このルール以外の場所はありません。したがって:これはどこにも述べられていません。したがって、長さが 2 以上のリストは決してソートされません。

于 2014-11-04T16:21:35.560 に答える
2

述語の最後の句に 2 つのタイプミスがsorted/1あります。

sorted([L1,L2| T]) :- shorter(L1, L2), sorted([L2| T]).
于 2014-11-04T02:44:39.937 に答える