问题标签 [difference-lists]

listdiff 是一对其 car 为 L 且其 cdr 为 eq 的对？到 L，或到 (cdr L)，或到 (cdr (cdr L)))，等等。 listdiff 的 cdr 不必是列表；它可以是任何对象。

一个 listdiff D 表示 (car D) 在 (cdr D) 之前的前缀。例如，假设 ils 是不正确的列表 (aeiou . y)。然后 (cons ils ils) 返回一个空的 listdiff， (cons ils (cdr (cdr ils))) 返回一个与列表 (ae) 具有相同元素的 listdiff，并且 (cons (cdr ils) 'y) 返回一个 listdiff与 (eiou) 相同的元素。相反， (cons '() ils) 和 (cons ils (append '(aeiou) 'y)) 都不会返回 listdiff。

我想在 Racket 上创建以下程序：

(listdiff?obj)

如果 obj 是一个 listdiff，则返回 #t，否则返回 #f。

任何人都可以给我指示吗？

在Haskell 中，差异列表

[a] 具有高效连接操作的列表表示

似乎是在功能组合方面实现的。

但是，函数和（动态）函数组合也必须以某种方式在计算机内存中使用数据结构来表示，这引发了一个问题，即如何在 Haskell 中实现dlist而不使用函数组合，而是通过一些基本的纯函数基于节点的数据结构。如何在与函数组合相同的性能保证下做到这一点？

我只是在学习 Prolog 和 Prolog 中差异列表的概念，所以请多多包涵。

我有以下代码：

现在，如果我在 SWI 解释器中附加列表 [1,2,3] 和 [a,b,c] 它会产生列表列表

而如果我像这样直接调用 append_dl：

有用...

我在做什么错，应该如何正确使用差异列表来包装这些功能？

谢谢你们的帮助：D

以下程序的意图如下 clist_d(f(a,f(a,a)),R) 结果是所有基本参数的列表，例如 R = [a,a,a]

但是，该程序包含一个错误。使用以下查询运行程序：

如您所见，产生一个错误，单独测试差异列表我得到以下结果

我在我的主程序中犯了一个错误，但我不知道要添加什么来让我的 diffapp 在那里工作。

我目前正在参加 Prolog 课程。

我熟悉[A|B]Prolog 中列表的表示法，但老师表明这[a,b,c|X]-X也是一种有效的列表方式，我们在其中引用了列表的尾部。但是，当我使用 Swi-Prolog 进行尝试时，我收到以下错误：ERROR: Undefined procedure: (-)/2 (DWIM could not correct goal).

(-)/2 运算符是刚刚在标准 Prolog 中定义但在 Swi-Prolog 中没有定义，还是我遗漏了什么？

我试图在不“破坏”列表的情况下找到最后一项（所有数字）。

我目前拥有的是这样的：

Max2 是一个在普通列表中查找最后一项的函数：

当我尝试使用一个项目的列表时，它可以工作 - 否则会失败：

我尝试了其他方法，但是当我给它一个包含一个项目的列表时，它转换了它：

所以我不能继续使用 X 作为自由变量。

我希望我写得很清楚。提前谢谢了。

prolog 中的上述代码检查列表的给定输入是否等于 a 和 b。

如

这涉及递归和差异列表。任何人都可以解释底层递归如何一步一步地检查 a 和 b 是否相等。

我正在阅读 Ivan Bratko 的 Prolog Programming for Artificial Intelligence 一书，但我之前没有使用 Prolog 的经验。在书中，列表的子列表关系被表述为：

关系如下：

为什么我们不只是将列表分解为两个列表并检查其中一个列表是否与 S 匹配，这对我来说似乎很奇怪？

当我阅读第 13 章时，Real World Haskell我想到了Difference Lists.
作者说，在命令式语言中，如果我们想将一个元素附加到一个列表中，代价就是O(1)我们会保留一个指向最后一个元素的指针。但是在 Haskell 中，我们有immutable对象，所以我们每次都需要遍历列表并将元素附加到末尾，因此0(n).

而不是[1,2,3]++[4]++[5]
我们可以使用部分应用程序：(++4).(++5) [1,2,3].

我不明白这如何更有效，因为：
- 当我这样做时，(++[5]) [1,2,3]它仍然是O(n)，然后0(n)是另一个(++4)

引用

我知道这种方法会很急切，所以我们没有像作者所说yet to be applied methods的那样保留左操作数，而不是保留左操作数small，但是....我们仍然对每个追加执行遍历。

给定一个列表：[1...100]并且想要追加1,2我仍然会遍历它2，因为我会：

1. f(f([1..100]))= f([1..100,1])- 遍历 1 次并附加1

2. [1..100,1,2]- 遍历第二次追加2

有人能告诉我这在时间复杂度上如何更有效吗？（因为space-complexity 不再是因为thunks, like foldl'）

附言

我知道规范的答案，并且我也阅读了这一章，我觉得这很有帮助。
我知道您可以O(1)通过使用 追加到左侧来实现复杂性:，但它不会类似于++.

如果我使用f=(:)on a= [1,2,3] ：
(f 4 . f 5) $ a
我可以说我0(1)对每个追加都有效率，因为我总是在左侧追加，但我不会得到[1,2,3,4,5]，我会得到[5,4,1,2,3]，那么在这种情况下difference list，对于追加的单一操作如何更有效一个元素？

我需要做一个类似的练习： Prolog - 将列表分成两半，反转前半部分。

我被要求将一个字母列表放入两个大小相等的列表（我猜是偶数大小的原始列表）或一个比另一个大一个元素（奇数大小的列表），并在我时反转第一个m ，但仅使用差异列表。

这些是必需的查询和输出

这是我使用前面示例的代码，但经过修改，我不知道如何正确比较两个列表从输入中“扣除”它们并产生[d,e,f]？

这是当前的跟踪：

谢谢