1

只是通过一些教程，我发现了一些高级递归过程，比如 flatten。我试图在谷歌上找到涉及多个递归（头尾）但无法得到我需要的结果的类似示例。

您能否推断出一些涵盖高级列表回避（头部，尾部）的谓词或教程？

4

1 回答 1

4

只是为了扩展@hardmath 的意思，让我们看一下列表的定义：

  • 基本情况：[]
  • 归纳案例：[Head|Tail]

使它成为递归数据结构的原因在于Tail它也是一个列表。所以当你看到时[1,2,3]，你也在看到[1|[2|[3|[]]]]。让我们证明一下：

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

因此，更“高级”的递归形式是涉及更复杂的递归数据类型或更复杂的计算的形式。大多数人接触到的下一个递归数据类型是二叉树，二叉树有一个很好的特性，即每个节点有两个分支，所以让我们先看看树。

首先，我们需要一个很好的定义，比如列表中的定义。我提出以下建议：

  • 基本情况：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).

因此，通过比较这两者，您可以清楚地看到递归处理数据结构的标志：

  • 您将获得一个递归数据结构，根据基本案例和归纳案例定义。

  • 您编写规则的基础来处理基本情况。

    这一步通常很明显；在长度或大小的情况下，您的数据结构将有一个空的基本情况，因此您只需将零与该情况相关联。

  • 你写下你的规则的归纳步骤。

    归纳步骤采用数据结构的递归案例并处理该案例添加的任何内容，并将其与递归调用您的规则以处理数据结构的“其余部分”的结果相结合。

因为列表只在一个方向上递归，所以在大多数列表处理规则中只有一次递归调用。因为树有两个分支，所以可以有一个或两个，这取决于您是需要处理整棵树还是只走一条路径。列表和树实际上都有两个“构造函数”，因此大多数规则都有两个主体，一个处理空案例，一个处理归纳案例。更复杂的结构，例如语言语法，可以有两个以上的基本模式，通常你要么分别处理它们，要么只寻找一种特别的模式。

作为练习，您可能想尝试编写search、insert、height或balance以及is_balanced各种其他树查询来更熟悉该过程。

于 2013-01-19T05:56:35.937 回答