Hatena::Grouphaskell

猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 このページをアンテナに追加 RSSフィード

2012-05-07

第12章 遅延評価 #2

08:20 | 第12章 遅延評価 #2 - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

12.5 無限のデータ構造

Haskell遅延評価は、無限のデータ構造を相手にした時も、必要がない限り無限回の評価は行わない。

一般的に、遅延評価は次のような性質を持つ。すなわち、遅延評価を用いると、式が利用される文脈が要求する回数だけしか、その式は評価されない。

ones :: [Int]
ones =  1 : ones

こういう無限リストがあったとして、ones評価すると停止しないが、head ones評価は二段階で停止する。

ここでいう文脈とは、関数headが「リストをとり、先頭の要素を返す」という振る舞いそのもののこと。なので、onesの先頭の要素が確定するところまでしか簡約しない。ここではonesの要素は1という値なのだけれど、これが何らかの式だったとしても、評価のし方によっては、式そのものの評価までは必要ない場合もあって、そうするとその式はまだ簡約されない。

12.6 部品プログラミング

無限リストから最初のn個を取り出す、という計算では、無限リストはデータ部品、リストから最初のn個を取り出すのは制御部品、として分離できる。

データは制御が要求する回数だけ評価され、二つの部品は交互に簡約を実施する。

例として、エラトステネスのふるいを実装する。

  1. 無限リスト 2, 3, 4, 5, 6, ...を生成する
  2. リストの先頭の整数pを素数であると印を付ける
  3. pの倍数をリストから取り除く
  4. 二番目の手順に戻る

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'の定義は微妙に違っていて、$!を使わずに同じ効果を得ているようだけど。

第12章 遅延評価 #3

00:16 | 第12章 遅延評価 #3 - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

問題文だけ転記。

12.9 練習問題

  1. 以下の式において、簡約可能式はどこか?また、選び出した簡約可能式が、最も内側か、 最も外側か、両方か、いずれでもないかを考えよ。
    1+(2*3)
    (1+2)*(2+3)
    fst (1+2, 2+3)
    (λx→1+x) (2*3)
    
  2. fst (1+2, 2+3)評価する際、最内簡約よりも最外簡約の方が適している理由を述べよ。
  3. 定義 mult = λx→(λy→x*y) が与えられたとき、式 mult 3 4評価が四段階の手順になることを示せ。
  4. リスト内包表記を使って、以下に示すフィボナッチ数の無限リストを生成する関数 fibs :: [Integer] を実装せよ。(フィボナッチ数は急激に大きくなるので、多倍長整数 Integer を使っていることに注意)
    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
    以下の手順を踏むこと。
    • 最初の二つの数を0と1とする
    • 次の数は、前の二つの数を足して算出する
    • 二番目に戻る
    ヒント:ライプラリ関数 zip と tail を利用せよ。
  5. 関数 fibs を用いて、0番目から数えてn番目のフィボナッチ数を返す関数 fib :: Int -> Integer を定義せよ。また、1000より大きい最初のフィボナッチ数を計算する式を示せ。
  6. 以下のライブラリ関数が、 以下の二分木に対して動くように変更せよ。
    repeat              :: a -> [a]
    repeat x            =  xs where xs = x:xs
    
    take                :: Int -> [a] -> [a]
    take 0 _            =  []
    take (n + 1) []     =  []
    take (n + 1) (x:xs) =  x : take n xs
    
    replicate           :: Int -> a -> [a]
    replicate n         =  take n . repeat
    
    data Tree a = Leaf | Node (Tree a) a (Tree a)
    
    訳者からのヒント:nは木の深さを表す。