Prolog 编程 - 解决方案的途径

Question

我在大学学习序言并面临一些问题。我已经发现的只是解决问题的方法。然而，我更感兴趣的是思考的方式，即如何得到这样的解决方案。

有人可以给我关于这个领域的建议吗？我非常感谢你的帮助。

我举了一个我正在处理的例子，并且在这里找到了 stackoverflow 上的解决方案，但我寻找的是他是如何做到这一点的，他如何找到答案:)

编写一个谓词 flatten(List,Flat) 来展平 a列表，例如 flatten([a,b,[c,d],[[1,2]],foo],X) 将给出 X=[a,b,c,d,1,2,foo]。

这是我在 stackoverflow 上找到的答案：

flatten(List, Flattened):-
   flatten(List, [], Flattened).

flatten([], Flattened, Flattened).
flatten([Item|Tail], L, Flattened):-
  flatten(Item, L1, Flattened),
  flatten(Tail, L, L1).
flatten(Item, Flattened, [Item|Flattened]):-
  \+ is_list(Item).

这个答案属于用户 gusbro 并由用户 Parhs 询问，我试图找到一种方法联系用户 gusbro 询问他如何得出这样的答案，但我不能。

非常感谢。

Answer 1

嗯，我只能说，解决问题的方式很大程度上取决于问题本身。有一系列问题可以使用递归来解决，Prolog 非常适合来解决它们。

在此类问题中，可以通过将较大问题划分为两个或多个案例类来导出更大问题的解决方案。

在一类中，我们有“基本情况”，当输入无法进一步分为更小的情况时，我们提供问题的解决方案。

另一类是“递归情况”，我们将输入分成几部分，分别求解，然后“连接”结果以给出更大输入的解决方案。

在 flatten/2 的示例中，我们希望将一个项目列表作为输入，其中每个项目也可以是一个列表，结果应是一个包含输入中所有项目的列表。因此，我们将问题分成不同的情况。
我们将使用辅助参数来保存中间展平列表，这就是我们实现 flatten/3 的原因。

因此，我们的 flatten/2 谓词将仅使用空列表作为起始中间扁平列表来调用 flatten/3：

flatten(List, Flattened):-
   flatten(List, [], Flattened).

现在对于 flatten/3 谓词，我们有两个基本情况。第一个处理空列表。请注意，当输入为空列表时，我们无法进一步划分问题。在这种情况下，我们只将中间扁平列表作为我们的结果。

flatten([], Flattened, Flattened).

我们现在采取递归步骤。这涉及获取输入列表并将问题分为两个步骤。第一步是展平此输入列表的第一项。第二步是递归地展平其余部分：

flatten([Item|Tail], L, Flattened):-
  flatten(Item, L1, Flattened),
  flatten(Tail, L, L1).

好的，因此调用 flatten(Item, L1, Flattened) 展平第一个项目，但将未绑定变量 L1 作为中间列表传递。这只是一个技巧，以便在谓词返回时，变量 L1 仍然保持无界，并且 Flattened 将采用 [...|L1] 形式，其中 ... 是 Item 的扁平项。

下一步，调用 flatten(Tail, L, L1) 展平输入列表的其余部分，结果以 L1 为界。

我们的最后一个子句实际上是另一个基本情况，处理单个项目（不是列表）。因此我们有：

flatten(Item, Flattened, [Item|Flattened]):-
  \+ is_list(Item).

它检查 item 是否是列表，当它不是列表时，它将结果绑定为带有 h​​ead=Item 的列表，并将中间扁平列表绑定为 tail。

Answer 2

首先，我将向您展示我解决问题的方法，然后我有一些学习递归思考的资源。

这是我对“展平列表列表（列表......）”问题的解决方案。我对其进行了注释以显示我是如何到达那里的：

• 首先，让我们定义解决方案的公共接口。我们定义flatten/2。它的主体由对内部实现 flatten/3 的调用组成，它采用一个累加器，作为空列表作为种子。

  展平 ( X , R ) :-
    展平 ( X , [] , R ) ,
    。
  

  这很简单。

