1

いくつかのチュートリアルを実行しただけで、フラット化のような高度な再帰プロシージャがいくつか見つかりました。複数の再帰 (ヘッドテール) を含む同様の例を見つけるためにグーグルを試みましたが、必要な結果を得ることができませんでした。

高度なリスト再帰 (ヘッド、テールの両方) をカバーするいくつかの述語またはチュートリアルを推測できますか?

4

1 に答える 1

4

@hardmath が言っていることを少し拡張するために、リストの定義を見てみましょう。

  • 規範事例：[]
  • 誘導の場合:[Head|Tail]

これが再帰的なデータ構造になっているのは、それTailがリストでもあるからです。だからあなたが見るとき[1,2,3]、あなたはまた見ている[1|[2|[3|[]]]]. それを証明しましょう：

?- X = [1|[2|[3|[]]]].
X = [1, 2, 3].

したがって、再帰のより「高度な」形式は、より複雑な再帰データ型またはより複雑な計算のいずれかを含む形式です。ほとんどの人がさらされる次の再帰的なデータ型はバイナリ ツリーです。バイナリ ツリーには、ノードごとに 2 つの分岐があるという優れた特性があるため、ツリーを少し見てみましょう。

まず、リストからの定義のような適切な定義が必要です。私は次のことを提案します：

  • 規範事例：empty
  • 誘導の場合:tree(LeftBranch, Value, RightBranch)

では、サンプル ツリーをいくつか作成して、それらがどのように見えるかを感じてみましょう。

% this is like the empty list: no data
empty

% this is your basic tree of one node
tree(empty, 1, empty)

% this is a tree with two nodes
tree(tree(empty, 1, empty), 2, empty).

構造的には、最後の例はおそらく次のようになります。

   2
  /
 1

次に、いくつかのレベルでより完全な例を作成しましょう。このツリーを構築しましょう:

     10
   /    \
  5      9
 / \    /  \
4   6  7   14

Prolog 構文では、次のようになります。

tree(tree(tree(empty, 4, empty), 5, tree(empty,  6, empty)), 
     10, 
     tree(tree(empty, 7, empty), 9, tree(empty, 14, empty)))

最初に必要なのは、ツリーのサイズを合計する方法です。リストと同様に、基本ケースと帰納ケースを考慮する必要があります。

% base case
tree_size(empty, 0).

% inductive case
tree_size(tree(Left, _, Right), Size) :-
  tree_size(Left, LeftSize),
  tree_size(Right, RightSize),
  Size is LeftSize + RightSize + 1.

比較のために、リストの長さを見てみましょう。

% base case
length([], 0).

% inductive case
length([_|Rest], Length) :- 
  length(Rest, LengthOfRest), 
  Length is LengthOfRest + 1.

編集: @false は、上記は直感的ですが、帰納的なケースを次のように変更することで、より優れた論理プロパティを持つバージョンを生成できることを指摘しています。

length([_|Rest], Length) :-
  length(Rest, LengthOfRest),
  succ(LengthOfRest, Length).

したがって、次の 2 つを比較すると、データ構造を再帰的に処理することの特徴が明確にわかります。

  • 基本ケースと帰納的ケースに関して定義された再帰的なデータ構造が与えられます。

  • 基本ケースを処理するルールの基本を記述します。

    通常、この手順は明らかです。長さまたはサイズの場合、データ構造には空の基本ケースがあるため、ゼロをそのケースに関連付ける必要があります。

  • ルールの誘導ステップを記述します。

    誘導ステップは、データ構造の再帰的なケースを取り、そのケースが追加するものを処理し、それをルールを再帰的に呼び出した結果と組み合わせて、データ構造の「残り」を処理します。

リストは一方向にのみ再帰的であるため、ほとんどのリスト処理ルールでは再帰呼び出しは 1 つだけです。ツリーには 2 つのブランチがあるため、ツリー全体を処理する必要があるか、1 つのパスだけを処理する必要があるかによって、1 つまたは 2 つのブランチが存在する可能性があります。リストとツリーの両方に事実上 2 つの「コンストラクター」があるため、ほとんどのルールには 2 つの本体があり、1 つは空のケースを処理し、もう 1 つは帰納的なケースを処理します。言語文法などのより複雑な構造には、2 つ以上の基本パターンが含まれる場合があり、通常はそれらすべてを個別に処理するか、特定の 1 つのパターンを探すだけになります。

演習として、search、insert、height、balanceまたはis_balancedその他のさまざまなツリー クエリを作成して、プロセスに慣れることができます。

于 2013-01-19T05:56:35.937 に答える