to2yの日記

 | 

2006-07-09「ふつける」勉強会5章レジュメ

遅延評価とは

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の様子が観察できるモードがあれば楽しいのに

 |