プログラミング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の関数名がひどすぎてすいません・・・