非递归遍历嵌套列表 - 在 Python 中构建类似的嵌套列表

Question

我需要遍历一个嵌套列表，对每个非列表项进行处理并使用str()返回相似的列表保留其结构。使用递归会比较容易，但是我需要以迭代的方式完成。下面是我的一次尝试，使用了while循环：

def myiter(e):
    a = [e] # initial list
    c = [[]] # final result
    get_last = lambda x: x[len(x)-1] # get ref to the final sublist
    l = get_last(c)
    while a:
        b = a.pop(0)
        if isinstance(b, list):
            # if there are more items to process in the original list
            if a:
                a = b + a
            # else extend original list to process sublists
            else:
                a.extend(b)
            # make a new sublist ref
            l = get_last(c)
            c.append([])
        else:
             # walk and process every item in the nested list
             l.append(str(b))
    return c

这种方法存在几个问题，输出结果如下所示：

myiter([1, [2, [3, 4], 5]]) # [['1'], ['2'], ['3', '4', '5'], []]

期望的结果是：

['1', ['2', ['3', '4'], '5']]

有没有一种简单的迭代方法可以在Python中完成这个任务？

- MarkokraM

---

期望的结果是什么？ - Jab

另外，a = [e] 看起来好像被误用了。你正在创建一个只包含 e 元素的列表。而 get_last 最好这样写：lambda x: x[-1]。 - Jab

我可以问一下为什么您不能使用递归吗？ - Jab

@Jab 三个原因：首先，我的一个应用程序经常达到最大递归限制；其次，出于性能方面的考虑，尽管 map 函数可能与迭代方法不相上下；第三，仅仅是为了训练和学习这两种不同的编码风格。 - MarkokraM

经过几次尝试，我转而同意@MoreFreeze的观点，我们可能需要使用自己的LIFO堆栈，否则递归会隐式地为我们提供。请使用LIFO堆栈检查我的答案。 - fountainhead

Answer 1

这似乎有效：

def stringify(a):
    a = a[:]                           # Make copy of what was passed in.
    res = []                           # Initialize result list.
    my_stack = []                      # Initialize our own LIFO stack.
    while (a or my_stack):                            # While a or my_stack is non-empty
        if (a):
            elem = a.pop(0)
            if (not isinstance(elem, list)):          # If popped elem is not a list
                res.append(str(elem))                 # Append stringified elem to res
            else:
                my_stack.append((a, res))           # Push some stuff, to resume working upon later.
                a = elem                            # Let's start iterating on this inner list
                res = []                            # This inner list needs a clean res, to start with.
        else:                                       # my_stack is non-empty
            a, res_prev = my_stack.pop()   # Pop some stuff, to resume, work on outer list
            res_prev.append(res)           # First, append our just-completed inner list.
            res = res_prev
    return res

输出：

a = [1, [2, [3, 4], 5]]
stringify(a)
['1', ['2', ['3', '4'], '5']]

通过了以下测试用例：

a = [1, [[[2]]]]
a = [[[1]], 2]
a = [1, [[2]]]
a = [1, [2, [3, 4], 5], [6, [7, [8]]], 9]
a = [1, [2, [3, 4], 5]]
a = [1, 2, 3, 4, 5]

关于这个的一些说明：

1. 如果我们列表 a 上的 pop 产生一个整数，我们只需将字符串化的整数附加到 res
2. 如果我们列表 a 上的 pop 产生一个内部列表，我们需要在处理该内部列表之前，先开始处理该内部列表，再处理出现在该内部列表之后的元素。处理完内部列表后，我们必须返回到剩余未弹出的 a 元素。
3. 每当我们检测到当前列表 a 变为空时，我们的 res 将指向等效的字符串化列表，此时我们就可以将我们的 res 添加到任何可能的（字符串化）外部列表中了。
4. 为了处理每个遇到的内部列表，我们采用该内部列表作为新的 a（分配 a = elem），并采用一个空列表作为新的 res（res = []）。在那之前，我们需要把我们当前的 a 和当前的 res 推入堆栈。
5. 为什么是 LIFO？嗯，这样看：无论我们当前正在处理哪个列表 (a)，无论是什么样的列表，被推入 my_stack 的任何最后一个都代表着该列表的立即外部列表。

- fountainhead

---

值得进一步调整。我没有像你那样广泛地修改“非列表情况”下的列表。为了进一步改进，目前这个测试用例失败了：[1，[2，[3，4]，5]，[6，[7，[8]]]，9]。 - MarkokraM

已修复并进一步测试了其他测试用例。请检查。 - fountainhead

现在很酷！我甚至有一个相同的部分，用于检查两个列表。你能解释一下LIFO栈的目的吗？如果你的回答对我的目的有足够的帮助，我会接受它。 - MarkokraM

@MarkokraM：请查看已添加到答案中的注释。 - fountainhead

Answer 2

为什么不使用递归？使用递归程序处理递归数据结构是自然而直接的。将递归进程转换为迭代进程不需要克隆输入，创建堆栈或其他中间值。你的大脑可以摆脱这种繁琐复杂性 -

def first (a = []):
  return a[0]

def rest (a = []):
  return a[1:]

