12.5 無限のデータ構造
Haskellの遅延評価は、無限のデータ構造を相手にした時も、必要がない限り無限回の評価は行わない。
一般的に、遅延評価は次のような性質を持つ。すなわち、遅延評価を用いると、式が利用される文脈が要求する回数だけしか、その式は評価されない。
ones :: [Int] ones = 1 : ones
こういう無限リストがあったとして、onesを評価すると停止しないが、head onesの評価は二段階で停止する。
ここでいう文脈とは、関数headが「リストをとり、先頭の要素を返す」という振る舞いそのもののこと。なので、onesの先頭の要素が確定するところまでしか簡約しない。ここではonesの要素は1という値なのだけれど、これが何らかの式だったとしても、評価のし方によっては、式そのものの評価までは必要ない場合もあって、そうするとその式はまだ簡約されない。
12.6 部品プログラミング
無限リストから最初のn個を取り出す、という計算では、無限リストはデータ部品、リストから最初のn個を取り出すのは制御部品、として分離できる。
データは制御が要求する回数だけ評価され、二つの部品は交互に簡約を実施する。
例として、エラトステネスのふるいを実装する。 +無限リスト 2, 3, 4, 5, 6, ...を生成する +リストの先頭の整数pを素数であると印を付ける +pの倍数をリストから取り除く +二番目の手順に戻る
Haskellではこれを素直にプログラムとして表現できる。しかも、無限リストを生成する手順1と、制御を表す手順2～4を別の部品にできる。
primes :: [Int] primes = sieve [2..] sieve :: [Int] -> [Int] sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
このように定義したprimeを評価すると、無限リストと関数sieveは交互に簡約される。
12.7 正格適用
- 基本型の場合は、値が定まるまで
- タプルの場合は、タプルが得られるまで
- リストの場合は、空リストまたは先頭の要素が得られるまで
評価を実行し、その後は通常の関数適用と同じ動きになる。
タプルやリストの要素自体の評価はどうするんだろうと思ってちょっとぐぐった。こっちも、基本型なら値が定まるまで評価されるのかな？
リストの和を取る関数を考える。
sumwith :: Int -> [Int] -> Int sumwith v [] = v sumwith v (x:xs) = sumwith (v + x) xs
この関数定義だと、加算を実行する前に、全体の和を式として構築するため、長いリストを相手にするとメモリが足りなくなる。
sumwith' :: Int -> [Int] -> Int sumwith' v [] = v sumwith' v (x:xs) = (sumwith' $! (v + x)) xs
この関数定義であれば、再帰のたびに引数を正格評価するので、メモリが足りなくならない。
同様にfoldlの正格評価を考える。
foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f v [] = v foldl' f v (x:xs) = ((foldl' f) $! (f v x)) xs
このように定義したfoldl'であれば、長いリストに対しても適用できる。
ちょっとぐぐったら、Haskellにおけるfoldl'の定義は微妙に違っていて、$!を使わずに同じ効果を得ているようだけど。