• 内部谓词flatten/3稍微复杂一点，但不是很复杂。

  • 首先，我们有边界条件：空列表。这标志着我们需要做的事情的结束，因此我们将累加器与结果统一起来：

    展平（[]，X，X）。
    

  • 下一个（也是唯一的）其他情况是非空列表。为此，我们检查列表的头部。我们这里的规则是它需要展平并附加到结果中。编程的一个好的规则是编写描述性代码，Prolog 本身就是一种描述性语言，而不是过程性语言：它描述了问题的解决方案并让推理引擎进行推理整理一下事情。

    所以...让我们描述一下现在需要发生什么，并把重点放在压平列表头部的机制上：

    展平( [X|Xs] , T , Y ) :-
      flatten_head(X,X1) ,
      附加（T，X1，T1），
      展平（ Xs ， T1 ， Y ）
      。
    

    这也很容易。

这就是整个解决方案的本质。我们将问题分为三部分：

• 特殊情况（空列表）
• 正常情况（非空列表）
• 如何处理列表中的每个元素（尚未定义）。

让我们继续实现如何​​展平单个列表元素。这也很容易。这里有两种情况：列表项可能是一个列表，也可能是其他东西。

• 首先，列表元素可能是未绑定的变量。我们不希望出现不良行为，例如无界递归的发生，因此让我们通过禁止无界术语（暂时）来直接解决这个问题。如果元素已绑定，我们会尝试通过再次调用公共接口 flatten\2 来展平它（oooooooh...更多递归！）

  这完成了两件事

  • 首先，它告诉我们是否有一个列表：如果传递的不是列表，flatten/2 就会失败。
  • 其次，当它成功时，flatten_head/2 的工作就完成了。

  代码如下：

  平头( X , Y ) :-     
    非变量(X) ,
    展平（ X ， Y ）
    。
  

• 最后，我们必须考虑的最后一种情况是列表元素不是列表的情况（未绑定的变量、原子或其他一些序言术语）。这些已经是“扁平的”...我们需要做的就是将它们包装为单个元素列表，以便调用者 (flatten\3) 获得其“返回值”的一致语义：

  平头（ X ， [X] ）。
  

这是完整的代码：

flatten ( X , R ) :-
  flatten ( X , [] , R )
  .

flatten( [] , X , X ) .
flatten( [X|Xs] , T , Y ) :-
  flatten_head(X,X1)      ,
  append( T,X1,T1)        ,
  flatten( Xs , T1 , Y )
  .

flatten-head( X , Y   ) :-
  nonvar(X)             ,
  flatten( X , Y )
  .
flatten-head( X , [X] ) .

每个单独的步骤都很简单。识别各个部分并将它们编织在一起是很困难的（尽管有时，弄清楚如何停止递归可能不太明显）。

一些学习资源

要理解递归，你必须首先理解递归——匿名

Eric Roberts 的 递归思考（1986）可能是最好的（唯一？）专门关于开发递归观点 WRT 开发软件的书。有更新版本用 Java 进行递归思考，20 周年纪念版 (2006)，虽然我还没看过。

当然，这两本书都可以从常见的地方获得：Powell's、Amazon 等。

• http ://www.amazon.com/Thinking-Recursively-Eric-S-Roberts/dp/0471816523
• http://www.amazon.com/Thinking-Recursively-Java-Eric-Roberts/dp/ 0471701467
• http://www.powells.com/biblio/61-9780471816522-2
• <一个href="http://www.powells.com/biblio/72-9780471701460-0" rel="nofollow noreferrer">http://www.powells.com/biblio/72-9780471701460-0

< img src="https://i.sstatic.net/OCqtU.jpg" alt="递归思考">

您可能还想阅读 Douglas Hofstadtler 的经典著作 哥德尔，埃舍尔，巴赫：永恒的金辫有些人认为这是有史以来最好的书。 YMMV。

也可从常见嫌疑人处获得：

• http://www.powells.com/biblio/62-9780140289206-1
• http://www.amazon.com/Godel-Escher-Bach-Eternal-Golden/dp/0465026567

一本新书，虽然不是直接关于递归理论，但可能有用，尽管我已经没看过（它得到了很好的评价）是 Michael Corballis 的 递归思维：
人类语言、思想和文明的起源