foldl, foldl’, foldr

結局どれよ

標準ライブラリで色々用意されているfold系関数の使いこなしに関しては色々な情報がネットに存在します。確認のために調べると

  • 畳み込むなら foldr より foldl (末尾再帰するから。thunk作らないから。)
  • foldl より foldl' (正格評価するから。)

ということで間違いないみたい。

さて、例外はあるだろうか?

手元に何も考えずにfoldlを使ったプログラムがありました。簡単に言ってしまえば以下のようなSTDINから読んだデータ :: [an instance of Read] の合計(または平均)を取るようなプログラムです。十数MBのデータを処理したりしていたので、高速化のためmconcatの部分を☆から★に変えてみることにしました。

instance Monoid Contents where
mappend a b = ...
mconcat (a : l) = foldl mappend a l -- ☆
mconcat (a : l) = foldl' mappend a l -- ★
merge :: (Eq a, Ord a) => [(a, Contents)] -> [(a, Contents)]
merge l = map (id &&& (mconcat . vals)) keys
where
vals :: a -> [Contents]
vals k = map snd $ filter ((k ==) . fst) l
keys :: [a]
keys = nub $ map fst l
main = print . merge =<< getContents

ghc-8.0.2で -O1 フラグを付けてコンパイルして実行してみると

$ time average-csv < test.csv > res1  # foldl を使った方
real 0m50.085s
user 0m49.873s
sys 0m0.210s
$ time average-csv < test.csv > res2 # foldl' を使った方
real 0m57.448s
user 0m57.287s
sys 0m0.163s
$ diff -u res*
$

何度やってもこうなる🙁 keys の正格評価が問題なのだろうか??? だったら試してみよ。

Day 2: そのうちやってみる予定

今ここ

Appendix

STDINから読んだデータ :: [an instance of Read] の合計(または平均)を取るようなプログラム。

instance Monoid Contents where
mconcat (a : l) = foldl mappend a l
mconcat (a : l) = foldl’ mappend a l
merge :: (Eq a, Ord a) => [(a, Contents)] -> [(a, Contents)]
merge l = map (id && (mconcat . vals)) keys
where
vals :: a -> [Contents]
vals k = map snd $ filter ((k ==) . fst) l
keys :: [a]
keys = nub (map fst l)

ghc-8.0.2での実行結果

$ time gp-averagecsv < test.csv > sort1.csv # foldl を使った方
real 0m50.085s
user 0m49.873s
sys 0m0.210s
$ time gp-averagecsv < test.csv > sort2.csv # foldl’ を使った方
real 0m57.448s
user 0m57.287s
sys 0m0.163s

Show your support

Clapping shows how much you appreciated Shuji N.’s story.