Haskell 5日目

Haskellの勉強5日目
今日は第5章 遅延評価です。

評価とは

評価(evaluation)という言葉を改めて述べると、プログラミングの世界では実行、計算とほぼ同じ意味で使われます。
原語をたどると、evaluateはラテン語のex+valueから来ており、直訳すると「値を出してくる」という意味になります。
つまり式から値をひねり出すことがevaluateになり、Haskellでの評価もその意味になります。

Haskellの評価過程は、置き換えモデル(substitution model)というモデルを使って表現できます。
置き換えモデルでは関数の適用を定義で置き換えることによってプログラムを評価します。

例えばsquare関数

square n = n * n

として、square (1 + 3)を評価すると、仮引数nを(1 + 3)に置き換えるので、

   square (1 + 3)
→ (1 + 3) * (1 + 3) 

となります。
この関数の適用を定義で置き換える作業を簡約と言います。

上記の式を最後まで評価すると、

   square (1 + 3)
→ (1 + 3) * (1 + 3) 
→ 4 * 4
→ 16 

となります。

CやJavaは最内簡約、Haskellは最外簡約

CやJavaのように、

   square (1 + 3)
→ square 4 
→ 4 * 4
→ 16

という順序で式を評価する評価のしかたを最内簡約(innermost reduction)と言います。
最内簡約は引数を簡約してから関数を展開します。

Haskellのように

   square (1 + 3)
→ (1 + 3) * (1 + 3) 
→ 4 * 4
→ 16

という順序で式を評価するとき、その評価のしかたを最外簡約(outermost reduction)と言います。
最内簡約は関数を展開してから引数を簡約します。

このように評価が最外簡約を使って行われるという点が、遅延評価の大きな特徴となります。

グラフ簡約

Haskellは最外簡約なので、

   square (1 + 3)
→ (1 + 3) * (1 + 3) 
→ 4 * 4
→ 16

という順序で式が評価されますが、評価の過程で(1 + 3)が2つに増えています。
この2つの(1 + 3)は、2カ所で別々に簡約されるのではないかと思ってしまいますが、そうではなく1度だけ簡約されます。

簡約の過程で、引数(1 + 3)は共有され、式を共有しながら簡約されます。
このような簡約方法をグラフ簡約(graph reduction)と言います。

グラフ簡約は遅延評価を実装する時の代表的な手法です。

データ構造の遅延評価

Haskellではデータ構造も遅延評価されます。

head関数の例で見ると

main = do cs <- getContents
       putStr $ firstNLines 10 cs

firstNLines n cs = unlines n $ take n $ lines cs

「lines cs」とあるので、標準入力から読み込んだ文字列はこの時点ですべて行ごとのリストに分割されてしまいそうにみえますが、「lines cs」の前に「take n」があり、nは10なので、「lines cs」の返り値のうち必要になるのは最初の10要素だけです。
ですので、「lines cs」では10行分しか文字列を処理しません。

検証する時に巨大なファイルを処理させても、あっという間に終わります。

次の例、以下のような式があったとします。

length [(1+1), (2+2), (3+3)]

この場合、リストの末尾までたぐらないとlength関数の返り値が計算できないので、リスト自体は評価されますが、リストの要素は必要ないので評価されません。つまり(1+1)、(2+2)、(3+3)は評価されません。

遅延評価の限界

遅延評価は必要がなければ評価されない特徴をもっていますが、限界があります。

tail.hsの例を見ると

main do cs <- getContents
        putStr $ lastNLines 10 cs

lastNLines n cs = unlines $ takeLast n $ lines cs

takeLast n ss = reverse $ take n $ recerse ss

このプログラムの例ではreverse関数が使われており、reverse関数はリストの最後までたどって全体を再構成するので、途中でリスト全体がプロセスに残ってしまいます。
そのため、このプログラムで巨大なファイルを処理させると、メモリを大量に使用することになります。

遅延評価は「必要なだけしか」式を評価せずデータ構造も作りませんが、巨大なデータ構造全体が必要になるプログラムを書いてしまえば、やはり巨大なデータが一度に作成されますので、この点では注意が必要です。

なお、メモリを大量に消費しないようにtails.hsを記述することも可能です。

長くなったので、今日はここまで

関連記事

[Haskell][プログラミング言語][関数型言語]Haskell 4日目
[Haskell]Haskellのリファレンスマニュアルを検索するツール href
[Haskell][プログラミング言語][関数型言語]ふつうのHaskellプログラミング
[プログラミング言語]ハッカーを目指す者が習得すべき５つのプログラミング言語
[プログラミング言語]プログラミング言語ヒエラルキー

ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門