前回は遅延評価の仕組みについて説明しました。今回は前回の知識をもとに，遅延評価の効率について検討していきたいと思います。
遅延評価のほうが速くなる場合
遅延評価の利点は，これまで何度も説明してきたように，無駄な計算を省けるところにあります。
(\x -> fst (sum x, product x)) [0..5]という式について考えてみましょう。sumとproductはいずれもPreludeの関数で，有限リストの数字を「足し合わせる関数」と「掛け合わせる関数」です（参考リンク）。この式は，先行評価ではこのように簡約されます。
先行評価 (\x -> fst (sum x, product x)) [0..5] => (\x -> fst (sum x, product x)) [0,1,2,3,4,5] => fst (sum [0,1,2,3,4,5], product [0,1,2,3,4,5]) => fst (15, product [0,1,2,3,4,5]) => fst (15, 0) => 15
一方，遅延評価での簡約は以下のようになります。
遅延評価 (\x -> fst (sum x, product x)) [0..5] => fst (sum x, product x); x = [0..5] => sum x; x = [0..5] => 15
遅延評価では，不要なproductの計算が省かれている分，簡約段数（簡約ステップ数）が少なくなっているのがわかりますね。
また，遅延評価の利点を生かせない場合でも，遅延評価の簡約段数が先行評価よりも多くなることはありません。以下のように，グラフ簡約のおかげでsumとproductの変数xが別々に評価されるのを防げるからです。
先行評価 (\x -> (sum x, product x)) [0..5] => (\x -> (sum x, product x)) [0,1,2,3,4,5] => (sum [0,1,2,3,4,5], product [0,1,2,3,4,5]) => (15, product [0,1,2,3,4,5]) => (15, 0)
遅延評価 (\x -> (sum x, product x)) [0..5] => (sum x, product x); x = [0..5] => (0+1+2+3+4+5, product x); x = [0,1,2,3,4,5] （↑グラフ簡約により，この時点で評価されたxをproductでも使える） => (15, product x); x = [0,1,2,3,4,5] => (15, 0)
このように，遅延評価はその性質をうまく生かすようにプログラミングすることで簡約段数を少なくできます。グラフ簡約があるため，たとえ遅延評価の特徴を生かし切れなくても，先行評価より簡約段数が増えることはありません。簡約段数の面から見れば，遅延評価のプログラムのほうが先行評価に比べて速いといえるでしょう。
遅延評価のほうが遅くなる場合
では，しばしば「Haskellプログラムが遅い」とか「遅延評価を使っているので遅い」といわれる理由はどのあたりにあるのでしょうか？
それは，計算を行うときの所要領域にあります。時間計算量（time complexity）にほとんど有意な差がない場合，領域効率（space efficiency，空間効率，あるいはspace complexity，領域計算量）の差がプログラムの実行速度の明暗を分けます。なぜなら，ハードウエアが効率的に利用できるメモリー（例えばキャッシュ・メモリー）の容量には制約があるからです。効率のよい領域に入りきらなかった変数は，より効率の悪い領域（メイン・メモリーやディスク上のキャッシュ）に置かれます。効率の悪い領域での操作は，それだけ負荷（overhead，オーバーヘッド）を伴うものになります。
一般に，遅延評価は先行評価に比べてプログラムに必要な所要領域が増大する傾向があります（もちろん，遅延評価がうまく当てはまる場合など，逆のこともありますが）。所要領域が大きくなれば，メモリーの確保，操作，ガーベジ・コレクション（GC: Garbage Collection，ごみ集め）の三つの段階における負荷が増大します。このため，簡約段数などに表れる時間計算量には差がない（あるいは速い）にもかかわらず，結果として遅延評価を行うプログラムが，先行評価のプログラムより遅くなってしまうことがよくあります。これが，一般に「遅延評価が遅い」といわれる主な理由です（遅延評価特有のコストも存在しますが，これらも広い意味では「所要領域の増大」の一種と考えることができます。参考リンク1，参考リンク2）。
例として，sum [0..1000000]という式について考えてみましょう。標準Haskellではsumは以下のように定義されています。
sum :: (Num a) => [a] -> a sum = foldl (+) 0
foldl（fold-left）は第7回で紹介したfoldr（fold-right）の親戚です（参考リンク）。
foldl :: (a -> b -> a) -> a -> [b] -> a foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs
したがって，sum [0..1000000]は以下のように簡約されます。
sum [0..1000000] => foldl (+) 0 [1..1000000] => foldl (+) (0+1) [2..1000000] => foldl (+) ((0+1)+2) [3..1000000] . . . => foldl (+) ((… ((0+1)+2)+ … )+ 1000000) [] => ((… ((0+1)+2)+ … )+ 1000000) => 500000500000
遅延評価が災いし，最終的に((… ((0+1)+2)+ … )+ 1000000)を評価するまで所要領域が膨れ上がっているのがわかるでしょう。この式を実際に評価してみると，オプションを指定して使用するメモリー量を増やさない限り，以下のようなエラー・メッセージを見ることになると思います（参考リンク1，参考リンク2）。
Prelude> sum [0..1000000] *** Exception: stack overflow
ここで，実際にメモリーがどのように使われるかを確かめるために，メモリーの使用状況を見る方法を紹介しておきましょう。GHCでは，-profオプションを指定してプログラムをコンパイルすることで，プログラムを実行するランタイム・システム（RTS：RunTime System）にプロファイルを取る機能を組み込むことができます（参考リンク）。
main = print $ sum [0..1000000]
というプログラムをLazy2.hsという名前で保存し，以下のコマンドを実行してみてください。
$ ghc --make Lazy2.hs -prof [1 of 1] Compiling Main ( Lazy2.hs, Lazy2.o ) Linking Lazy2.exe ... $ ./Lazy2 +RTS -K100M -hc 500000500000 $ hp2ps Lazy2.hp
最初に-profオプションを指定してLazy2.hsをコンパイルしています。次に，実行可能ファイルLazy2のランタイム・システムに組み込まれた-hcオプションを使って，<実行コマンド名>.hpファイルを生成しています。最後に，GHCに付属するhp2psコマンドで<実行コマンド名>.hpの内容をわかりやすく図にした<実行コマンド名>.psのポストスクリプト（PostScript）ファイルを生成しています（参考リンク1，参考リンク2）。この例ではLazy2.hpが生成され，それを使ってLazy2.psを生成しているのがわかるでしょう。
Lazy2の+RTSオプションは，その後に続く引数がすべてランタイム・システムを対象にすることを指示するものです。この後にランタイム・システムを対象にしない引数を指定したい場合には，ランタイム・システムを対象とするオプションの最後に-RTSを付けてください。そうすれば，+RTSと-RTSで挟まれた部分だけがランタイム・システムを対象にするようになります（参考リンク）。-K100M（-Ksize）オプションで，スタック・オーバーフローを回避するためにスタックとして100MBのメモリーを確保するよう指示しています。
実行時の状況によってグラフの形状に多少の差が出ますが，だいたい山あるいは下り坂のような形になると思います。大量に確保したスタックが開放されていくことを示します。CAFという見慣れない言葉が使われていますが，これはConstant Applicative Form（定作用形）の略です。モジュールのトップレベル（大域レベル）で定義される12や1+2，*3といった「引数を持たない式」（ラムダ抽象を除く）のことです（参考リンク）。
