递归横向(Python)

Question

对于我正在做的编程挑战，我需要遍历一个列表列表，在编写标准的2D遍历函数时，我想为什么不泛化它，所以我做到了。这是我最大的努力：

我的代码

def rTraverse(lst, f = lambda x: x):        #Traverse a list and any of its (non self referential) sublists recursively.
    for item in lst:
        if isinstance(item, list):
            if "..." in str(item):  #Skip self-referential lists.
                continue
            traverse(item, f)   #Traverse the sublist.
        else:
            f(item)

Answer 1

嗯，我没有考虑的一个失败案例是包含带有“.”字符串的子列表。在它们内部破坏了功能。此外，将列表转换为字符串是一项昂贵的操作。在咨询了SE以外的人之后，我进一步完善了算法：

重构版

"""
*   A faster version of `rTraverse()` that uses a set instead of a stack to store a list's ancestry. 

*   Searching a set is O(1) in the average case, while searching a list is O(n) in the average case, so `rTraverse2()` would run faster.
*   Params:
    *   `lst`: the list to be traversed.
    *   `f`: the function to be applied to the list items.
    *   `seen`: a set that stores the ancestry of the current sublist. (would be used for checking if a sublist is self referential).
*   Return:
    * None: The list is modified in place.
*   Caveats:
    *   The function no longer traverses in order.
*   Credits:
    *   The main insight(s) for the algorithm comes from "raylu" on the [programming discord](https://discord.gg/010z0Kw1A9ql5c1Qe)
"""
def rTraverse2(lst, f, seen=None):
    seen = set() if seen is None else seen      #Initialise the set.
    toRecurse = []      #The list of sublists to be recursed on.
    for idx in range(len(lst)):
        if isinstance(lst[idx], list):
            if id(lst[idx]) not in seen:    #Traverse only non self referential sublists.
                toRecurse.append(lst[idx])  #Add the sublist to the list of sublists to be recursed upon.
        else:
            lst[idx] = f(lst[idx])
    seen.update(id(x) for x in toRecurse)
    for item in toRecurse:  #Traverse all sublists in `toRecurse`.
        rTraverse2(item, f, seen)
```