如何以更简单的方式合并列表中的元素？Prolog

Question

我正在尝试合并列表中的元素，规则如下：

1. 合并一个列表，如果列表中有2个连续的数字是相同的，则通过将它们相加来将它们合并为一个数字（例如：[4,4,0,0] -> [8,0,0,0]）。

2. 新合并的数块不能在同一回合中与另一个数块结合（例如：[4,4,8,0] -> [8,8,0,0] True，但 [16,0,0,0] False）。

3. 列表长度应为4。如果在合并后列表缩短，则在尾部添加一个零（例如：[4,4,0,2] -> [8,0,2,0]）。

4. 注意零的情况：[0,0,2,2] -> [0,4,0,0]。

我已经能够创建代码，但我想找到详细解释的更简单的方法。

我的方法：

merge([H|T],L):-
   merge2([H|T],J),
    (
    length(J,2)->  
    append(J,[0,0],L);
    length(J,3)->  
    append(J,[0],L);length(J,4)-> J=L).

merge2(_,[]).
merge2([X],[X|_]).
merge2([H1,H2|T],[W|L]):-
    H1=H2,
    W is H1+H2,
    merge2(T,L).
merge2([H1,H2|T],[H1|L]):-
    H1\=H2,
    merge2([H2|T],L).

- Reema Q Khan

---

新的零在尾部是从哪里来的？为什么不是 [4,4,0,0] --> [8,0] 和 [4,4,8,0] ->[8,8,0]？ - Will Ness

只是为了明确：[4,4,0,2] -> [8,0,2,0]，而不是[8,2,0,0]，[0,0,2,2] -> [0,4,0,0]，而不是[4,0,0,0]？ - DuDa

不，0等于0，所以根据你的定义应该是[0,4,0,0]。你没有说应该跳过0。 - Will Ness

是的， {[0,0,2,2]} -> [0+0, ...{[2,2]} ...[0]] -> [0+0, ...[2+2,0], ...[0]] -> [0,4,0,0]，其中 {....} 表示“执行转换”，而 [ A, ...[B] ] 是列表拼接伪代码，代表此处的 [A|B]。 - Will Ness

@Raubsauger 抱歉，应该是 [0,4,0,0]，我改正了。 - Reema Q Khan

Answer 1

长度为4不足以仅靠写出每种情况来解决问题：

merge( [A,B,C,D], Y) :-
  ( A=B -> ( C=D -> X=[A+B,C+D,0,0] 
                 ;  X=[A+B,C,D,0] )
        ;  ( B=C -> X=[A,B+C,D,0]
                 ;  ( C=D -> X=[A,B,C+D,0]
                          ;  X=[A,B,C,D] ))),
  maplist(is,Y,X).

这只是根据您的规定编写案例。我们可以通过符号 + 将和写成符号形式，而不必每次添加两个变量时手动调用 is，最后通过 maplist 一次性调用结果中的所有元素。

- Will Ness

---

你能否解释一下你的代码，特别是maplist部分。 - Reema Q Khan

不客气。 :) 如果长度未知，可能会更难一些。 - Will Ness

Answer 2

这是一个在单次遍历中解决任意长度列表问题的解决方案，而且不需要使用append。（但这对我来说是个罕见的情况，需要“切”操作！）

主谓语调用一个帮助器来计算要添加到末尾的零的数量：

merge(List, Merged) :-
    merge(List, 0, Merged).

这个帮助程序的重要条款是合并相邻的相等值。它还会增加零计数器，以便在结尾处添加零:

merge([X, X | Xs], ExtraZeros, [Sum | MergedRest]) :-
    !,
    Sum is X + X,
    merge(Xs, s(ExtraZeros), MergedRest).

否则，复制元素直到我们到达列表的末尾：

merge([X | Xs], ExtraZeros, [X | Ys]) :-
    merge(Xs, ExtraZeros, Ys).

在列表末尾，根据需要生成零：

merge([], ExtraZeros, ZeroList) :-
    length_zerolist(ExtraZeros, ZeroList).

length_zerolist(0, []).
length_zerolist(s(N), [0 | Zeros]) :-
    length_zerolist(N, Zeros).

问题中的测试：

?- merge([4, 4, 0, 0], Merged).
Merged = [8, 0, 0, 0].

?- merge([4, 4, 8, 0], Merged).
Merged = [8, 8, 0, 0].

?- merge([4, 4, 0, 2], Merged).
Merged = [8, 0, 2, 0].

?- merge([0, 0, 2, 2], Merged).
Merged = [0, 4, 0, 0].

更长的列表：

?- merge([0, 1, 1, 2, 3, 3, 4, 4, 5], Merged).
Merged = [0, 2, 2, 6, 8, 5, 0, 0, 0].

- Isabelle Newbie

---

谢谢您的回答。您能解释一下 s(N) 和 s(ExtraZeros) 是什么吗？我在Prolog中从未见过这个。 :) - Reema Q Khan

@ReemaQKhan 当 merge/3 开始工作时，它的第二个参数是 0。然后在求和的情况下，0 被转换为 s(0)，如果没有求和，则保持为 0。然后 s(0) 被转换为 s(s(0)) 等等，通常情况下，如果进行了求和，则将 ExtraZeros 转换为 s(ExtraZeros)，否则保持不变。如果我们计算该复合术语中嵌套的 s 的数量，我们会发现它的深度与我们所做的求和数量相同。这被称为 Peano 算术，或者说是一元计数（与二进制或十进制相对）。 - Will Ness

这比我的临时答案好多了。:) 简单明了。 - Will Ness