Prolog 编程 - 解决方案的途径 [英] Prolog programming - path way to a solution

查看：53 发布时间：2021/6/22 18:46:05 prolog

本文介绍了Prolog 编程 - 解决方案的途径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我正在大学学习 prolog 并面临一些问题.我已经发现的只是解决问题的方法.但是，我对思考方式更感兴趣，即如何获得这样的解决方案.

有人可以给我关于这个领域的建议吗?我将衷心感谢您的帮助.

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

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

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

flatten(List, Flattened):-展平(列表，[]，展平).展平([]，展平，展平).flatten([Item|Tail], L, Flattened):-展平(项目，L1，展平)，展平(尾，L，L1).展平(物品，展平，[物品|展平]):-\+ is_list(项目).

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

非常感谢.

解决方案

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

这是我对展平列表(列表......)"问题的解决方案.我已经注释了它以显示我是如何到达那里的:

首先，让我们定义解决方案的公共接口.我们定义 flatten/2.它的主体由对内部实现 flatten/3 的调用组成，它接受一个累加器，作为空列表播种.
```
flatten ( X , R ) :-展平 ( X , [] , R ) ,.
```
那很简单.
内部谓词 flatten/3 有点复杂，但不是很复杂.
- 首先，我们有边界条件:空列表.这标志着我们需要做的事情结束，因此我们将累加器与结果统一起来:
```
flatten( [] , X , X ).
```
- 下一个(也是唯一的)其他情况是一个非空列表.为此，我们检查列表的头部.我们的规则是它需要展平并附加到结果中.一个好的编程规则是编写描述性代码，Prolog 本身是一种描述性，而不是过程性语言:描述问题的解决方案并让推理引擎整理一下.
  那么...让我们描述一下现在需要发生的事情，并讨论压平列表头部的机制:
```
flatten( [X|Xs] , T , Y ) :-flatten_head(X,X1) ,追加(T，X1，T1)，展平( Xs , T1 , Y ).
```
  那也很简单.

这就是整个解决方案的精髓，就在那里.我们已将问题分解为 3 个部分:

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

让我们继续讨论如何展平单个列表元素的实现.这也很容易.这里有两种情况:列表项可能是列表，也可能是其他内容.

首先，列表元素可能是一个未绑定的变量.我们不希望出现诸如无界递归之类的不良行为，所以让我们通过禁止无界项(暂时)来解决这个问题.如果元素被绑定，我们尝试通过再次调用我们的公共接口 flatten\2 来将它展平(oooooooh...更多递归！)
这完成了两件事
- 首先，它告诉我们是否有一个列表:flatten/2 如果传递的不是列表，则失败.
- 第二，当它成功时，flatten_head/2 的工作就完成了.
代码如下:
```
flatten-head( X , Y ) :-非变量(X) ,展平( X , Y ).
```
最后，我们必须考虑的最后一种情况是列表元素不是列表(未绑定的变量、原子或其他一些序言术语)的情况.这些已经是扁平的"……我们需要做的就是将它们包装成一个单一的元素列表，以便调用者 (flatten\3) 为其返回值"获得一致的语义:
```
flatten-head( X , [X] ).
```

完整代码如下:

flatten ( X , R ) :-展平 ( X , [] , R ).展平( [] , X , X ) .展平( [X|Xs] , T , Y ) :-flatten_head(X,X1) ,追加(T，X1，T1)，展平( Xs , T1 , Y ).平头(X，Y):-非变量(X) ,展平( X , Y ).扁平头( X , [X] ) .

每个步骤都很简单.识别各个部分并将它们编织在一起很困难(尽管有时，弄清楚如何停止递归可能并不那么明显).

一些学习资源

要了解递归，首先要了解递归—anonymous

Eric Roberts 的有人认为这是有史以来最好的书.天啊.

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

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

I am studying prolog at university and facing some problems. What I already found out is just solution to a problem. However, I'm more interested in the way to think, i.e. how to get such solution.

Can somebody give me an advise on this field. I would really appreciate your help.

