標準ライブラリで色々用意されている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 lmain = 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 lmerge :: (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
