拒绝懒惰的家

需求:

有些列表的元素可能还是一个列表,而这样的嵌套可能持续下去.你需要遍历列表的每一个元素,并将嵌套的列表元素转换为单列表(及列表中不存在列表).

讨论:

我们需要首先讨论一下什么元素是"子列表",并要将它扩展到什么标准.简单来说 ,我们需要提供一个断言来说明什么样的元素是需要我们扩展的.(断言是一个函数,可以对于任何对象调用,它返回它的真实性,在这里,true表示可以扩展,false表示不能).默认的情况,我们可以说列表(list)和元素是可以扩展(tuple)的,而其它的类型不可以.然后写下下面的代码:

def list_or_tuple(x):
    return isinstance(x, (list, tuple)) 
def flatten(sequence, to_expand=list_or_tuple):
    for item in sequence:
        if to_expand(item):
            for subitem in flatten(item, to_expand):
                yield subitem
        else:
             yield item

在嵌套列表中处理,或者说,在一个树中遍历叶子节点,是很多应用程序都会遇到的问题.你从一个嵌套结构开始,而只关心里面的元素,并不关心它的结构,比如:

for x in flatten([1, 2, [3, [  ], 4, [5, 6], 7, [8,], ], 9]):
    print x,

输出1 2 3 4 5 6 7 8 9.

在这类问题中,核心问题是需要知道什么元素是需要扩展的,或者对什么元素使用yield,并不是想像中的那么明显.所以我避开了这个问题,将它交给一个代理函数,有用户决定什么类型是需要扩展的,默认只处理列表类型和元组类型.
在flatten模块中,我们需要再写一个断言函数,因为用户可能希望扩展一切具有迭代特性的对象,当然除了字符串,因为它是不可修改的,而且本身就是常量,而不是子列表.
为了判断一个对象是否具有可迭代属性,调用它的iter方法就可以了,如果返回TypeError异常,就说明它是不可迭代的.判读一个对象是不是字符串类型,看看它是不是basestring的子类就可以了.所以,这个断言并不难写:

def nonstring_iterable(obj):
    try: iter(obj)
    except TypeError: return False 
    else: return not isinstance(obj, basestring)

现在调用者可以使用nonstring_iterable,如果它希望将任何可迭代对象扩展的话.不过,最好不要把nonstring_iterable做为断言的默认值,因为它会比list_or_tuple慢3倍.
我们也可以写一个非递归的版本.这样可以使你避免达到Python递归的深度上限.这个上限一般是几千层.替代递归的方法就是建立一个后入先出的堆栈 (LIFO).在这里,我们可以使用iterator的列表来实现:

def flatten(sequence, to_expand=list_or_tuple):
    iterators = [ iter(sequence) ]
    while iterators:
        # loop on the currently most-nested (last) iterator 
        for item in iterators[-1]:
            if to_expand(item):
                # subsequence found, go loop on iterator on subsequence
                iterators.append(iter(item))
                break 
            else:
                yield item
        else:
            # most-nested iterator exhausted, go back, loop on its parent
            iterators.pop( )

if语句的子句对每一个传递进的item进行操作,在那个子句中我们将item的迭代器放入iterators中,然后跳出for循环,回到外层的while循环, 它会对我们添加进的迭代器进行新的for循环.if语句的else语句是将任何不需要扩展的元素进行yield操作.
for语句的else语句在没有调用break且for执行完毕后运行,也就是说,当前列表已经遍历完毕.所以我们删除它的迭代器,回到while循环.while循环会开始新的循环,或者中止.实际上,我们记录了迭代的状态.
上面的非递归代码也适用于一般的简单递归问题.如果你认为递归比非递归要快,那么你要失望了,根据我自己的经验,非递归解法要比递归解法慢10%,这是在一系列例子运行后总结的结果.

相关说明:

iter(...)
    iter(collection) -> iterator
    iter(callable, sentinel) -> iterator

    Get an iterator from an object.  In the first form, the argument must
    supply its own iterator, or be a sequence.
    In the second form, the callable is called until it returns the sentinel.