2008年9月28日日曜日

Python でリスト内のリストを連結 - Haskell の concat 関数を真似る

1. ネストしたリストの要素を結合したい

Python で、リスト内のリストを結合したい。

[[1,2,3],[4]] → [1,2,3,4]

Haskell の concat 関数 に相当する関数を探したが、見つからなかった。

Prelude> concat [[1,2,3],[4]]
[1,2,3,4]

自分で書くしかないのかな ?

 

2. Haskell の concat 関数は、型に注意

最初に、Haskell の concat 関数の動作を確認する。

Prelude によると、concat 関数の型は、

concat :: [[a]] -> [a]

いくつかの例を試す。

test1a = [[1,2,3],[4]]
test1b = [[1,2,3],4]

test2a = [[[1,2,3]],[[4]]]
test2b = [[[1,2,3]],[4]]

main = print $ concat test1b

実行したら、エラーが出た。 (+_+)

concattest.hs:2:18:
    No instance for (Num [t1])
      arising from the literal `4' at concattest.hs:2:18
    Possible fix: add an instance declaration for (Num [t1])
    In the expression: 4
    In the expression: [[1, 2, 3], 4]
    In the definition of `test1b': test1b = [[1, 2, ....], 4]

concattest.hs:5:21:
    No instance for (Num [t])
      arising from the literal `4' at concattest.hs:5:21
    Possible fix: add an instance declaration for (Num [t])
    In the expression: 4
    In the expression: [4]
    In the expression: [[[1, 2, ....]], [4]]

Haskell におけるリストの要素は、同じ型でなければならない。

[a]

「単一の数値」と「数値のリスト」は、型が異なる。「リスト」と「リストのリスト」も、型が異なる。

基本的なところを押さえてなかった。 パタッ(o_ _)o~†

 

3. Python で concat 関数を実装する

Haskell に準じて、

[[1, 2, 3], 4]

というリストは、対象にしないことにする。

「リストの中にあるリスト」

を結合する関数を定義する。

 

for ループ、リスト内包表記を使う場合

まずは、単純に for ループを使って実装する。

result = []
for es in [[1,2,3],[4]]:
    for e in es:
        result.append(e)

同じものをリスト内包表記で書く。

result = []
[[result.append(e) for e in es] for es in [[1,2,3],[4]]]

そうえいば、ループを二重に回す必要はなかった。 ^^; リスト内の要素を結合すると考えれば良い。

result = []
for e in [[1,2,3],[4]]:
    result += e

リスト内包表記の場合、上記のように代入文を使えないので extend を使う。

result = []
[(lambda x: result.extend(x))(e) for e in [[1,2,3],[4]]]

 

reduce 関数を使う

reduce 関数を使えばシンプルに書ける。

reduce(lambda a,b: a+b, [[1,2,3],[4]],[])

 

再帰的な定義

再帰で考える場合は、

  1. 空のリスト → 空
  2. 要素が 1 つのリスト → 要素を取り出す
  3. 要素が 2 つ以上 → 先頭の要素を取り出したものと、それより後ろの要素に再帰的に適用した結果を結合
def rec_concat(L):
    if L == []      : return []
    elif len(L) == 1: return L[0]
    else            : return L[0] + rec_concat(L[1:])

追記(2008.9.28) : 上記で書いた、リストの要素数が 1 つのときの処理は冗長だった。 (+_+) 要素が1つの場合は、要素が 2 つ以上のときの処理でまかなえる。要素が 1 つのときは、一つの要素の後ろに空の要素があると考えれば良い。

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

リストの要素が一つのとき、L[1:] は [] が返される。よって、空の検査をしている条件が適用される。

 

Haskell の concat の実装と比較する

Haskell の concat の実装は、Haskell Code by HsColour によると、

concat :: [[a]] -> [a]
concat = foldr (++) []

foldr 関数は、Python の reduce に相当すると見なせば良い。

 

itertools モジュールを利用する

追記(2008.9.28) : 6.5.3 Recipesitertools モジュールにおける chain 関数を使った例が書かれていた。このモジュールを使うなら、

from itertools import chain
def flatten(listOfLists):
    return list(chain(*listOfLists))

print flatten([[1,2,3],[4]])

変数 listOfLists を可変引数 *listOfLists に渡すことによって、リストの要素に分割されるようだ。

(cf. Python の可変引数)

 

4. Ruby の flatten の動作を再確認

Ruby には、どれだけ要素がネストしていようと、真っ平らにしてまうメソッドが Array クラスにある。

p [[1,2,3],4,[[[[[[[[[[5,[6,7]]]]]]]]]]]].flatten

結果、

[1, 2, 3, 4, 5, 6, 7]

Python で flatten - ネストしたリストをフラットにする」につづく…