プログラミングHaskell 12章

12.hs

{--
12.1 
     1 + (2*3) の簡約可能式は
       最も外側のものが 1+(2*3)
       最も内側のものが (2*3)

     (1+2)*(2+3)の簡約可能式は
	最も外側のものが (1+2)*(2+3)
	最も内側のものが (1+2)と(2+3)の両方

     fst(1+2, 2+3)の簡約可能式は
     	最も外側のものが fst(1+2, 2+3)
	最も内側のものが 1+2と2+3の両方

     (\x -> 1 + x) (2*3)の簡約可能式は
     	 最も外側のものが (\x -> 1 + x) (2*3)
	 最も内側のものが 2*3
--}

{--
12.2
	fstはタプルの第一要素を返す関数であり、他の要素を必要としない。
	必要の無い要素を評価しても計算時間が無駄になるため、最外簡約の方が適している。
--}

{--
12.3
	mult 3 4               (multを評価する)
	(\x -> ...) 3 4        (\x -> ...) 3 を評価する
	(\y -> x * y) 4        (\y -> ...) 4 を評価する
	(x * y)		       (x*y) を評価する
	12
--}

-- 12.4

ones = 1:ones
integers = 1:(map (+ 1) integers)

primes :: [Integer]
primes = sieve [2 ..]
sieve :: [Integer] -> [Integer]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

fibs :: [Integer]
fibs = 0:1: (map (\(x,y) -> x + y) (zip fibs (tail fibs)))

-- 12.5

getFib n = fibs !! n

getFirstFibGreaterThan1000 = head [x | x <- fibs, x > 1000]

-- 12.6
data Tree a = Leaf | Node (Tree a) a (Tree a)
     deriving (Show)

insert x Leaf = Node Leaf x Leaf
insert x (Node l y r) | x < y = Node (insert y r) x l
       	       	      | otherwise = Node (insert x r) y l

x0 = insert 5 Leaf
x1 = insert 7 x0
x2 = insert 3 x1
x3 = insert 9 x2
x4 = insert 2 x3
x5 = insert 11 x4

repeatTree :: a -> Tree a
repeatTree x = Node subtree x subtree where 
	   subtree = repeatTree x

takeTree :: Int -> Tree a -> Tree a
takeTree 0 _ = Leaf
takeTree _ Leaf = Leaf
takeTree n (Node l x r) = Node (takeTree n' l) x (takeTree n' r) where
	 n' = n - 1

replicateTree :: Int -> a -> Tree a
replicateTree n = takeTree n . repeatTree