文章/答案/技术大牛

发布

社区首页 >问答首页 >Prolog编程--解决方案的路径方法

问Prolog编程--解决方案的路径方法
EN

Stack Overflow用户

提问于 2011-09-28 09:09:56

回答 2查看 981关注 0票数 1

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

有人能在这方面给我个建议吗。我非常感谢你的帮助。

我给出了一个我正在处理的例子，并且在这里找到了一个关于堆栈溢出的解决方案，但是我要寻找的是他是如何做到的，他是如何找到答案的:)

写一个使列表变平的谓词flatten，例如flatten([a，b，c，d，[1,2]，foo]，X)将给出X=a，b，c，d,1,2，foo。

这就是我在堆栈溢出中找到的答案：

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).

这个答案属于用户古斯布罗，由用户Parhs询问，我试图找到一种方法联系用户，询问他如何得到这样的答案，但我做不到。

非常感谢。

prolog

回答 2

Stack Overflow用户

发布于 2011-09-28 14:01:47

嗯，我能说的是，解决问题的方法在很大程度上取决于问题本身。有一组问题可以使用递归来解决，其中Prolog非常适合于解决这些问题。

在这类问题中，我们可以通过将一个较大的问题分成两个或多个案例类来得到它的解决方案。

在一个类中，我们有“基本案例”，当输入不能被进一步划分为更小的情况时，我们提供了一个问题的解决方案。

另一个类是“递归案例”，我们将输入分成几个部分，分别对它们进行求解，然后“加入”结果，为这个较大的输入提供一个解决方案。

在flatten/2的示例中，我们想要将一个项目列表作为输入，其中每个项目也可能是一个列表，其结果将是包含输入中的所有项的列表。因此，我们把这个问题分成两个部分。我们将使用一个辅助参数来保存中间平坦的列表，这也是我们实现平坦/3的原因。

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

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

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

flatten([], Flattened, Flattened).

现在我们开始递归步骤。这涉及到输入列表和将问题分成两个步骤。第一步是将此输入列表的第一项压平。第二步是递归地将其其余部分扁平化：

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

好的，所以对( item，L1，平坦的)的调用使第一项变平，但作为中间列表传递给未绑定变量L1。这只是一种诡计，因此在谓词返回时，变量L1仍然保持无界，并且平坦的变量为...|L1形式，其中.是项目的扁平项。

下一步，它调用flatten(Tail，L，L1)，使输入列表的其余部分平坦，并且结果与L1有界。

我们的最后一个子句实际上是另一个大小写，它处理单个项(不是列表)。因此，我们有：

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

它检查项目是否是一个列表，当它不是一个列表时，它将结果绑定为一个使用head=Item的列表，并将中间扁平的列表作为尾部绑定。

票数 2

Stack Overflow用户

发布于 2011-09-29 17:01:39

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

以下是我对这个问题的解决方案：“把列表(列表.)的列表压平”。我给它加了注解，以显示我是如何到达那里的：

首先，让我们定义解决方案的公共接口。我们定义了flatten/2。它的主体由调用内部实现flatten/3组成，它接受一个累加器，种子作为空列表。平坦(X，R) :-平坦(X，[]，R)，那很容易。
内部谓词flatten/3稍微复杂一些，但不太复杂。

- First, we have the boundary condition: the empty list. That marks the end of what we need to do, so we unify the accumulator with the result:

平坦( []，X，X )。

-下一个(也是唯一的)其他情况是一个非空的列表。为此，我们将检查列表的首字母。我们这里的规则是，它需要扁平化并附加到结果中。编程的一个好规则是编写描述性代码，Prolog本身是一种描述性的语言，而不是过程性语言:一种描述问题的解决方案，并让推理机解决问题。

那么.让我们来描述一下现在需要发生的事情，然后讨论一下将列表的头压平的机制：

平坦(X_ Xs，T，Y) :- flatten_head(X，X1)，附加(T，X1，T1)，扁平(X，T1，Y)。

这也很容易。

这就是整个解决方案的实质，就在这里。我们把我们的问题分成了三个部分：

特例(空列表)
正常情况(非空列表)
如何处理列表中的每个元素(尚未定义)。

让我们继续讨论如何扁平单个list元素的实现。这也很简单。这里有两种情况:列表项可能是列表，也可能是其他东西。

首先，list元素可能是一个未绑定的变量。我们不希望出现不规范的行为，比如无界递归发生，所以让我们立即处理，不允许无界项(目前)。如果元素是绑定的，我们将尝试通过调用公共接口flatten\2 (oooooooh...more递归！)来使其平坦。这完成了两件事

- First, it tells us whether we've got a list or not: `flatten/2` fails if handed something other than a list.
- Second, when it succeeds, the job of `flatten_head/2` is done.

下面是代码：

平头(X，Y) :- nonvar(X)，平坦(X，Y).

最后，我们必须考虑的最后一种情况是列表元素不是列表(未绑定的vars、原子或其他prolog项)。这些已经是“平面”的...all，我们需要做的是将它们包装为单个元素列表，以便调用方(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] ) .

每一个步骤都很简单。识别这些片段并将它们编织在一起是很困难的(尽管有时候，弄清楚如何阻止递归可能不那么明显)。

一些学习资源

要理解递归，您必须首先了解递归-匿名。

埃里克罗伯茨的http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471816523.html (1986年)可能是最好的(只有？)书中专门介绍了开发递归视角的WRT开发软件.有一个更新的版本http://www.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000611.html (2006年)，虽然我还没有看到它。

当然，这两本书都可以从通常的地方买到:鲍威尔的，亚马逊的等等。