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_ _)ｏ~†
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 つ以上 → 先頭の要素を取り出したものと、それより後ろの要素に再帰的に適用した結果を結合
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 つのときの処理は冗長だった。 (+_+) 要素が１つの場合は、要素が 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 Recipes に itertools モジュールにおける 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 - ネストしたリストをフラットにする」につづく…
0コメント:
コメントを投稿