プログラミング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. -- ???
プログラミングHaskell 5章
リスト内包表記はMathematicaで慣れてるのでサクサク通過。
-- 5. リスト内包表記 import Data.Char(isLower, isUpper, ord, chr) -- 5.1 生成器 concat :: [[a]] -> [a] concat xss = [x | xs <- xss, x <- xs] firsts :: [(a,b)] -> [a] firsts ps = [x | (x,_)<-ps] -- in Prelude.hs -- length :: [a] -> Int -- length xs = sum [1| _ <- xs ] -- 5.2 ガード -- 正の整数に対し、すべての約数を計算する factors :: Int -> [Int] factors n = [ x | x <- [1..n], n`mod`x==0 ] -- 整数が素数か否かを判定する prime :: Int -> Bool prime n = factors n == [1,n] -- 与えられた上限までの素数全てを生成する primes :: Int -> [Int] primes n = [ x | x<-[2..n], prime x] find :: Eq a => a -> [(a,b)] -> [b] find k t = [ v | (k',v)<-t, k == k'] -- 5.3 関数zip -- リストから隣り合う要素を組にして、リストとして返す pairs :: [a] -> [(a,a)] pairs xs = zip xs (tail xs) -- 順序クラスに属する任意の型の要素を持つリストが、 -- 整列されているか調べる sorted :: Ord a => [a] -> Bool sorted xs = and [x<=y | (x,y)<- pairs xs] -- 目的とする値がリストのどの位置にあるかを調べて、 -- その位置すべてをリストとして返す positions :: Eq a => a->[a]->[Int] positions x xs = [ i | (x',i)<-zip xs[0..n], x==x'] where n = length xs - 1 -- 5.4 文字列の内包表記 -- 小文字の個数を数える lowers :: String -> Int lowers xs = length [ x | x<-xs, isLower x] -- 特定の文字の個数を数える count :: Char -> String -> Int count x xs = length [ x' | x' <- xs, x==x' ] -- 5.5 シーザー暗号 -- 小文字を0から25の整数に変換する let2int :: Char->Int let2int c = ord c - ord 'a' -- let2intの逆関数 int2let :: Int->Char int2let n = chr(ord 'a' + n) -- 小文字をシフト数だけずらす shift :: Int -> Char -> Char shift n c | isLower c = int2let((let2int c + n) `mod` 26) | otherwise = c -- 与えられたシフト数で文字列を暗号化する encode :: Int -> String -> String encode n xs = [shift n x | x<-xs] table :: [Float] table = [8.2,1.5,2.8,4.3,12.7,2.2,2.0,6.1,7.0,0.2,0.8,4.0,2.4, 6.7,7.5,1.9,0.1,6.0,6.3,9.1,2.8,1.0,2.4,0.2,2.0,0.1] percent :: Int -> Int -> Float percent n m = (fromIntegral n / fromIntegral m)*100 -- 任意の文字列に対して文字の出現頻度表を返す freqs :: String -> [Float] freqs xs= [percent (count x xs) n | x <- ['a'..'z']] where n = lowers xs -- カイ二乗検定 chisqr :: [Float] -> [Float] -> Float chisqr os es = sum [((o-e)^2) / e | (o,e)<-zip os es] -- リストの要素をnだけ左に回転させる rotate :: Int -> [a] -> [a] rotate n xs = drop n xs ++ take n xs crack :: String -> String crack xs = encode (-factor) xs where factor = head (positions (minimum chitab) chitab) chitab = [chisqr (rotate n table') table | n<-[0..25] ] table' = freqs xs
Exercise
1.
リスト内包表記を使って、
1から100までの二乗の和 1^2 + 2^2 + ... + 100^2 を計算する式を考えよ。
sum [x^2 | x<-[1..100]]
2.
関数lengthと同じように、ある要素のみからなるリストを生成するライブラリ関数
replicate :: Int -> a -> [a] をリスト内包表記を用いて定義せよ。
replicate :: Int -> a -> [a] replicate n a = [a | x<-[1..n]]
3.
x^2+y^2=z^2 を満たす正の整数をピタゴラス数と予備、3つ組(x,y,z)で表す。
ピタゴラス数のリストを生成する関数
pyths :: Int -> [(Int,Int,Int)]をリスト内包表記を使って定義せよ。
ただし、ピタゴラス数の要素は、与えられた上限以下であるとする。
pyths :: Int -> [(Int,Int,Int)] pyths n = [(x,y,z) | x<-[1..n], y<-[1..n], z<-[1..n], x^2+y^2==z^2]
4.
自分自身を除く約数の和が自分自身と等しいとき、その整数を完全数と呼ぶ。
与えられた上限までに含まれる完全数すべてを算出する関数
perfects :: Int -> [Int] をリスト内包表記と関数factorsを使って定義せよ。
perfects :: Int -> [Int] perfects n = [ x | x<-[1..n], x == (sum (factors x))-x]
5.
2つの生成器を持つリスト内包表記
[(x,y) | x<-[1,2,3], y<-[4,5,6]]
は、1つの生成器を持つリスト内包表記2つでも表現できることを示せ。
ヒント: 一方のリスト内包表記を他方への中に入れ、またライブラリ関数concatも使え。
Main.concat [[(x,y) | y<-[4..6]] | x<-[1..3]]
6.
関数positions を関数findを使って再定義せよ。
positions2 :: Eq a => a->[a]->[Int] positions2 x xs = find x [(a,b) | (a,b) <- zip xs [0..n]] where n = length xs - 1
7.
長さがnである整数のリストxsとysの内積は、対応する要素の積の和として計算できる。
関数chisqrと同様に、2つのリストから内積を計算する関数
scalarproduct::[Int] -> [Int] -> Int
をリスト内包表記を使って定義できることを示せ。
scalarproduct :: [Int] -> [Int] -> Int scalarproduct xs ys = sum [x*y | (x,y)<- zip xs ys]
8.
シーザー暗号のプログラムを大文字も扱えるように変更せよ。
uppers :: String -> Int uppers xs = length [ x | x<-xs, isUpper x] let2intUpper :: Char->Int let2intUpper c = ord c - ord 'A' int2letUpper :: Int->Char int2letUpper n = chr(ord 'A'+n) shift2 :: Int -> Char -> Char shift2 n c | isLower c = int2let((let2int c + n) `mod` 26) | isUpper c = int2letUpper((let2intUpper c + n) `mod` 26) | otherwise = c encode2 :: Int -> String -> String encode2 n xs = [shift2 n x | x<-xs] freqs2 :: String -> [Float] freqs2 xs= [percent (count x xs + count y xs) n | (x,y) <- zip ['a'..'z'] ['A'..'Z']] where n = lowers xs + uppers xs crack2 :: String -> String crack2 xs = encode2 (-factor) xs where factor = head (positions (minimum chitab) chitab) chitab = [chisqr (rotate n table') table | n<-[0..25] ] table' = freqs2 xs
問8の関数名がひどすぎてすいません・・・
