P107: Flatten a nested list structure
摊平嵌套的列表。 先写出验证实现的单元测试：
from python99.lists.p107 import flatten
def test_flatten():
assert flatten([1, [2, 3], 4]) == [1, 2, 3, 4]
assert flatten([1, 2, 3, 4]) == [1, 2, 3, 4]
assert flatten([1, [2, [3, 4]]]) == [1, 2, 3, 4]
assert flatten([]) == []
assert flatten([[1, 2, 3, 4], 5, 6, [[7, 8], [9, 10]]]) == [
1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
一层嵌套的列表简单，遍历列表，遇到列表类型元素就拼接到结果列表中。可多层嵌套可怎么办呢？
没有什么问题是递归解决不了的！
首先，假定已经拥有一个方法可以摊平任意层级嵌套列表。 然后，将列表拆分为第一个元素和其余列表。若第一个元素是列表，则先摊平第一个元素再摊平其余列表，最后合併之。若第一个不是列表，则先摊平其余列表，再併第一个元素和摊平后的其余列表。 摊平方法不断地拆分列表，直至列表为空。
举个例子，给定嵌套列表[1, [2, 3], [4, [5, 6]]]：
- 将列表
[1, [2, 3], [4, [5, 6]]拆分为第一个元素1和剩余列表[[2, 3], [4, [5, 6]]。第一个元素1不是列表，所以无需摊平第一个元素。 - 将剩余列表
[[2, 3], [4, [5, 6]]继续拆分为第一个元素[2, 3]和剩余列表[[4, [5, 6]]。第一个元素[2, 3]是列表，所以需要先摊平第一个元素再摊平剩余列表。 - 将上步中的第一个元素
[2, 3]拆分为第一个元素2和剩余列表[3]。拆分出来的第一个元素2不是列表且剩余列表[3]中仅含有一个非列表的元素。至此，上一步中的第一个元素已被摊平。接下去，摊平上一步中的剩余列表。 - 将剩余列表
[[4, [5, 6]]]拆分为第一个元素[4, [5, 6]]和剩余列表[]。第一个元素是列表，需要摊平之。将第一个元素拆分为4和[5, 6]。剩余列表[]是空，无需摊已平。 - 继续摊平上一步剩余的
[5, 6]。将列表[5, 6]拆分为5和[6]，5不是列表，已平，[6]可被拆分为6和[]。 - 最后，将所有摊平的「第一个元素」按序拼接起来。
代码实现：
## Flatten a nested list structure
def flatten(l):
if l is None:
return []
if len(l) == 0:
return []
element = l[0]
remain = l[1:len(l)]
if isinstance(element, list):
return flatten(element)+flatten(remain)
else:
return [element]+flatten(remain)