>>654 ReadP の計算で左結合になってる >>= がある場合でも、 内側の P の >>= をすべて右結合にすることで、 P の >>= の再帰が無くなって効率が良くなる。
9節の第1パラグラフに書いてある通りなんだけど。
左結合を右結合にってのは、>>= の結合則 (m >>= f) >>= g == m >>= (\a -> f a >>= g) の左辺を右辺にするってな話。 例えば、string s >>= f でも string s の中で >>= を使ってるので、左結合になってる。 つまりほとんど全ての場合に当てはまる。
実際 String の ++ を頻繁に使う class Show あたりでは、 できるだけ type ShowS = String -> String を使うことになってる。 shows :: Show a => a -> ShowS を使ってさっきの foldl (.) id (map shows [1..10000]) [] をやってみると、今度は問題無く速い。
m >>= f (P の >>=)は、m の最後の return a を f a に置き換える。 それを効率よくやるには、最初っから return なんか使わないで、 Get (\c1 -> Get (\c2 -> return [c1,c2])) を \k -> Get (\c1 -> Get (\c2 -> k [c1,c2])) みたいにしとけばいいじゃんという発想。 つまり P a を forall b. (a -> P b) -> P b に、 m を m >>= に、>>= を \m f k -> m (\a -> f a k) にする。
foldr c n xs は、xs の : を c に、[] を n に置き換える。 それを効率よくやるには、最初っから : や [] なんか使わないで、 1:2:3:[] を \c n -> 1 `c` 2 `c` 3 `c` n みたいにしとけばいいじゃんという発想。 つまり [a] を forall b. (a -> b -> b) -> b -> b にする。 リストに戻すときは build xs = xs (:) [] を使う。 すると foldr c n (build xs) ==> xs c n と変換できる。
map f xs <==> build (\c n -> foldr (c . f) n xs) 例えばこういう変換を定義すれば、 (map f . map g) xs = map f (map g xs) ==> build (\c n -> foldr (c . f) n (build (\c n -> foldr (c . g) n xs))) ==> build (\c n -> (\c n -> foldr (c . g) n xs) (c . f) n) ==> build (\c n -> foldr (c . f . g) n xs) ==> map (f . g) xs のように map f . map g ==> map (f . g) という変換ができる。 map f . map g 以外にも、他のいろいろなリスト関数の foldr/build を使った形への変換を定義しておけば、いろいろな変換ができる。 foldr/build による融合変換ってやつ。今の GHC もこれを使ってる。 詳しくは GHC User's Guide の 8.13. Rewrite rules あたりを見てくれ。
