Prolog 中的双向链表

Question

我在业余时间学习 Prolog 大约 8 个月到一年，现在我正着手解决实现一些经典数据结构和算法的问题。

我有兴趣在 Prolog 中实现双重 linked 列表，但对如何进行感到困惑。我被 Prolog 吸引是因为我对 "logical purity" .

感兴趣

我似乎非常适应面向对象的范例，以至于超出了简单的范围，没有它我就无法继续！

对于双 linked 列表的参考，我的意思类似于 link 中描述的内容：

Double Linked List

Answer 1

Prolog 中双链表的一种可能具体化是使用 zipper。如果您不熟悉这个概念，请参见

https://en.wikipedia.org/wiki/Zipper_(data_structure)

拉链允许您前后导航列表，同时提供对当前元素的访问。因此，它提供了双向链表所共有的功能。 Logtalk（您可以运行使用大多数 Prolog 编译器）包括对 zippers 的库支持。 zipper协议可以浏览：

https://logtalk.org/library/zipperp_0.html

此协议由 zlist 对象为列表实现。您可以在以下位置浏览其代码：

https://github.com/LogtalkDotOrg/logtalk3/blob/master/library/zlist.lgt

请注意，大多数谓词都是纯谓词，其中一些谓词由事实定义。还有一个用法示例：

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/slides

Answer 2

这是一个不断弹出的问题。你真的需要解释你试图用这个双向链表做什么。我很想再次将其归档到我的 collection 令人愉快的 XY problem 展览中。

题目中的popular opinion是"the easiest way to get to the real problem is usually asking Why five times".

所以：为什么需要双向链表？你在实施队列吗？您想要双向遍历的排序列表？还有别的吗？

为了让这个答案更真实：

如果您使用普通列表，则可以在需要另一端时将其反转。

如果你需要一个可以从两端推入并从一端弹出的队列，你可以使用 Prolog 队列：

queue_empty(q(0, Q, Q)).
queue_back(q(N, Q, [X|Q0]), X, q(s(N), Q, Q0)).
queue_front(q(N, Q, Q0), X, q(s(N), [X|Q], Q0)).

这真的取决于，为什么你需要双向链表？你的用例是什么？

Answer 3

正如在对原始问题的评论中所讨论的那样，如 SQL 中所述，您可以在 Prolog 中断言可用作链表的事实：

head_node(Id).
node(Id, Data, LeftId, RightId).

您可以将原子 nil 指定为空值。

作为一个非常简单的例子：

head_node(a).

node(a, 123, nil, c).
node(b, 214, c, nil).
node(c, 312, a, b).

然后您可以编写谓词来处理此数据：

remove_node(NodeId) :-
    node(NodeId, _, LeftId, RightId),
    ...

...的其余部分可以用retract、assertz等来写。但是，正如Guy Coder在他的评论中指出的那样，这缺乏逻辑纯度，这似乎是最初的追求。数据结构使用起来很麻烦，正如我在评论中提到的，最好找到更合适的 Prolog 式方法来解决给定的问题，而不是假设必须使用更适合不同类型的模式来解决它语言。

Answer 4

使它成为双向链表的原因是它有两个链接而不是一个链接，指向列表中的上一项和下一项。所以我们可以制作一个 node(Value, Previous, Next) 结构并像这样手动制作列表：A = node(1, nil, B), B = node(2, A, nil).。我们可以用类似的方式制作更长的列表，只是创建更多的中间变量。

将其转换回 "normal" 列表看起来像这样：

dl2list(node(X, _, nil), [X]).
dl2list(node(A, _, node(X,Y,Z)), [A|Rest]) :- dl2list(node(X,Y,Z), Rest).

这没有特别使用 "previous" 指针，但您可以看到它有效：

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   dl2list(A, L).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [1, 2, 3, 4] .

我们也可以向后构建，从末尾开始：

dl2listrev(node(X, nil, _), [X]).
dl2listrev(node(A, node(X,Y,Z), _), [A|Rest]) :- dl2listrev(node(X,Y,Z), Rest).

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   dl2listrev(D, L).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [4, 3, 2, 1]

要从一个列表构造一个双向链表，你需要比这两个更强一点的东西：

l2dl(L, DL) :- l2dl(L, DL, nil).

l2dl([X], node(X, Prev, nil), Prev).
l2dl([X,Y|Xs], node(X, Prev, Next), Prev) :- 
    l2dl([Y|Xs], Next, node(X, Prev, Next)).

您可以在此处看到双向工作：

?- l2dl([1,2,3,4], X), dl2list(X, L).
X = node(1, nil, node(2, _S1, node(3, _S2, _S3))), % where
    _S1 = node(1, nil, node(2, _S1, node(3, _S2, _S3))),
    _S2 = node(2, _S1, node(3, _S2, _S3)),
    _S3 = node(4, node(3, _S2, _S3), nil),
L = [1, 2, 3, 4]

这里：

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   l2dl(L, A).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [1, 2, 3, 4]

Prolog 中的双向链表

Doubly Linked List in Prolog

prolog

doubly-linked-list

logical-purity