需要帮助理解附加列表元素的序言方法

发布于 2024-12-06 05:03:04 字数 557 浏览 0 评论 0原文

append([],Xs,Xs).
append([Head|Tail],List2,[Head|Tail2]):-
    append(Tail,List2,Tail2).

上面的追加方法将前两个参数槽中的元素添加到第三个参数变量中。

?-append([2,1], [3,4], X).
?-X=[2,1,3,4]

我在步骤中看到它的方式是（这可能是错误的）：

append(2 | [1], [3,4], 2 | X)
append([1], [ 3,4], X)
append(1 | [], [3,4], 1 | X)
append([], [3,4], [ 3,4])

这就是它。我无法理解它如何将元素组合在一起，这就是我可以使用的帮助 - 关于此方法如何工作的清晰解释。我只是不明白 [2,1] 数组如何添加到最终结果中。

原文

append([],Xs,Xs).
append([Head|Tail],List2,[Head|Tail2]):-
    append(Tail,List2,Tail2).

The upper append method adds elements from first two parameter slots to the third param variable.

?-append([2,1], [3,4], X).
?-X=[2,1,3,4]

The way I see it in steps is (which is propably wrong):

append(2 | [1], [3,4], 2 | X)
append([1], [3,4], X)
append(1 | [], [3,4], 1 | X)
append([], [3,4], [3,4])

And that's it. I can't wrap my head around how it adds together the elements and that's what i could use help with - a clear explanation on how this method works. I just don't understand how the [2,1] array gets added to the final result.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

淡莣 2024-12-13 05:03:04

递归中的 X 与原始调用中的 X 不同，如果您在跟踪中重命名它，您会看到

append(2 | [1], [3,4], 2 | X1) -- X = [2|X1]

append([1], [3,4], X1)

append(1 | [], [3,4], 1 | X2) -- X1 = [1|X2]
append ([], [3,4], [3,4])  -- X2 = [3,4]

X1 = [1,3 ,4] 和 X = [2,1,3,4]

the X in the recursion is not the same X as in the original call if you rename it in the trace you'll see

append(2 | [1], [3,4], 2 | X1) -- X = [2|X1]

append([1], [3,4], X1)

append(1 | [], [3,4], 1 | X2) -- X1 = [1|X2]
append ([], [3,4], [3,4])  -- X2 = [3,4]

so X1 = [1,3,4] and X = [2,1,3,4]

回复收藏 0 原文

三岁铭 2024-12-13 05:03:04

首先，您必须了解 Prolog 中如何实现列表。它本质上是一种递归数据结构。

空列表是零项的列表，由原子 [] 表示。
非空列表由结构./2表示，由列表的头（序言术语）和尾< /strong> 列表（另一个列表，包含所有项目，保存第一个）。所以...
[] — 零个项目的列表，表示为
[]
[a] — 包含 1 项的列表，表示为
.(a,[])
[a,b] — 包含 2 个项目的列表，表示为
.(a,.(b,[]))
[a,b,c] — 3 个项目的列表，表示为
.(a,.(b,.(c,[])))

使用方括号的标准列表表示法只是此表示形式之上的语法糖。说 [Head|Tail] 是说 .(Head,Tail) 和 [X,Y,Z|More] 的礼貌方式是 .(X,.(Y,.(Z,More))) 的礼貌说法。（您可能会注意到这里的内部列表符号有某种......Lisp-ishness。）

了解列表的表示方式，将一个列表附加（连接）到的简单算法另一个是这样的：

首先，需要考虑两种特殊情况：

将非空列表 X 附加到空列表 Y 的结果是 X。
Append [ 1,2,3] 至[] 并获取 [1,2,3]。注意。 这种情况可以（通常）由不过，下面是普通情况。这是一个优化的机会，因为没有必要递归整个列表，只需在末尾用 [] 替换 [] ，对吧？。< /p>
< p>将空列表 X 附加到非空列表 Y 的结果是 Y。
将 [] 附加到 [1,2,3] 并得到 [1, 2,3]。

否则，我们有普通情况：

将非空列表 Y 附加到非空列表 X 以生成列表 Z。 这样做很简单：
我们只需在列表 X 上递归，边走边弹出它的头，然后将其添加到列表 Z 中，即结果。您会注意到，发生这种情况时，列表 Z 是一个损坏的列表结构，因为它的最后一个节点始终未绑定，而不是 []。当源列表列表 X 耗尽并退化为空列表的特殊情况时，这个问题在最后得到修复。此时，未绑定的最后一个节点在与列表 Y（零个或多个节点的列表）统一时被绑定，从而为我们留下了正确的列表结构。

append/3 的 Prolog 代码直接表达了该算法。如前所述，第一个子句是可选优化，因为它可以由第三个子句（普通情况）处理。不过，它希望削减，否则的话，回溯会产生两个解决方案。

append( X      , [] , X      ) :- !. ; concatenate empty list X to list Y producing Y
append( []     , Y  , Y      ).      ; concatenate list X to empty list Y producing X
append( [X|Xs] , Y  , [X|Zs] ) :-    ; anything else
  append( Xs , Y , Zs )
  .

First, you have to understand how a list is implemented in Prolog. It is an essentially recursive data structure.

The empty list is a list of zero items, represented by the atom [].
Non-empty lists are represented by the structure ./2, consisting of the head of the list (a prolog term), and the tail of the list (another list, consisting of all items save the first). So...
- [] — a list of zero items, is represented as
  []
- [a] — a list of 1 item, is represented as
  .(a,[])
- [a,b] — a list of 2 items, is represented as
  .(a,.(b,[]))
- [a,b,c] — a list of 3 items, is represented as
  .(a,.(b,.(c,[])))

The standard list notation using square brackets is just syntactic sugar on top of this representation. Saying [Head|Tail] is a polite way of saying .(Head,Tail) and saying [X,Y,Z|More] is the polite way of saying .(X,.(Y,.(Z,More))). (You might be noticing a certain....Lisp-ishness...to the internal list notation here.)

Understanding how a list is represented, the naive algorithm for appending (concatenating) one list to another is this:

First, there are two special cases to consider:

The result of appending a non-empty list X to an empty list Y is X.
Append [1,2,3] to [] and get [1,2,3].Note. This case is can be (is normally) handled by the ordinary case below, though. It's an opportunity for optimization as there's no point in recursing down the entire list, just to replace [] with [] at the end, right?.
The result of appending an empty list X to a non-empty list Y is Y.
Append [] to [1,2,3] and you get [1,2,3].

Otherwise, we have the ordinary case:

Append non-empty list Y to non-empty list X to produce list Z. To do this is trivial:
We simply recurse down on list X, popping its head as we go and and prepending that to list Z, the result. You'll notice that as this happens, list Z is a broken list structure, since its last node is always unbound rather than being []. This gets fixed at the very end when the source list, list X, is exhausted and degenerates into the special case of being an empty list. At that point, the unbound last node gets bound as it unifies with list Y (a list of zero or more nodes), leaving us with a correct list structure.

The Prolog code for append/3 expresses this algorithm directly. As noted earlier, the first clause is an optional optimization, as that can be handled by the 3rd clause (the ordinary case). It wants a cut, though, as without, backtracking would produce two solutions.

append( X      , [] , X      ) :- !. ; concatenate empty list X to list Y producing Y
append( []     , Y  , Y      ).      ; concatenate list X to empty list Y producing X
append( [X|Xs] , Y  , [X|Zs] ) :-    ; anything else
  append( Xs , Y , Zs )
  .

回复收藏 0 原文

~没有更多了~