3

これは、2つのリストを一緒に追加するアルゴリズムです。

Domains
list= integer*

Predicates
nondeterm append(list, list, list)

Clauses
append([], List, List) :- !.
append([H|L1], List2, [H|L3]) :- append(L1, List2, L3).

Goal
append([9,2,3,4], [-10,-5,6,7,8], Ot).

結果はリスト[9,2,3,4,-10,-5,6,7,8]であり、「」に保存されOtます。

私の質問は、これはどのように機能するのかということです。

私が理解しているのは、すべての再帰呼び出しで、最初のリストではテールのみがリストとして取得され（したがって、サイズが小さくなる1までサイズが小さくなり[]ます）、2番目の引数 " List2"はまったく変更されず、3番目の引数は.. 。最初はです。[]再帰呼び出しを行うたびにテールが取得されますが、なので[]、そのまま[]です。

では、どうして突然、3番目の引数（ " Ot"）にリストが追加されたのでしょうか。誰かがこのアルゴリズムを段階的に説明できますか？

4

2 に答える 2

13

まず、句をより理解しやすいものに翻訳しましょう。

append([], List, List) :- !.

書くことができます

append([], List2, Result) :-
    Result = List2,
    !.

と

append([H|L1], List2, [H|L3]) :- append(L1, List2, L3).

書くことができます

append(List1, List2, Result) :-
    List1  = [Head1 | Tail1],
    Result = [HeadR | TailR],
    Head1  =  HeadR,
    append(Tail1, List2, TailR).

これがあなたにとってすでに明確になることを願っています。

次に、段階的に、番号は毎回使用される句を示し、結果の呼び出しが表示されます。

append([9, 2, 3, 4], [-10, -5, 6, 7, 8], Ot).
|
2
|
` append([2, 3, 4], [-10, -5, 6, 7, 8], Ot'). % and Ot = [9|Ot']
  |
  2
  |
  ` append([3, 4], [-10, -5, 6, 7, 8], Ot''). % and Ot' = [2|Ot'']
    |
    2
    |
    ` append([4], [-10, -5, 6, 7, 8], Ot'''). % and Ot'' = [3|Ot''']
      |
      2
      |
      ` append([], [-10, -5, 6, 7, 8], Ot''''). % and Ot''' = [4|Ot'''']
        |
        1
        |
        ` Ot'''' = [-10, -5, 6, 7, 8]

このステップでは、関心のあるすべての値がすでに定義されています。結果の先頭が、後続の（末尾再帰）呼び出しによっていっぱいになる前に設定され、Prologトップダウン方式の特性（「末尾再帰モジュロ短所」とも呼ばれます）で結果のリストが作成されることに注意してください。append

Ot最後のステップで、定義に従って、何であるかを確認しましょう。

Ot = [9|Ot']
        Ot' = [2|Ot'']
                 Ot'' = [3|Ot''']
                           Ot''' = [4|Ot'''']
                                      Ot'''' = [-10, -5, 6, 7, 8]
                           Ot''' = [4,          -10, -5, 6, 7, 8]
                 Ot'' = [3,         4,          -10, -5, 6, 7, 8]
        Ot' = [2,        3,         4,          -10, -5, 6, 7, 8]
Ot = [9,       2,        3,         4,          -10, -5, 6, 7, 8]

私はあなたがそれから何かを得ることを願っています。

于 2012-05-16T14:06:15.520 に答える
3

Prologから英語に翻訳しましょう。2つのルールがあります。

  1. Listにanyを追加すると、その結果になり[]ますList。

  2. 最初の要素がで残りがListであるリストにanyを追加した結果は、最初の要素がであり、残りがに追加した結果であるリストと同じです。HL1HListL1

したがって、に追加[-10,-5,6,7,8]し[9,2,3,4]ます。追加されるリストは空ではないので、そのルールをスキップできます。2番目のルールでは、結果は9最初の要素としてあり、その後にに追加[-10,-5,6,7,8]した結果が続き[2,3,4]ます。

したがって、に追加[-10,-5,6,7,8]し[2,3,4]ます。追加されるリストは空ではないので、そのルールをスキップできます。2番目のルールでは、結果は2最初の要素としてあり、その後にに追加[-10,-5,6,7,8]した結果が続き[3,4]ます。

したがって、に追加[-10,-5,6,7,8]し[3,4]ます。追加されるリストは空ではないので、そのルールをスキップできます。2番目のルールでは、結果は3最初の要素としてあり、その後にに追加[-10,-5,6,7,8]した結果が続き[4]ます。

したがって、に追加[-10,-5,6,7,8]し[4]ます。追加されるリストは空ではないので、そのルールをスキップできます。2番目のルールでは、結果は9最初の要素としてあり、その後にに追加[-10,-5,6,7,8]した結果が続き[]ます。

したがって、に追加[-10,-5,6,7,8]し[]ます。追加されるリストは空であるため、最初のルールでは、結果はになり[-10,-5,6,7,8]ます。

[-10,-5,6,7,8]に追加した結果[]はですので、に追加し[-10,-5,6,7,8]た結果はです。[-10,-5,6,7,8][4][4,-10,-5,6,7,8]

[-10,-5,6,7,8]に追加した結果[4]はですので、に追加し[4,-10,-5,6,7,8]た結果はです。[-10,-5,6,7,8][3,4][3,4,-10,-5,6,7,8]

[-10,-5,6,7,8]に追加した結果[3,4]はですので、に追加し[3,4,-10,-5,6,7,8]た結果はです。[-10,-5,6,7,8][2,3,4][2,3,4,-10,-5,6,7,8]

[-10,-5,6,7,8]に追加した結果[2,3,4]はですので、に追加し[2,3,4,-10,-5,6,7,8]た結果はです。[-10,-5,6,7,8][9,2,3,4][9,2,3,4,-10,-5,6,7,8]

于 2012-05-16T14:06:29.927 に答える