Python3で高階関数 (map/filter/product, 畳み込み関数)

(2017.8.6)

Pythonでは, 関数に ()を付けなければ, 呼び出しではなく, 関数オブジェクトになる。別の関数呼び出しの引数として関数を渡すのがたやすい。関数を引数として取る関数を「高階関数」higher-order function という。

高階関数を使うと、アルゴリズムと適用する処理を分離することができる。ソースコードの再利用性が高まる。

_内包表記を分解

高階関数と一口に言っても, いくらでもある。まずは簡単に, 内包表記の機能を支える関数を紹介する。

Python は, リストを取りそうなところには iterable を与えるようになっている。リスト内包表記も、本当にリストが欲しい場合以外は、ジェネレイタ内包表記が推奨される。

何でも iterable とイテレイタ。

ただ、概念として iterable よりもリストで考えたほうがイメージしやすいことが多い。

map()関数

各要素に対して関数を適用する。

Pythonなので, リストを取って関数を適用、ではない。iterable を取って, 各要素に対して関数を適用する。

map( 関数, iterable )

map()関数の戻り値は class 'map' 型のオブジェクト. __iter__(), __next__() を持ち, イテレイタとして振る舞う。

リストを取って、関数を適用し、リストを得る、と考えたほうが分かりやすい。

Python
  1. lst = [-1, 3, -5, 7, -9]
  2. # 組み込み関数
  3. print( list( map(abs, lst) ))
  4. # ラムダ式
  5. print( list(map(lambda x: x * 2, lst) ))
  6. import operator
  7. # 関数形式の標準演算子
  8. print( list( map(operator.neg, lst) ))
実行結果
[1, 3, 5, 7, 9]
[-2, 6, -10, 14, -18]
[1, -3, 5, -7, 9]

map()関数は、要素の数は変えず、一つ一つの要素を変換する。map() の第1引数 関数 が値を返さなかった場合, その要素は None になる。要素が詰められるわけではない。

map()関数は、ジェネレイタの内包表記を使って, 次とまったく同じです。

Python
  1. def my_map(func, iterable):
  2. return (func(x) for x in iterable)

filter()関数

要素を取捨選択する。

filter( 関数, iterable )

こちらも実際にはリストを取るわけではない。iterable の各要素に対して関数を適用して、真となった要素のみを残すようなイテレイタを返す。

filter()関数の戻り値は class 'filter' 型のオブジェクト。mapオブジェクトと同様に, iterator として振る舞う。

Python
  1. lst = [-1, 3, -5, 7, -9]
  2. print( list( filter(lambda x: x >= 0, lst) ))
実行結果
[3, 7]

filter関数は次とまったく同じです

Python
  1. def my_filter(func, iterable):
  2. return (x for x in iterable if func(x))

product()関数

組み合わせ.

複数のイテレイタを取り、すべての組み合わせをタプルにして生成。

Python
  1. import itertools
  2. lstA = [-1, 3, -5, 7]
  3. lstB = [2, 3]
  4. print( list(itertools.product(lstA, lstB) )) # 後ろの引数が内側
実行結果
[(-1, 2), (-1, 3), (3, 2), (3, 3), (-5, 2), (-5, 3), (7, 2), (7, 3)]

次と同じ。

Python
  1. def my_product(i1, i2):
  2. return ( (i,j) for i in i1 for j in i2 ) # 右のforが内側

_畳み込み関数

「畳み込み」というのは, リストの隣同士の要素に対して演算を行い、結果として一つの値を得るようなもの。

演算の順序として, foldl (fold-left) と foldr (fold-right) がある。

Haskell には両方ある。foldr, foldl の宣言は次のようになっている。引数は次の3つ --関数、初期値、リスト.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

それぞれ, 次のような演算が行なわれる。

foldr func z []   = z
foldr func 初期値 [x0, x1, ..., xn] = x0 `func` (x1 `func` (...(xn `func` 初期値)))

foldlは次のようになる;

foldl func z []  = z
foldl func 初期値 [x0, x1, ..., xn] = (((初期値 `func` x0) `func` x1)...) `func` xn

