サイモン・ペイトン・ジョーンズらが執筆した論文を読んでいました。「Playing by the Rules: GHC における実用的な最適化手法としての書き換え」 . 2番目のセクション、つまり「基本的な考え方」で、彼らは次のように書いています。
mapリストの各要素に関数を適用するおなじみの関数を考えてみましょう。Haskell で書くと、map次のようになります。
map f [] = []
map f (x:xs) = f x : map f xs
ここで、コンパイラが の次の呼び出しに遭遇したとします
map。
map f (map g xs)
この式が
map (f . g) xs
(「.」は関数合成)、中間リストがないため、後者の式が前者よりも効率的であることがわかります。しかし、コンパイラにはそのような知識はありません。
考えられる反論の 1 つは、コンパイラはより賢くあるべきだというものです --- しかし、プログラマは、コンパイラが理解できないことを常に知っています。別の提案は次のとおりです。プログラマーがそのような知識をコンパイラーに直接伝達できるようにします。それが私たちがここで探求する方向です。
私の質問は、コンパイラをよりスマートにできないのはなぜですか? 著者は、「しかし、プログラマーは、コンパイラーが把握できないことを常に知っている」と述べています。map f (map g xs)ただし、コンパイラはが と同等であることを実際に把握できるため、これは有効な答えではありません。そのmap (f . g) xs方法は次のとおりです。
map f (map g xs)
map g xsと一体化map f [] = []。したがって
map g [] = []。map f (map g []) = map f [].map f []と一体化map f [] = []。したがって
map f (map g []) = []。map g xsと一体化map f (x:xs) = f x : map f xs。したがって
map g (x:xs) = g x : map g xs。map f (map g (x:xs)) = map f (g x : map g xs).map f (g x : map g xs)と一体化map f (x:xs) = f x : map f xs。したがって
map f (map g (x:xs)) = f (g x) : map f (map g xs)。
したがって、次のルールがあります。
map f (map g []) = []
map f (map g (x:xs)) = f (g x) : map f (map g xs)
ご覧のとおり、f (g x)ちょうど再帰的に呼び出されています(f . g)。map f (map g xs)これはまさに の定義ですmap (f . g) xs。この自動変換のアルゴリズムはかなり単純なようです。では、ルールを書き換える代わりにこれを実装してみませんか?