Python でリストに対する再帰的な関数の適用

2008年10月1日水曜日

Python でリストに対する再帰的な関数の適用

1. リストに対する再帰的な考え方のポイント

リストに対して、再帰的な関数を適用する場合、次の二つの視点を頭に入れておく。

先頭要素と、それ以外の残りのリスト。
リストは要素として、リスト、または、値を持つ。

2. フラットなリストに対する再帰的な処理

ネストのないフラットなリストに対して適用する関数を考える場合、

先頭要素
先頭要素以外の残りの要素

に分けて考える。先頭要素に適用した場合の処理と、それ以外の要素を含むリストに対して、再帰的に関数を適用するように記述する。

何もしない関数

一気に考えると脳みその容量をオーバーするので段階的に考える。 (+_+)

まず、フラットなリスト L を受けとったら、そのまま返す関数 map1 を考える。

L = [1,2,3,4,5]

ただし、そのまま返すと言っても、関数を再帰的に適用する。

実装を考えるとき、

空のリストが渡されたら、空のリストを返す。
リストの先頭要素と、それ以外の残りの要素に再帰的に関数を適用したものを結合する。

def map1(L):
    if L == []:
        return []
    else:
        return [L[0]] + map1(L[1:])

print map1(L)

先頭の要素を取り出した後、後続のリストと結合するため、要素を「要素一つのリスト」にする。

関数を適用する関数

次に、リストの各要素に関数を適用する関数に変更する。

引数として要素に適用する関数 f を追加する。

def map1(f,L):
    if L == []:
        return []
    else:
        return [f(L[0])] + map1(f,L[1:])
    
print map1(lambda x: x*2, L)

これで組込みの map 関数のような動作の関数ができた。

3. ネストのあるリスト

ネストのあるリスト L の場合を考える。

このとき、リストは Compositeパターンになっていると見なせる。このようなリストに対する関数は、リストと値の場合に分けて考える。リストのときは、その要素に再帰的に関数を適用する。

L = [1,[21,22],3,[41,[421,422],43,44],5]

何もしない関数

リストを受けとったら、何もしないで返す関数 map2 を定義する。

def map2(L):
    if isinstance(L, list):
        if L == []:
            return []
        else:
            return [map2(L[0])] + map2(L[1:])
    else:
        return L

print map2(L)

最初に、対象がリストであるか、値であるか判定をしてから処理を進める。

値であれば、それをそのまま返す。
リストの場合は、先ほどのフラットなリストと同じ処理を行う。ただし、今回は、取り出した先頭の要素が値ではなく、リストである可能性もあるので、それに対して再帰的に関数を適用する。

関数を適用する関数

上記の関数を、リストの各要素に適用する関数を引数として受けとるように変更する。

def map2(f,L):
    if isinstance(L, list):
        if L == []:
            return []
        else:
            return [map2(f,L[0])] + map2(f,L[1:])
    else:
        return f(L)

print map2(lambda x: x*2, L)

上記を実行した結果、ネストしたリストにも関数が適用されるようになった。

[2, [42, 44], 6, [82, [842, 844], 86, 88], 10]

再帰処理において map を使う

map2 関数の再帰処理はごちゃごちゃしている。 (+_+)

リストである場合の処理において、組込みの map 関数を利用して再帰的に関数を適用してみる。一気に変更するとわからなくなるので、まずは何もしない関数 map2b を定義。

def map2b(L):
    if isinstance(L, list):
        result = []
        for e in L:
            result += [map2b(e)]
        return result
    else:
        return L

こちらの方がコードがシンプルで読みやすい。

同じように、要素に関数を適用できるように変更する。

def map2b(f,L):
    if isinstance(L, list):
        result = []
        for e in L:
            result += [map2b(f,e)]
        return result
    else:
        return f(L)

print map2b(lambda x: x*2, L)

折角なので map で書き直してみる。

cf. Python の map, filter, reduce とリスト内包表記

def map2b(f,L):
    if isinstance(L, list):
        return map(lambda x: map2b(f,x), L)
    else:
        return f(L)

reduce で書くなら、map の部分を以下のように書ける。

return reduce(lambda a,b: a+[map2b(f,b)], L, [])

すぐに忘れる脳みそのためのメモ

2008年10月1日水曜日