プログラミングHaskell 6章
演習問題の6だけ「?」が残りました。foldrとか使うんだと思うんだけど・・・
どうやったら簡略化できるんだろ？
-- 6. 再帰関数 -- 6.1 基本概念 factorial :: Int->Int -- factorial n = product [1..n] factorial 0 = 1 factorial n = n * factorial (n-1) -- (*) :: Int -> Int -> Int -- m * 0 = 0 -- m * n = m + (m*(n-1)) -- 6.2 リストに対する再帰 -- product :: Num a => [a] -> a -- product [] = 1 -- product (n:ns) = n * product ns -- length :: [a] -> Int -- length [] = 0 -- length (_:xs) = 1 + length xs -- reverse :: [a] -> [a] -- reverse [] = [] -- reverse (x:xs) = reverse xs ++ [x] -- (++) :: [a] -> [a] -> [a] -- [] ++ ys = ys -- (x:xs) ++ ys = x:(xs ++ ys) insert :: Ord a => a -> [a] -> [a] insert x [] = [x] insert x (y:ys) | x <= y = x:y:ys | otherwise = y:insert x ys -- insertion sort isort :: Ord a => [a] -> [a] isort [] = [] isort (x:xs) = insert x (isort xs) -- 6.3 複数の引数 -- zip :: [a] -> [b] -> [(a,b)] -- zip [] _ = [] -- zip _ [] = [] -- zip (x:xs) (y:ys) = (x,y) : zip xs ys -- drop :: Int -> [a] -> [a] -- drop 0 xs = xs -- drop n [] = [] -- drop n (_:xs) = drop (n-1) xs -- 6.4 多重再帰 fibonacci :: Int -> Int fibonacci 0 = 0 fibonacci 1 = 1 fibonacci n = fibonacci (n-2) + fibonacci (n-1) -- quick sort qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger where smaller = [ a | a<-xs, a<=x ] larger = [ b | b<-xs, b>x ] -- 6.5 相互再帰 -- even :: Int -> Bool -- even 0 = True -- even n = odd n-1 -- odd :: Int -> Bool -- odd 0 = False -- odd n = even n-1 -- リストから偶数の位置の要素を取り出す evens :: [a] -> [a] evens [] = [] evens (x:xs) = x:odds xs -- リストから奇数の位置の要素を取り出す odds :: [a] -> [a] odds [] = [] odds (_:xs) = evens xs
exercise
1.
乗算演算子 * の再帰を参考にして、負でない整数に対する累乗演算子 ^ を定義せよ。
また、その定義を使って、2^3を簡約せよ。
(^) = Int -> Int -> Int m ^ 0 = 1 m ^ n = m * (m ^ (n-1)) 2^3 = 2 * (2^2) = 2 * (2 * (2^1)) = 2 * (2 * (2 * (2^0))) = 2 * (2 * (2 * (1))) = 8
2.
この章で与えた定義を使って、length [1,2,3], drop 3 [1,2,3,4,5],
およびinit[1,2,3]を簡約せよ。
length [1,2,3] = 1 + length [2,3] = 1 + (1 + length [3]) = 1 + (1 + (1 + length []) = 1 + (1 + (1 + 0)) = 3 drop 3 [1,2,3,4,5] = drop 2 [2,3,4,5] = drop 1 [3,4,5] = drop 0 [4,5] = [4,5] init [1,2,3] = 1 : init [2,3] = 1 : (2 : init [3]) = 1 : (2 : []) = [1,2]
3.
標準ライブラリを見ないで、以下のライブラリ関数を再起を使って定義せよ。
and :: [Bool] -> Bool and [x] = x and (x:xs) = x && and xs concat :: [[a]] -> [a] concat [] = [] concat (x:xs) = x ++ concat xs replicate :: Int -> a -> [a] replicate 0 x = [] replicate n x = x : replicate2 (n-1) x (!!) :: [a] -> Int -> a (x:xs) !! 0 = x (x:xs) !! n = xs !! (n-1) elem :: Eq a => a -> [a] -> Bool elem a [] = False elem a (x:xs) = a==x || elem a xs
4.
関数 merge :: Ord a => [a] -> [a] -> [a]は、整列された2つのリストを2つとり、
1つの整列されたリストにして返す関数である。
関数 merge を再帰を用いて定義せよ。
ただし、関数 insertやisortなど、整列されたリストを処理する関数は利用してはならない。
merge :: Ord a => [a] -> [a] -> [a] merge [] [] = [] merge (x:xs) [] = x : merge xs [] merge [] (y:ys) = y : merge [] ys merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys
5.
関数 merge を使って、マージソートを実行する関数
msort :: Ord a => [a] -> [a]
を再帰を用いて定義せよ。
マージソートは、引数のリストを2つに分割し、それぞれを整列した後、再び1つに戻すことで、
整列を実現する。
ただし、空リストと要素が1つのリストは、すでに整列されていると考える。
ヒント: 最初に、リストを半分に分割する関数 halve:: [a] -> ([a],[a])を定義せよ。
生成された2つのリストの長さは、高々1しか違わない。
halve :: [a] -> ([a], [a]) halve xs = (take n xs, drop n xs) where n = (length xs) `div` 2 msort :: Ord a => [a] -> [a] msort [] = [] msort (x:[]) = [x] msort xs = merge (msort a) (msort b) where (a,b) = halve xs
6.
五段階の工程を使って、以下のライブラリ関数を定義せよ。
数値のリストに対し要素の和を計算する関数sum
リストの先頭からn個の要素を取り出す関数take
空でないリストの末尾の要素を取り出す関数last
-- sum/1. sum :: (Num a) => [a] -> a -- sum/2. sum [] = sum (x:xs) = -- sum/3. sum [] = 0 sum (x:xs) = -- sum/4. sum [] = 0 sum (x:xs) = x + sum xs -- sum/5. sum = foldl (+) 0 -- take/1. take :: Int -> [a] -> [a] -- take/2. take 0 (x:xs) = take n (x:xs) = -- take/3. take 0 (x:xs) = [] take n (x:xs) = -- take/4. take 0 (x:xs) = [] take n (x:xs) = x : take (n-1) xs -- take/5. -- 一般化・・・？ -- last/1. last :: [a] -> a -- last/2. last (x:[]) = last (x:xs) = -- last/3. last (x:[]) = x last (x:xs) = -- last/4. last (x:[]) = x last (x:xs) = last xs -- last/5. -- ???