I give an example I am coping with and also, found a solution on stackoverflow here, but what I looking for is how does he do that, how does he find the answer :)

Write a predicate flatten(List,Flat) that flatten a list, e.g. flatten([a,b,[c,d],[[1,2]],foo],X) will give X=[a,b,c,d,1,2,foo].

This is the answer I found on 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).

this answer belongs to user gusbro and asked by user Parhs, I have try to find a way to contact user gusbro to ask him how he can derive such answer but I cannot.

Thank you very much.

解决方案

First, I'll show you my approach to the problem, then I've got some resources for learning to think recursively.

Here's my solution to the problem "flatten a list of lists (of lists ...)". I've annotated it to show how I got there:

First, let's define the public interface to our solution. We define flatten/2. It's body consists of a call to the internal implementation flatten/3, which takes an accumulator, seeded as an empty list.
```
flatten ( X , R ) :-
  flatten ( X , [] , R ) ,
  .
```
That was easy.
The internal predicate flatten/3 is a little more complex, but not very.
- 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:
```
flatten( [] , X , X ).
```
- The next (and only) other case is a non-empty list. For this, we examine the head of the list. Our rule here is that it needs to flattened and appended to the result. A good rule of programming is to write descriptive code, and Prolog is itself a descriptive, rather than procedural, language: one describes the solution to the problem and lets the inference engine sort things out.
  
  So...let's describe what needs to happen now, and punt on the mechanics of flattening the head of the list:
```
flatten( [X|Xs] , T , Y ) :-
  flatten_head(X,X1)     ,
  append( T,X1,T1)       ,
  flatten( Xs , T1 , Y )
  .
```
  That, too, was easy.

That's the essence of the entire solution, right there. We've broken our problem into 3 pieces:

a special case (the empty list)
the normal case (a non-empty list)
what to do with each element in the list (not yet defined).

Let's move on to the implementation of how to flatten a single list element. That's easy, too. We've got two cases, here: the list item might be a list, or it might be something else.

First, the list element might be an unbound variable. We don't want untowards behaviour, like unbounded recursion happening, so let's take care of that straightaway, by disallowing unbound terms (for now). If the element is bound, we try to flatten it by invoking our public interface, flatten\2 again (oooooooh...more recursion!)

This accomplishes two things
- 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.
Here's the code:
```
flatten-head( X , Y   ) :-     
  nonvar(X) ,
  flatten( X , Y )
  .
```
Finally, the last case we have to consider is the case of list elements that aren't lists (unbound vars, atoms or some other prolog term). These are already "flat"...all we need to do is wrap them as a single element list so that the caller (flatten\3) gets consistent semantics for its "return value":
```
flatten-head( X , [X] ).
```

Here's the complete code:

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

Each individual step is simple. It's identifying the pieces and weaving them together that's difficult (though sometimes, figuring out how to stop the recursion can be less than obvious).

Some Learning Resources

To understand recursion, you must first understand recursion—anonymous

Eric Roberts' Thinking Recursively (1986) is probably the best (only?) book specifically on developing a recursive point-of-view WRT developing software. There is an updated version Thinking Recursively With Java, 20th Anniversary Edition (2006), though I've not seen it.

Both books, of course, are available from the Usual Places: Powell's, Amazon, etc.

You might also want to read Douglas Hofstadtler's classic Gödel, Escher, Bach: An Eternal Golden Braid Some consider it to be the best book ever written. YMMV.

Also available from the Usual Suspects:

A new book, though not directly about recursive theory, that might be useful, though I've not seen it (it's gotten good reviews) is Michael Corballis' The Recursive Mind: The Origins of Human Language, Thought, and Civilization

这篇关于Prolog 编程 - 解决方案的途径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文

Prolog 编程 - 解决方案的途径 [英] Prolog programming - path way to a solution

问题描述

相关文章

其他开发最新文章

热门教程

热门工具

登录关闭

Prolog 编程 - 解决方案的途径 [英] Prolog programming - path way to a solution

问题描述

相关文章

其他开发最新文章

热门教程

热门工具

登录 关闭

登录关闭