2016-12-20 22 views
1

私はProgramming in Prolog: Using the ISO Standardを読んでいるが、私はこの本によって導入appendの再帰的定義の理解の問題を抱えている:例えば理解プロローグ「追加」再帰的定義

append([], List, List). 
append([X|List1], List2, [X|Result]) :- append(List1, List2, Result). 

?- append([a, b, c], [3, 2, 1], Result). 
Result = [a, b, c, 3, 2, 1] 

を私が理解する限り、結果リストには最初のリストの先頭が先頭に含まれるはずであるため、最初は結果リストは[ a ]です。次に、第1引数と第3引数の末尾に再帰的にappend()を実行し、2番目の引数をそのまま残して、3番目の引数([ a ])に新しい最初の引数の先頭をその先頭に含める必要があります。リストは[ b, a ]です(これは後方ですので、私は正しく従っていません)。ある時点で、最初のリストは[]あり、そして得られた配列は[ c, b, a ]あるので、我々はベースケースヒット:

append([], List, List). 

のでappend([], [3, 2, 1], [ c, b, a ]).、全く意味がありません。また、定義全体で操作が行われない場合、第2のリストの内容がどのように考慮されるかについては従わない。

+0

定義によると、結果のリストには最初のリストの先頭がその先頭に含まれるはずです。*最初は結果リストは '[a | Result] '' Result'はまだインスタンス化されていません。次に、 'Result'は' [b |結果2] 'となるので、リスト全体がもう少し分かるようになります。' [a、b |結果2]。 [その他](https://stackoverflow.com/questions/11539203/how-do-i-append-lists-in-prolog/11551001#11551001) –

+0

'append/3'の定義が再帰的であるという事実は、本当にポイントの横にある。あなたはあなたの質問をたどることができたでしょうし、各回帰レベルで何が起こったのか正確に見ていたでしょう。ここで重要なことは、述部自体が評価された場合に成功するための3つの引数のそれぞれについて保持しなければならないものを定義することです。 @matの答えはこれを詳しく説明していますが、私はちょうど反復することが傷つけられないと感じました。 –

答えて

3

[...]定義によれば、結果のリストには最初のリストの先頭が先頭に含まれるはずであるため、最初は結果のリストは[a]です。

あなたが言及したように、定義が結果のリストの先頭がaで、それはリスト全体が[a]であることを言っていないと言います。さらに、このリストは、再帰呼び出しの引数として渡されません。

結果のリストは[X|Result]と定義されているので、この場合はXaで統一されています。 Resultについてはまだわかりませんが、再帰呼び出しの3番目の引数として "渡します"。したがって全体的には、出力はaになり、その後に再帰呼び出しが出力されます。 bcため

の手順はまったく同じですので、あなたは、スタックのように想像することができます:

R = [a|R1] 
R1 = [b|R2] 
R2 = [c|R3] 

または、平坦化:[a|[b|[c|R3]]]。今注文は本当に正しいことに注目してください。

残りの唯一の質問はR3です。さて、この時点の最初の引数は空のリストなので、基本ケースに達しました。これは、単に「最初のリストが空であれば、結果は2番目のリストです」と言います。 だからR3 = [3, 2, 1]。この後、スタックは巻き戻され、追加されたリストが出力として表示されます。それはのように、「入力」と「出力」の観点で考えること、それは非常に魅力的になりますので、私の見解では

+2

定義がtail-recursiveなので、巻き戻すスタックはありません。[* modulo cons *](https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons)。 –

3

、このよう運用読書は、離れ論理プログラミングの真の利点からあなたを導くでしょう関数型プログラミング。このような手続き的または機能的な読書は、関係の完全一般に正義をしない点で、があまりにも限定されているので、です。

さらに、既にご存知のように、この定義を操作上読み取ると、は非常に難しいです。 Prologの正確なコールフローは複雑で、一般的には初心者のために理解するのが難しく、また専門家 もあります。私の意見で


、あなたの定義について考えるための良い方法は、、宣言読書に私たちをリードする、2つの句を検討し、その意味を理解することです。

まず、考えてみます。

append([], List, List). 

をこれは単に保持し、簡単に正しいと見ることができるものを述べている:最初のリストが空の場合は、2番目のリストはよう 同じです3番目のリスト。

注意文言:すべての引数が指定してもしなくてもよいので、私たちも、結果のリストに言及されていません。

次に、第二句を考えてみます。

append([X|List1], List2, [X|Result]) :- append(List1, List2, Result). 

、すなわち&LEFTARROW、それが何であるかのように:-を読む;.だから、これは言う:

append(List1, List2, Result)が、その後、append([X|List1], List2, [X|Result])を保持している場合もが成り立ちます。

再び、これは容易に正確であることが見られ、全て 方向に適用可能である読み取りを可能にすることができます。

Resultが3番目の引数に適しているかどうかと、さらに@WillNessが指摘するように、append/3もこの関係を記述するのに良い名前であるかどうかを検討することができます。

+1

* ...または 'append'が関係の良い名前であるかどうか*(aoteg" appended ";' [A | B]、C、[A | D] 「B、C、D」が「付加」されているとき)。 –

+1

ありがとう、それは修正されました! – mat