问题标签 [difference-lists]

我试图理解 Prolog 中的差异列表，但我正在努力正确地实现一个，每次我尝试这样做时，我都会得到一个列表列表，但这不是我想要的。我正在尝试实现附加谓词，但到目前为止运气不佳。很少尝试，所有这些都不起作用。

或者

结果与第一个相同，（它们似乎基本相同）。我在一本书中有一个确实有效的例子（尽管它不是谓词），但我不明白其中的区别。X被实例化为正确的答案[a,b,c,z]，这与我的第二个示例有何不同？

我错过了什么？谢谢。

我正在阅读有关 Prolog 中上下文无关语法的教程，他们在页面底部提到使用差异列表在 Prolog 中实现上下文无关语法，其中包括以下代码块：

它提到：

仔细考虑这些规则。例如，s 规则说：我知道列表 X 和 Z 表示一个句子，如果 (1) 我可以消费 X 并留下一个 Y，并且 X 和 Y 对表示一个名词短语，并且 (2)然后我可以继续消费 Y 留下 Z，YZ 对代表一个动词短语。np 规则和第二个 vp 规则的工作方式类似。

和

将第一个列表视为需要使用的内容（或者如果您愿意：输入列表），将第二个列表视为我们应该留下的内容（或：输出列表）。从这个（相当程序）的角度来看，差异列表

代表一个女人射杀一个男人的句子，因为它说：如果我把左边的符号都吃光了，把右边的符号都留下了，那么我就有了我感兴趣的句子。也就是我们感兴趣的句子是这两个列表内容的区别。

这就是我们需要知道的关于重写我们的识别器的差异列表的全部内容。如果我们简单地记住消费某物并留下某物的想法，我们将获得以下识别器：

作为解释，但这并没有做任何事情来向我澄清这段代码。我知道它比 using 更有效append/3，但至于消耗事物并将其他事物抛在后面的概念，它似乎比以前的append/3实现更令人困惑，我就是无法理解它。此外，当我将该代码复制并粘贴到Prolog 可视化器中以尝试理解它时，可视化器说有错误。任何人都可以对此有所了解吗？

我尝试使用列表编写 Prolog 程序。但是，我必须使用差异列表，输出应该是：

列表的第 i^个元素与列表的第 (n-i+1)^个元素相同，n 是列表的长度。例如，[a,X,c,b,Y]应该给出X = b和Y = a。我在其他问题中找不到类似的回文示例。

到目前为止，我已经实现：

但是，我无法完成。请帮我！

我有一个新类型来代表 Hughes 的列表（即列表构造）：

有一些功能可以处理它：

该Monoid实例与上述功能一样简单：

...但是当我到达FunctorandApplicative实例时，麻烦就出现了。到目前为止，这是我想出的：

我的问题是我不喜欢使用unsafeCoerce. 有没有办法在Functor不使用实例的情况下设计实例，还是不可避免？

此外，我将如何实现Monad此数据类型的实例？

编辑：与DList包中不同，我想保持性能改进，即不评估[a] -> [a]但映射它。

我在用纸笔解决差异列表问题时遇到了问题，而不是在 SWI Prolog 的帮助下（这些天我正在准备我的逻辑编程考试）。

这是问题：

明确给出查询 ?- q(t) 的所有基本项 t 的集合。成功。以封闭形式陈述集合的正式定义（即，不要使用递归定义）。

答案是：

{[t1, . . . , tn-1, tn, tn-1, . . . , t1] | n > 0, ti 是所有 i ∈ {1, . . . , n}}

我使用了 [1,2,3,2,1]，它给了我真正的预期答案。

我不明白解决这个问题的步骤是什么？

差异列表是一种“解决”变量在序言中不可变的事实的方法吗？

即，如果我使用差异列表实现附加：

然后运行：

在某种程度上，X 已被用作可变变量。为了我们的意图和目的，它已经改变了吗？

换句话说，我们能够修改 X（可变）而不是必须构造一个新列表，比如 Z（不可变），这一事实使差异列表具有吸引力。那么为什么不只使用可变变量呢？

更新：

How can I build a predicate in prolog that receives a number and a list, I must insert the number in the list by the tail

I tried inserting the number in the list by the head: insert(H,[P|Q],[H,P|Q]). and it works, but how can I do it by the tail?

由于我想避免成本append/3，我使用差异/开放列表。

然而，开放列表的问题是member/2通过将元素添加到尾部来对开放列表做出反应。例如：

这是正确的行为，因为打开列表具有无限的“尾部”，并且该member/2函数将此尾部/孔（变量）与成员的第一个参数统一起来。

但是，我正在寻找一种方法来检查打开列表中是否有一个等于给定元素的元素。我怎样才能做到这一点？

空列表……对于像我这样的 Prolog 初学者来说很奇怪。我会说不可能将空列表写[]为差异列表T1-T2，就像不可能将原子写为差异列表一样。但是，我猜想要使用递归，必须有一种方法可以[]在差异列表设置中使用。我已经谷歌了，但我找不到答案，而 Bratko（人工智能的 Prolog 编程）只是简单地触及了这个主题。

那么，是否可以在 Prolog 中编写一个空列表作为差异列表，如果可以，它如何以及何时有用？

当我在一个空列表上写下这个问题作为差异列表时，我想测试我对这些结构的了解。然而，当我尝试像比较不同符号这样简单的事情时，似乎我错了，我不明白差异列表的实际情况。

我在 SWI-Prolog 和 SICStus 上对此进行了测试。我验证了这个符号，因为这是 Bratko 的 Prolog Programming for AI，第 210 页中的写法，但显然不可能统一。这是为什么？这些符号不具有相同的声明意义吗？