プログラミングHaskell第2版 5章メモ書き

5章まできました。 リスト内包表記便利。

第5章 リスト内包表記

内包表記

[x^2 | x <- [1..5]]
[1, 4, 9, 16, 25]

-- x ← [1..5]を生成器と呼ぶ。
-- 後方の生成器は、前方の生成器が使う変数を利用できる
[(x, y) | x <- [1..3], y <- [x..3]]
[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

-- 具体例
-- 前方のリストで「リストのリスト」の要素であるリストを1つずつ取り出し、各リストの要素を後方の生成器で1つずつ取り出す
concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

concat [[1, 2, 3], [4, 5]]
[1, 2, 3, 4, 5]

-- ワイルドカードで要素の一部を捨てることもできる
firsts :: [(a, b)] -> [a]
firsts ps = [x | (x, _) <- ps]

-- ワイルドカードの応用
-- `_ <- xs`は1を適切な個数だけ生成するカウンターになっている
length :: [a] -> Int
length xs = sum [1 | _ <- xs]

ガード

前方の生成器で生成された値を間引く方法。ガードでTrueになる値は残され、Falseになる値は捨てられる。

[x | x <- [1..10], even x]
[2, 4, 6, 8, 10]

-- キーと値からなる組のリストの探索
find :: Eq a => a -> [(a, b)] -> [b]
find k t = [v| (k', v) <- t, k == k']

find 'b' [('a', 1), ('b', 2), ('c', 3), ('b', 4)]
[2, 4]

遅延評価

-- 関数positionsは目的に要素のインデックスを返す
-- リスト[0..]は概念上無限だが、遅延評価なのでそれが使われる文脈で必要とされる要素しか生成しない
positions :: Eq a => a -> [a] -> [Int]
positions x xs = [i | (x', i) <- zip xs [0..], x == x']

シーザー暗号

暗号化したいそれぞれの文字を、任意の数だけ後ろの文字に置き換える。

アルファベットの末尾は先頭に接続していると考える。

import Data.Char しておく。

問題を単純にするため、ここでは小文字のみを暗号化することとする。

-- 文字 -> 整数
let2int :: Char -> Int
let2int c = ord c - ord 'a'

-- 整数 -> 文字
int2let :: Int -> Char
int2let n = chr (ord 'a' + n) -- chr 97 #=> 'a'

-- 小文字をシフト数分だけずらす関数shift
-- 正、負両方のシフト数が使える。小文字のみが変化する。
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]

暗号解読

カイ二乗検定で出現する文字の観測頻度と期待頻度を比較する。

算出されたカイ二乗検定の値のリストの中で最小の値の位置をシフト数と考える。

-- 文字の出現頻度表を返す関数
freqs :: Int -> Int -> 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

練習問題の回答はこちら

https://gist.github.com/h-shima/1e6c22c4fa655940009b60b436f0f886