私は Prolog を勉強していますが、レッスンについていけなかったので、SWI Prolog 述語で構築されたmaplistの特定の使用法に関連していくつか疑問があります。
それでは、私の状況を説明しましょう。
addavl(Tree/Height, Element, NewTree/Height)
要素Element
をAVLツリーTree
(この元のツリーの高さ)に挿入し、新しい高さを含むHeight
新しいAVLツリーを生成する名前の個人的な述語がありますNewTree
Element
Height
要素のリストがあり、これらの要素を AVL ツリー (最初は無効) に追加するので、次の述語があります (問題なく動作します)。
SWI Prolog 組み込みの述語の使用に関連するいくつかの疑問がありますmaplist/4
。また、このすべての述語の一般的な解釈が正しいかどうか、または何かが欠けているかどうかもわかります。
/* Predicate that from a given list of elements build an AVL Tree: */
buildTree(List,Tree):-
length(List, N), % N: the number of element in List
/* Create L1 as a list that have the same number of element of List
For example if List have N=4 element L1=[A,B,C,D] where A,B,C,D
are variable that are not yet set
*/
length(L1,N),
/* Se fosse: append(L1,[Tree],NewList) otterrei: NewList=[A,B,C,D|Tree]
ma essendo NewList=[_|L2] so L2=[B,C,D|Tree]
*/
append(L1,[Tree],[_|L2]),
/* Put the couple (nil,0) in the L1 head so I have that A=(nil,0) that
represents an empty AVL tree:
*/
L1=[nil/0 |_],
/* Call addavl passing as parameter the tree in the L1 head, the value
to insert in the List Head and the head of L2 as the current new Tree-
When the variable Tree is reached it represents the final AVL tree
*/
maplist(addavl, L1, List, L2).
述語全体の私の解釈は次のとおりです。
最初の変数には、AVL ツリーに挿入するN
元の要素リストの長さが含まれますList
次に、元のリストと同じ数の要素L1
を持つ新しいリストが作成されますが、この場合、まだ値が設定されていない変数が含まれています。List
L1
たとえば、元の要素リストが次
List = [5, 8, 3, 4]
の場合、リストは次のL1
ようになりL1 = [A, B, C, D]
ますA, B, C, D
。
ここで、満たさなければならない次のステートメントがあります。
append(L1,[Tree],[_|L2]),
私はこのように読んだ:
append(L1,[Tree],NewList)
代わりに前のステートメントがあれば、次のようになります。
NewList = [A,B,C,D,Tree]
ここで、 はリストA,B,C,D
の以前の設定されていない変数であり、新しい設定されていない変数です。L1
Tree
しかし、私の場合はNewList = [_|L2]
そうL2 = [B,C,D,Tree]
です。
前のappend
操作の意味はL2
、最初にn
非評価変数を含むリストの作成です (前の例では、4 つの非評価変数: B,C,D
、Tree
)。
これらの変数はそれぞれ、元のリストに新しい要素が挿入されたツリーを表しますList
したがって、最初に、プログラムは次の命令によって、このリストの先頭に void AVL ツリーを配置します (私の例ではA
変数内) L1=[nil/0 |_]
。
したがって、変数の先頭には、L1
高さが 0 のボイド ツリーがあります (ボイド ツリーは正しい AVL ツリーです)。
そして今、私は最初の疑いを持っています:前の操作でリストのヘッド変数を評価しましたL1
が、この操作の前に、次のNewList=[_|L2]
ステートメントを使用してリストを作成しました:
append(L1,[Tree],[_|L2])
これは、リストの_
無名変数がAVL ツリー[_|L2]
と一致することを意味しますか? これは、リストを追加するリストを作成した後にヘッドnil/0
を評価した場合にも、このように機能しますか?L1
[_|L2]
L1
[Tree]
わかりました、私の解釈が正しければ、述語に組み込まれたmaplist SWI Prologがどのように正確に機能するかに関連しているという2 番目の疑いに進みます。
私は持っている:
maplist(addavl, L1, List, L2).
この述語は正確には何をしますか?
公式ドキュメントを読む: http://www.swi-prolog.org/pldoc/man?predicate=maplist%2F2
次のように動作するように私には思えます:
リストの各要素で満たさなければならないGOALであるaddavl
述語があります
addval
その述語は次のように機能する ことを思い出してくださいaddavl(Tree/Height, Element, NewTree/Height)
。
そう:
1) L1
AVL ツリーのリストです (最初は void AVL ツリーです: nil/0
)
2)List
は、挿入する要素を含む元のリストです
3)L2
は、これから作成する AVL ツリーを含むリストです。
したがって、現在は次のように機能していると思います。
最初に の先頭から void AVL ツリー ( nil/0
) をL1
取得し、List から追加する最初の要素を取得し、GOAL を実行し (この要素を void AVL ツリーに挿入します)、結果をL2
リストの先頭に配置します (つまり、私の前の例はB
変数なので、B
変数には要素の最初の要素を含む AVL ツリーが含まれますList
) list**
次に、要素リストの他のすべての要素を挿入してこの手順を繰り返しますList
。最後に、リストの最後の要素L2
(Tree
変数) は、すべての要素が挿入された最終的な AVL ツリーを表します。
私の推論は正しいですか、それとも何かが欠けていますか?