to2yの日記

■ 遅延評価とは

haskellの評価過程は項置き換えモデルで表現できる。

square (1 + 3)
-> (1 + 3) * (1 + 3)
-> 4 * 4
-> 16

haskellの評価方法

最外簡約：一番外側の項の簡約規則を適用

グラフ簡約：同じように表示された項は一度だけ簡約

※参照透明性が確保されているから可能？

■ ifを関数として書く

定義は教科書参照のこと

Schemeでは

ifをspecial formとして定義することにより評価順を制御

javaではifを関数ではなく、statementとして用意して、評価順を制御

■ データ構造の遅延評価

データ構造（リストやタプル）も必要なときに初めて評価される

■ 遅延評価のシミュレーション

myifとmap（リスト処理）

■ 遅延評価の利点と欠点

• 不要な計算を減らせる
• 無限の長さのリストが扱える。

最終評価に必要な部分しか評価しないので、全体が無限長であっても問題ない

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

本文と題目があっていないような・・・

あるデータ構造から他のデータ構造への変換を、コストを気にせず気軽に出来る。

（そして、最終的にはリスト形式に落とせるのでうれし <- 本当か？）

■ たらいまわし関数(竹内郁夫関数？）

   print (tarai 20 10 5)
-> print (if 20 <= 10 then 10 else (tarai (tarai (20-1) 10 5) (tarai (10-1) 5 20) (tarai (5-1) 20 10)
-> print (if False then 10 else (tarai (tarai (20-1) 10 5) (tarai (10-1) 5 20) (tarai (5-1) 20 10)
-> print (tarai (tarai (20-1) 10 5) (tarai (10-1) 5 20) (tarai (5-1) 20 10)
-> print (if (tarai (20-1) 10 5) <= (tarai (10-1) 5 20) then (tarai (10-1) 5 20) 
else tarai ( tarai ( (tarai (20-1) 10 5)-1) (..) (..) ) (tarai (..) (..) (..)) (tarai (..) (..) (..))

とここまで書いて

haskellの計算時間が圧倒的に早いのは、グラフ簡約だからではないかと考察

reductionの様子が観察できるモードがあれば楽しいのに