第12章 遅延評価 #3

問題文だけ転記。

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は木の深さを表す。