読者です 読者をやめる 読者になる 読者になる

チューリング不完全

What are you afraid of? All you have to do is try.

プログラミング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.
-- ???