flatten() に再帰は必要ない（Python版） #Python

スクリプト言語には flatten([[1, 2, [3]], 4]) -> [1, 2, 3, 4] みたいな、ネストしたリストを平坦化する関数が用意されています。

flatten は動作がわかりやすいので、再帰呼び出しのサンプルにもってこいです。

でも・・・

でも良く考えると flatten() は、現在いる要素の子要素がリストの場合、そのリストの中身をすべて現在いる場所に移動し、自身を削除し、そして今と同じ箇所で再検査すればいいだけなのだ。スタックとして覚えておく必要もない。なので実装は以下の様になる。

Big Sky :: flatten() に再帰は必要ない

という事なので、Pythonでも実装してみましょう。

はじめの「再帰を使った flatten()」を私たちに馴染み深い Python で書くとこんな感じ：

def rec_flatten(src_list):
    """再帰を使ったflatten()"""
    flat_list = []
    for x in src_list:
        if isinstance(x, list):
            flat_list.extend(rec_flatten(x))
        else:
            flat_list.append(x)
    return flat_list

これだとリストがネストした分だけ、関数の再帰呼び出しもネストすることになり、[[[[[[[[[[...[[[1]]]...]]]]]]]]]] みたいな深くネストしたリストではスタックが足りなくなることがある。

ちなみに再帰呼び出しの最大回数は sys.getrecursionlimit で調べられます。

$ python -c 'import sys; print(sys.getrecursionlimit())'
1000

さて、Pythonのリストは変更可能なので、元記事と同じように「子要素のリストの中身を現在いる場所に移動」する事で、再帰無しで flatten を実装できます！

具体的には「スライスへの代入」を使います。

def flatten(alist):
    alist = list(alist)
    i = 0
    while i < len(alist):
        if isinstance(alist[i], list):
            alist[i:i+1] = alist[i]
        else:
            i += 1
    return alist

※コメントでも指摘されていますが、Pythonのリストはリンクリストではないので、この実装だと非効率かもしれません。

ちなみに、Pythonの標準ライブラリには flatten はありませんでした¹。ざんねん。

itertools.chain.from_iterable で１レベルの展開はできる。 ↩