-1

我正在学习 Prolog，但我无法按照课程学习，所以我对SWI Prolog 谓词中内置的maplist的特定用途有一些疑问。

那我来解释一下我的情况：

我有一个名为的个人谓词addavl(Tree/Height, Element, NewTree/Height)，它将元素Element插入到 AVL 树中（原始树的高度Tree在哪里）并生成一个新的 AVL 树，命名为包含并具有新的高度HeightNewTreeElementHeight

现在我有一个元素列表，我会将这些元素添加到 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]ListA,B,C,D的前一个未设置变量在哪里，并且是一个新的未设置变量。L1Tree

但就我而言，我就是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 树）

现在我有了第一个疑问：通过前面的操作，我已经对列表的 head 变量进行了 valorized，L1但是在此操作的前面，我NewList=[_|L2]使用以下语句创建了列表：

append(L1,[Tree],[_|L2])

这意味着列表的_匿名变量与AVL树[_|L2]匹配？如果我在创建列表附加列表之后对头部进行了nil/0valorized，那么这种方式也可以工作？L1[_|L2]L1[Tree]

好的，如果我的解释是正确的，请继续我的第二个疑问，它与maplist SWI Prolog 内置谓词的工作方式有关..

我有：

 maplist(addavl, L1, List, L2).

这个谓词到底是做什么的？

阅读官方文档：http ://www.swi-prolog.org/pldoc/man?predicate=maplist%2F2

在我看来，它的工作方式如下：

我的addavl谓词是必须在列表的每个元素上满足的 GOAL

记住addval谓词以这种方式起作用： addavl(Tree/Height, Element, NewTree/Height).

所以：

1）L1是AVL Tree的列表（第一个是void AVL Tree nil/0：）

2)List是包含要插入的元素的原始列表

3)L2是包含我将创建的 AVL 树的列表。

所以我认为现在可以通过以下方式工作：

nil/0首先从 的头部取出 void AVL Tree ( ) L1，从 List 取出第一个元素 do add，执行 GOAL（将此元素插入到 void AVL Tree 中）并将结果放入L2列表头部（即，根据我之前的示例是B变量，因此B变量包含包含元素的第一个元素的 AVL 树List）列表**

然后重复此过程，将所有其他元素插入到元素列表中List，最后，列表的最后一个元素L2（Tree变量）将代表最终的 AVL 树，所有元素都插入其中。

我的推理是正确的还是我遗漏了什么？

4

1 回答 1

2

在 Prolog 中，我们说“尚未实例化的变量”或“未实例化的变量”。

关于L1=[nil/0 |_]，我们可以称之为“用初始值初始化”。

_in[_|L2]确实与 init 值匹配，我们并不关心它。

（这给出了调用的想法append(L1, [Tree], [nil/0 | L2])，而不是原始代码中的两个调用）。

是的，操作顺序并不重要。X=t(A), A=2或A=2, X=t(A)两者都导致相同的替换，A=2, X=t(2).

maplist( pred, ...Lists ...)工作，因此pred必须满足列表中的元素，成对（或按列）。例如maplist(plus, [1,2,3],[4,X,8],[5,6,Y])。

列表L1和L2两者共享结构：

nil/0   B   C   D   Tree
------------------
       L1
        -----------------
               L2

maplist通过按列将它们馈送到以下位置来查看并处理它们addavl：

nil/0   B     C     D       % L1
 E1     E2    E3    E4      % List
 B      C     D    Tree     % L2

所以是的，它就像你说的那样。

我不认为你的老师会接受这个作为答案。您应该改为编写直接递归解决方案。两种变体都描述了相同的迭代计算过程，即逐步将元素添加到树中，使用前一个调用的输出作为下一个调用的输入。但是在任何给定的实现中，一个可以比另一个更好地优化。在这里使用列表很可能比递归变体效率低。

于 2013-05-01T08:40:31.477 回答