def myiter (a = []):
  # base: empty a
  if not a:
    return []
  # inductive: non-empty a, first elem is list
  elif isinstance(first(a), list):
    return [ myiter(first(a)) ] + myiter(rest(a))
  # inductive: non-empty a, first elem is non-list
  else:
    return [ str(first(a)) ] + myiter(rest(a))     

print(myiter([1, [2, [3, 4], 5]]))

当然，在函数f中将str作为参数是有意义的。

def myiter (f, a = []):
  # base: empty a
  if not a:
    return []
  # inductive: non-empty a, first elem is list
  elif isinstance(first(a), list):
    return [ myiter(f, first(a)) ] + myiter(f, rest(a))
  # inductive: non-empty a, first elem is non-list
  else:
  return [ f(first(a)) ] + myiter(f, rest(a))

现在您可以按照自己的意愿深度映射字符串，就像这样 -

print(myiter(str, [1, [2, [3, 4], 5]]))
# ['1', ['2', ['3', '4'], '5']]

或者使用您选择的任何功能 -

def square (x):
  return x * x

print(myiter(square, [1, [2, [3, 4], 5]]))
# [1, [4, [9, 16], 25]]

您是因为栈限制而试图避免递归吗？ 如果使其成为尾递归 -

def identity (x):
  return x

def myiter (f, init = []):
  def run (a = init, then = identity):
    if not a:
      return \
        then([])
    # inductive: non-empty a, first elem is list
    elif isinstance(first(a), list):
      return \
        recur(first(a), lambda l: \
          recur(rest(a), lambda r: \
            then([ l ] + r)))
    # inductive: non-empty a, first elem is non-list
    else:
      return \
        recur(rest(a), lambda r: \
          then([ f(first(a)) ] + r))
  # loop inner function
  return loop (run)

然后实现一个通用的loop，将递归调用栈转换为迭代序列 -

def recur (*values):
  return (recur, values)

def loop (f):
  acc = f ()
  while type(acc) is tuple and acc[0] is recur:
    acc = f(*acc[1])
  return acc

输出结果相同，但现在myiter可以接受任意嵌套限制的数组。不受限制地进行递归，多美妙的事情啊！

print(myiter(str, [1, [2, [3, 4], 5]]))
# ['1', ['2', ['3', '4'], '5']]

print(myiter(square, [1, [2, [3, 4], 5]]))
# [1, [4, [9, 16], 25]]

使用repl.it在您自己的浏览器中查看此程序并验证结果。

---

为什么不能使用递归？- Jab

@Jab，有三个原因：首先，在我的某个应用程序上经常达到最大递归限制，其次是性能问题，虽然map方法可能与迭代方式相媲美，但第三种是为了训练和学习这两种不同的编码风格。 – MarkokraM

所以你还没有达到递归限制，但你担心你的程序会吗？最好了解实际的限制而不是围绕幽灵编写程序。在使用生成器的简化实现中，请注意只有在遇到嵌套级别时才会发生递归。即使将此实现保留为原样，它也可以支持任何长度的列表以及嵌套级别高达堆栈限制，其中默认值可能约为1,000。这意味着唯一会使您的堆栈崩溃的数据输入是嵌套1000次或更多次的数据输入。直到达到实际限制之前，保留此程序可能是安全的。

def square (x):
  return x * x

def myiter (f, init = []):
  def gen (a):
    for x in a:
      if isinstance(x, list):
        yield list(gen(x)) # recursion
      else:
        yield f(x)
  return list(gen(init))

print(myiter(str, [1, [2, [3, 4], 5]]))
# ['1', ['2', ['3', '4'], '5']]

print(myiter(square, [1, [2, [3, 4], 5]]))
# [1, [4, [9, 16], 25]]

- Mulan

---

我经常因为特定于领域的问题遇到了最大递归限制，这里太复杂了，无法解释。一个简化版本的通过映射递归遍历所有列表项并保持列表结构的方法是：def recmap(a): return list(map(recmap, a)) if isinstance(a, list) else str(a)。与迭代方法相比，它非常简短和优雅。纯匿名函数版本也可以工作：print((lambda f, a: f(f, a)) ((lambda f, a: list(map(lambda b: f(f, b), a)) if isinstance(a, list) else str(a)), [1, [2, [3, 4]], 5]))。 - MarkokraM

真的更好的答案； 考虑递归但解决迭代。 像scheme这样的函数式语言就是这样行为的，对吧？ - Nishant

@Nishant，你懂的。Scheme才是王道 ^_^ - Mulan

@user633183，但是这种方法在Python中是否可行呢？因为Python不支持尾递归。例如，请看这段代码 - myiter(str, range(0, 957))。你能分享一下你的想法吗？ - Nishant

@Nishant 当然。你试过运行它吗？它会返回 [ '0', '1', '2', ..., '954', '955', '956' ]。这个例子甚至可以在最后一个使用生成器实现的程序上工作（而不是 loop）。 - Mulan

@user633183，是的，我尝试过了，但对我没有用。你能否检查一下 https://repl.it/repls/BrightFortunateWorker？当我使用1000时，我得到了一个“RecursionError”。不确定我是否遗漏了什么？请给予建议。我嵌套到了类似的深度，但那个可以正常工作！如果值得的话，我甚至可以将此作为另一个问题提出。 - Nishant