第12章 遅延評価 #4
12.9 練習問題
- 以下の式において、簡約可能式はどこか？また、選び出した簡約可能式が、最も内側か、 最も外側か、両方か、いずれでもないかを考えよ。
こんな感じ？簡約可能式に抜け漏れがなければいいけど。
- 1+(2*3)
- 2*3...最内
- 1+()...最外（追記）原著の解答では、こっちは簡約可能式とみなされてない……なぜだ。
- (1+2)*(2+3)
- 1+2...最内
- 2+3...どちらでもない（追記）こっちも最内といえるような気がするけど、原著の解答ではこっちは最内じゃないみたい。
- ()*()...最外
- fst (1+2, 2+3)
- 1+2...最内
- 2+3...どちらでもない（追記）こっちも最内といえるような気がするけど、原著の解答ではこっちは最内じゃないみたい。
- fst ()...最外
- (λx→1+x) (2*3)
- 2*3...最内
- 1+x...どちらでもない（追記）原著の解答ではこっちは簡約可能式とみなされていない。ラムダ式の内側だから？
- (λx→1+x) ()...最外
- 式
fst (1+2, 2+3)を評価する際、最内簡約よりも最外簡約の方が適している理由を述べよ。
最内簡約だと
1+2と2+3の両方を評価するが、最外簡約だと1+2だけ評価すればよいため。
- 定義
mult = λx→(λy→x*y)が与えられたとき、式mult 3 4の評価が四段階の手順になることを示せ。
- 初期状態
mult 3 4 - multを評価
(λx→(λy→x*y)) 3 4 - 3を束縛
(λy→3*y) 4 - 4を束縛
3*4 - 積を計算
12
- 初期状態
- リスト内包表記を使って、以下に示すフィボナッチ数の無限リストを生成する関数
fibs :: [Integer]を実装せよ。(フィボナッチ数は急激に大きくなるので、多倍長整数Integerを使っていることに注意)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
以下の手順を踏むこと。- 最初の二つの数を0と1とする
- 次の数は、前の二つの数を足して算出する
- 二番目に戻る
fibs :: [Integer] fibs = 0 : 1 : [x + y | (x, y) <- zip fibs (tail fibs)]
- 関数
fibsを用いて、0番目から数えてn番目のフィボナッチ数を返す関数fib :: Int -> Integerを定義せよ。また、1000より大きい最初のフィボナッチ数を計算する式を示せ。
fibsはリストなんだから、これでいいよね。
fib :: Int -> Integer fib = (fibs !!)
1000より大きな最初のフィボナッチは
head $ dropWhile (<=1000) fibsでいいですか。
- 以下のライブラリ関数が、 以下の二分木に対して動くように変更せよ。
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は木の深さを表す。
repeatは左の子にぶら下げるべきか、両方の子にぶらさげていくべきか。とりあえず両方の子にぶら下げよう。repeat' :: a -> Tree a repeat' x = xt where xt = Node xt x xt
takeは、n+1パターンは使えない前提で。take' :: Int -> Tree a -> Tree a take' 0 _ = Leaf take' n Leaf = Leaf take' n (Node l x r) = Node (take' (n-1) l) x (take' (n-1) r)
replicateはそのまま。replicate' :: Int -> a -> Tree a replicate' n = take' n . repeat'
