Python实现可变参数连接运算符

Question

澄清：

我刚刚意识到我的定义和下面的代码可能是错误的，因为它们没有考虑嵌套列表。我真的希望concatenate的最终结果是一个不是列表的对象，或者一个不是列表的多个对象的列表（所以没有嵌套列表）。并且空列表应该成为对象Empty。

---

但是用户可以提供由嵌套列表组成的输入，在这种情况下我需要它们被去除。抱歉不清楚这一点。

我有某种类型的对象（也可以将Empty作为值），并且我在这些对象上有一个满足以下公理的二元连接运算符（这里[A，B]表示包含A和B的列表）：

concatenate2(Empty, A) = concatenate2(A, Empty) = A  
concatenate2(A, [B, C]) = concatenate2([A, B], C) = [A, B, C]  
concatenate2(A, B) = [A, B] (if A, B do not match any of the previous cases).

现在我想要一个任意多个术语的连接：

concatenate([]) = Empty  
concatenate([A]) = A  
concatenate([A, B]) = concatenate2(A, B)  
concatenate([A, B, ...]) = concatenate([concatenate2(A, B), ...])

我想以最小化列表复制操作数量的方式实现这些运算符，但我不确定如何在Python中做到这一点。

我目前的想法是做这样的事情：

def concatenate2(A, B):
    if A == Empty:
        return B

    if B == Empty:
        return A

    if type(A) == list:
        return concatenate(A + [B])

    if type(B) == list:
        return concatenate([A] + B)

    return [A, B]

def concatenate(terms):
    if terms == []:
        return Empty

    if len(terms) == 1:
        return terms[0]

    if len(terms) == 2:
        return concatenate2(terms[0], terms[1])

    return concatenate(concatenate2(terms[0], terms[1]) + terms[2:])

这看起来非常漂亮和清晰，但我不知道它在性能和内存使用方面的表现如何。我担心在每个[...] + [...]操作期间可能会导致列表副本太多。

有没有更好的方法来实施这些操作？

请注意，最终只需要concatenate操作。 concatenate2运算符用于给出一个很好的递归定义，但如果有人可以提出一个不使用它的更有效的解决方案，我也会接受它。

Answer 1

你似乎想要的不仅仅是变量，而且还有混合型签名。

假设我们想要定义一些concatenate_all(*args)函数来连接抛出它的所有参数。

如果你同意concatenate_all的所有参数都是序列，我们可以用它们形成一个单独的序列，然后用concatenate折叠它：

import itertools

# Pretend that concatenate_all is [[A]] -> [A]
def concatenate_all(*seqs):
  all_seqs = itertools.chain(*seqs)
  return reduce(lambda acc, x: concatenate(acc, x), all_seqs, EMPTY)

如果我们假设某些args是标量，有些是列表，我们可以将标量包装到列表中并使用相同的技巧。

def concatenate_all(*scalars_or_seqs):
  def to_list(x):
      # TODO: should make it work with generators, too.
      return x if isinstance(x, list) else [x]

  # We use itertools to avoid creating intermediate lists.
  all_items = itertools.chain(*scalars_or_seqs)
  all_lists = itertools.imap(to_list, all_items)
  return reduce(lambda acc, x: concatenate(acc, x), all_lists, EMPTY)

如果我们假设某些args也是我们需要展平的嵌套列表，您可以更新上面的代码来处理它。

我想警告你不要让一个对它的论点过于聪明的函数。过多的魔法可能最初是look neat，但在实践中变得太难以推理，特别是当使用像Python这样的高度动态语言时，静态检查几乎为零。最好将包装和展平推送到调用方并使其明确。

Answer 2

使用+进行重复连接并不理想，因为它不断为每个二进制级联创建中间list对象，这导致关于组合长度的二次最坏情况时间复杂度。一种更简单和更好的方法是具有线性复杂性的嵌套理解。这也使用*运算符解包任意数量的参数：

def concatenate(*terms):
    return [x for t in terms for x in (t if isinstance(t, list) else [t])]

>>> concatenate([3, 4], 5, [], 7, [1])
[3, 4, 5, 7, 1]

>>> concatenate()
[]