map分配則

 プログラム運算は, プログラムの変形なので, そのための変換規則というのがありますが, そのうちの一つに, map分配則というものがあります.

 map分配則は, 次のような規則です.

map (f . g) = map f . map g

 両辺とも意味的には同じなのですが, 片方の式が実行時間が短くなります.
 さてどちらでしょうか.
 高速化(等)のためのプログラム変換なので, 上記の式の片方がプログラム中に登場した時もう片方へ書き換えることで, 高速化を図るというテクニックです.

 実行時間は 左辺 > 右辺 左辺 < 右辺となります. つまり, 上の等式の右辺のような式を見つけた時, 左辺に変換可能であり, かつ, 左辺に変換することで高速化します.

 理由は簡単で, 右辺 map f . map g は, リストを生成を二回行いますが, 左辺 map (f . g)は, mapの回数が一回なので新しいリストを一回生成するに留まります. 右辺はほとんど, 二度ループを行っているようなものですね.

 等式ついては例えば, 次のように証明できます.

mapの定義は次のものとし,
map f [] = []
map f (x:xs) = f x : map f xs

また, 合成関数は次のように定義します.
(f . g) x = f (g x)

この時, 数学的帰納法により等式の証明を試みると
i) 空リストについて, mapの定義より,
map (f . g) [] = []であり,
(map f . map g) []
= map f (map g [])
= map f [] = []で空リストについて成立するので,  成立します.

ii) あるリストxsについて, map (f . g) xs  = (map f . map g) xs が成立すると仮定する.
xsに1つ要素をconsしたリスト(x:xs)について,
map (f . g) x:xs
= (f . g) x : map (f . g) xs
= f (g x) : map (f . g) xs
= {ここで仮定より} f (g x) : (map f . map g) xs    ......①
(map f . map g) (x:xs)
= {合成関数の定義より} map f (map g (x:xs))
= map f (g x : map g xs)
= f (g x) : map f (map g xs)
= {合成関数の定義から} f (g x) : (map f . map g) xs
= {①より} map (f . g) x:xs
より, 与えられたリストがx:xsの時にも map (f . g) = map f . map gが成立.

 というわけで数学的帰納法によりmap分配速が成立する. この辺までは高校レベルの数学に登場する数学的帰納法を知っていれば, 理解できます.
※) Haskellの記法なので, 関数適用がcons演算子や関数合成の演算子よりも優先順位が高いことに注意.

 map分配則は直感的に理解できるもので, わざわざ証明するまでもないようなものですが, もう少し複雑な規則なら上記の手法を用いることで, バグを含まない健全さを手に入れることができるかもしれません.

 さて, 問題はホントに速いのかということですが, 実際にやってみました.

こんなプログラムを用意して,

import Data.Time

gettime ls = do
  start <- getCurrentTime
  print $ sum ls
  end <- getCurrentTime
  print $ "elapsed time : " ++  (show $ diffUTCTime end start)

f = (20 *)
g = (1 +)

ghci上で実際に次のように計測してみたところ,

*Main> gettime $ (map f . map g) [1..10000000]
1000000300000000
"elapsed time : 7.2572358s"
*Main> gettime $ map (f . g) [1..10000000]
1000000300000000
"elapsed time : 5.2496645s"

map (f . g)の方が高速であることが分かるかと思います.