4

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

我对在 Prolog 中实现双向链表很感兴趣，但对如何进行感到很困惑。我被 Prolog 所吸引是因为我对“逻辑纯度”感兴趣。

看来我是如此适应面向对象的范式，以至于超出了简单的范式，没有它我就无法继续！

作为双向链表的参考，我的意思类似于此链接中描述的内容：

双链表

4

4 回答 4

3

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

于 2019-01-27T23:33:13.007 回答
2

正如对原始问题的评论中所讨论的，就像在 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 方式来解决给定问题，而不是假设必须使用更适合不同类型的模式来解决它的语言。

于 2019-01-28T11:52:52.917 回答
2

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

关于这个话题的流行观点是“解决真正问题的最简单方法通常是问为什么五次”。

那么：为什么需要双向链表？您是否正在实施队列？您想要双向遍历的排序列表？还有什么？

为了让这更像是一个真正的答案：

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

如果您需要一个可以从两端推入并从一端弹出的队列，您可以使用 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)).

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

于 2019-01-28T06:22:51.557 回答
2

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

将其转换回“正常”列表将如下所示：

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]
于 2019-01-28T18:11:06.610 回答