2015-12-28 『ふつうのHaskellプログラミング』 もくもく読書会（第5章）の振り返り

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

第5章 遅延評価

評価

• プログラミングの世界では「実行」、「計算」とほぼ同じ意味
• ラテン語の「ex + value」より来ている
  → 「値をひねり出す」の意味
• Haskellの評価モデルは置き換えモデル（substitution model）で表現できる
• Haskellの評価は遅延評価（lazy evaluation）である
• 必要な式しか評価されない

最外簡約（outermost reduction）

Haskellの評価過程を段階的に表現する

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

この評価の仕方を最外簡約（outermost reduction）と言う

逆にJavaなどのように

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

と評価されるのを最内簡約（innermost reduction）と言う

グラフ簡約（graph reduction）

• square関数の引数の(1 + 3)は1度だけ評価され、それ以降は結果が共有される
• この式を共有しながら簡約する方法をグラフ簡約（graph reduction）と言う

if.hs

※ Windowsのコマンドプロンプトでghcでif.hsをコンパイル後に下記で実行しようとしたらエラーになる

> if
コマンドの構文が誤っています。

if.exeもしくは本のように.\ifとする必要がある

データ構造の遅延評価

• Haskellでは実際にプログラムで使われる要素だけ作成される

例1：

take 10 lines <= getContents

では、何万行もあるファイルを指定したとしても10行分しか文字列処理をしない

例2：

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

では、リスト自体は全て評価されるが、各要素の式は評価されない

遅延評価で式の値が必要とされるタイミング

Haskellでは以下の2か所

• パターンマッチ
• 組み込み演算

myIf :: Bool -> a -> a -> a
myIf True t e = t
myIf False t e = e

では、myIf関数を使う際に第1引数は必ず評価されるが第2引数と第3引数は必要になるまで評価されない

参照透明性

• 同じ引数を渡せば毎回同じ結果が返る性質
• Haskellは参照透明である

遅延評価の利点

• 不要な計算を減らせる
• 無限の長さのリストが扱える
• インターフェイスが統一できる

無限リストの使い道

• 数学の問題でも解く状況下でない限り、無限リストは使いどころがないと思われがち
• 標準入力は論理的に無限リスト
• WEBアプリケーションでHTTPリクエストの無限リストを受け取ってHTTPレスポンスの無限リストを返す関数を考えるときれいにモデル化できる

インターフェイスを統一できる

• 様々な処理をリスト処理にできる
• 例えば巨大なツリー構造の全要素をリストにする場合
• getContentsアクションもリスト処理で対応できる

コメント

• 「インターフェイスが統一できる」と言う遅延評価の利点はあまりピンとこない。
  → 高階関数の利点なのでは？

遅延評価の欠点

• 思った順番で操作を実行するのが難しい
• デバッグしにくい

デバッグしにくい理由

• 意味があるスタックトレースがとれない
• どのような順序で評価されるのか予想がつかない

コメント

• 意味があるスタックトレースがとれない理由があまりピンとこない
  → 参照透明性であるなら引数の値がわかれば毎回同じ順序で評価されるので追えそうな気もするが？
  → よく手で書きだすステップ実行的なイメージだったが、コンパイラが内部で色々やるらしい →　それじゃ、無理だ…