Haskellは遅延評価で、無限リストは foldr で扱える。foldlとfoldrについては、例えばこの記事が興味深い; foldlを直す - 純粋関数空間

いっぽう Python は正格評価で, iterableは左からしか要素が取り出せない。畳み込みは reduce()関数という名前で, fold-left になっている。

Python3で、functools モジュールに移動した。

functools.reduce( func, iterable [, 初期値] )

初期値が省略された場合, リストの最初の要素が取り出され, 初期値となる。初期値が省略され、さらにリストが空だったときは、TypeErrorが投げられる。

初期値があるがリストが空、あるいは初期値が省略されてリストの要素がただ一つのときは、その値がreduce()の計算結果となる。

例;

Python
  1. import functools # Python3
  2. lst = [1, -3, 5, -7, 9]
  3. print( functools.reduce(lambda x,y:x+y, lst) )
実行結果
5

第一引数として2つ引数を取る (+) を与えた。この例では ((((1 + (-3)) + 5) + (-7)) + 9) => 5 となる。reduce()の戻り値はイテレイタではなく、計算結果。

reduce()さえあれば、ほかの畳み込む関数を作れる。ただし、組み込み関数は最適化されているはずで、無闇に自作関数を使うべきではない。

all(), any()は, 高階関数として作ると, 次のようになる。

Python
  1. import functools
  2. # @return 全部の要素についてfunc(item)が真の場合、True. そうでない場合 False.
  3. # iterable が空リストの場合は True.
  4. # Python の論理ANDは 'and'.
  5. # 戻り値は左辺または右辺 (True/Falseではない) で、0や''は偽.
  6. def my_all(func, iterable):
  7. first_false = [None]
  8. # lambda式の制約が厳しいため、関数で定義する
  9. def a_and_b(x, y):
  10. ret = func(y)
  11. if ret:
  12. return ret
  13. # 全部走査する必要なし.
  14. first_false[0] = ret
  15. raise StopIteration
  16. try:
  17. # 最初の要素から判定するため, 初期値が必要
  18. return functools.reduce(a_and_b, iterable, True)
  19. except StopIteration:
  20. return first_false[0]
  21. # @return どれかの要素のfunc(item)が真の場合, True. そうでない場合 False.
  22. # iterable が空リストの場合は False.
  23. # 論理OR 'or' の値も、左辺または右辺.
  24. def my_any(func, iterable):
  25. first_true = [None]
  26. def a_or_b(x, y):
  27. ret = func(y)
  28. if not ret:
  29. return ret
  30. first_true[0] = ret
  31. raise StopIteration
  32. try:
  33. return functools.reduce(a_or_b, iterable, False)
  34. except StopIteration:
  35. return first_true[0]
  36. print( my_all(lambda x: x, []) ) #=> True
  37. print( my_all(lambda x: x, ['']) ) #=> ''
  38. print( my_all(lambda x: x, [1, 0, 3]) ) #=> 0
  39. print( my_all(lambda x: x, ['a', 'b', 'c']) ) #=> 'c'
  40. print( my_any(lambda x: x, []) ) #=> False
  41. print( my_any(lambda x: x, ['', 'a', 'b']) ) #=> 'a'
  42. print( my_any(lambda x: x, ['', False, 0]) ) #=> 0
実行結果
True

0
c
False
a
0

最初 a and b, a or bで作っていたが、隣同士で演算することもなかった。それから、この例では、条件によっては途中で脱出できる。

返す値はリストでもいい

reduce()は、別に畳み込まなくてもいい。reduce()に渡す第1引数がリストを返すようにすれば、reduce()の結果もリストになる。

Python
  1. import functools
  2. def my_map(func, iterable):
  3. # lambda式は代入すら書けない
  4. def list_extend(list, item):
  5. list.extend([item]) # 戻り値はNone
  6. return list
  7. return functools.reduce(lambda x, y: list_extend(x, func(y)), iterable, [])
  8. print( my_map(lambda x: x * x, []) )
  9. print( my_map(lambda x: x * x, [1, -2, 3]) )
実行結果
[]
[1, 4, 9]