プログラミングHaskellを読む(7)

第7章高階関数

基本

高階関数とは: 引数として関数をとったり、関数を返したりする関数。ただし、Haskellではカリー化のため関数を返すのが常なので、明示的に高階関数と呼ぶ場合は、引数として関数を取る関数である事が多い。

twice :: (a -> a) -> a -> a
twice f x = f (f x)

リスト処理

リスト系の高階関数色々。

map' :: (a -> b) -> [a] -> [b]
map' f xs = [f x | x <- xs]

filter' :: (a -> Bool) -> [a] -> [a]
filter' f xs = [x | x <- xs, f x]

あとは練習問題にて。

畳込関数foldr, foldl

関数型言語の醍醐味の畳込関数。

foldr' :: (a -> b -> b) -> b -> [a] -> b
foldr' f v [] = v
foldr' f v (x : xs) = f x (foldr f v xs)

sum' = foldr (+) 0
product' = foldr (*) 1
or' = foldr (||) False
and' = foldr (&&) True

length' = foldr (\_ n -> 1 + n) 0
reverse' = foldr (\x xs = xs ++ [x]) []
combine' xs ys = fildr (:) ys xs

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f v [] = v
foldl' f v (x : xs) = foldl f (f v s) xs

関数合成演算子"."

数学で言う合成関数を作る方法です。

composeWith' :: (b -> c) -> (a -> b) -> (a -> c)
f `composeWith` g = \x -> f (g x)

色々使えます。

odd' = not . even
twice' f = f . f

合成関数の単位元idを使うことでfoldrに適用できる。

id :: a -> a
id = \x -> x

compose :: [a -> a] -> (a -> a)
compose = foldr . id

何もしないidにも、なるほど単位元という意味があったんですね。

文字列の変換器

練習問題にて。

練習問題

1. [f x | x <- xs, p x] をmapとfilterで

comprehension :: (a -> b) -> [a] -> (a -> Bool) -> [b]
comprehension f xs p = map f (filter p xs)

2. all, any, takeWhile, dropWhile

all' :: (a -> Bool) -> [a] -> Bool
all' f xs = length [x | x <- xs, f x] == length xs

all'' :: (a -> Bool) -> [a] -> Bool
all'' f xs = and [f x | x <- xs]

any' :: (a -> Bool) -> [a] -> Bool
any' f xs = length [x | x <- xs, f x] > 0

any'' :: (a -> Bool) -> [a] -> Bool
any'' f xs = or [f x | x <- xs]

takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' _ [] = []
takeWhile' f (x : xs) = if f x then x : (takeWhile' f xs)
                        else []

dropWhile' :: (a -> Bool) -> [a] -> [a]
dropWhile' f xs = reverse (takeWhile' f (reverse xs))

3. map f, filter p

map' :: (a -> b) -> [a] -> [b]
map' f = foldr (\x xs -> (f x) : xs) [] 

filter' :: (a -> Bool) -> [a] -> [a]
filter' f = foldr (\x xs -> if (f x) then x : xs else xs) []

4. dec2int

dec2int :: [Int] -> Int
dec2int xs = foldl (\v x -> v + (fst x)*(snd x)) 0
             (zip xs [10^i | i <- reverse [0..(length xs - 1)]])

ちょと汚いですね。

5. 以下が誤りな理由

sumsqreven = compose [sum, map (^2), filter even]

関数の型が一致していないためリストの部分がエラーになります。

*Main Char> :t sum
sum :: Num a => [a] -> a
*Main Char> :t map (^2)
map (^2) :: Num b => [b] -> [b]
*Main Char> :t filter even
filter even :: Integral a => [a] -> [a]

6. curry, uncurry

curry' :: ((a, b) -> c) -> (a -> b -> c)
curry' f = \x y -> f (x, y) 

uncurry' :: (a -> b -> c) -> ((a, b) -> c)
uncurry' f = \(x, y) -> f x y

7. unfoldによるchop8, map f, iterate f

{- 
p: 終了条件
h: 現時点のxから導き出すべき値を生成
t: xから次にxとして渡す値を生成
-}
unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]
unfold p h t x | p x = []
               | otherwise = h x : unfold p h t (t x)

int2bin' :: Int -> [Bit]
int2bin' = unfold (== 0) (`mod` 2) (`div` 2)

chop8' :: [Bit] -> [[Bit]]
chop8' = unfold null (take 8) (drop 8)

map' :: (a -> b) -> [a] -> [b]
map' f = unfold null (f . head) tail

iterate' :: (a -> a) -> a -> [a]
iterate' f = unfold (\x -> False) f f

8. パリティビット, 9. transmit

まとめてコードを載せます。

import Char

-- 文字列の変換器

type Bit = Int

bin2int :: [Bit] -> Int
{-
bin2int bits = sum [w * b | (w, b) <- zip weights bits]
               where weights = iterate (*2) 1
-}
bin2int = foldr (\x y -> x + 2 * y) 0

int2bin :: Int -> [Bit]
int2bin 0 = []
int2bin n = n `mod` 2 : int2bin (n `div` 2)

make8 :: [Bit] -> [Bit]
make8 bits = take 8 (bits ++ repeat 0)

encode :: String -> [Bit]
encode = concat . map (make8 . int2bin . ord)

chop8 :: [Bit] -> [[Bit]]
chop8 [] = []
chop8 bits = take 8 bits : chop8 (drop 8 bits)

decode :: [Bit] -> String
decode = map (chr . bin2int) . chop8

transmit :: String -> String
transmit = decode . channel . encode

channel :: [Bit] -> [Bit]
channel = id


-- 8の解答 -------------------------------

-- パリティビットの計算
parity :: [Bit] -> Bit
parity bits = foldr (+) 0 bits `mod` 2

-- パリティビットが正しいかチェック
checkParity :: [Bit] -> [Bit]
checkParity xs = if parity (init xs) == (last xs) then xs
                 else error "The parity does not correspond."

-- パリティビットの付加
addParity :: [Bit] -> [Bit]
addParity bits = bits ++ [parity bits]

-- パリティビットの除去
removeParity :: [Bit] -> [Bit]
removeParity = init

chop9 :: [Bit] -> [[Bit]]
chop9 [] = []
chop9 bits = take 9 bits : chop9 (drop 9 bits)

encode' :: String -> [Bit]
encode' = concat . map (addParity . make8 . int2bin . ord)

decode' :: [Bit] -> String
decode' = map (chr . bin2int . removeParity . checkParity) . chop9

-- 9の解答 -------------------------------

-- transmitから考える
transmit' :: String -> String
transmit' = decode' . channel' . encode'

-- 先頭を落とす
channel' :: [Bit] -> [Bit]
channel' = tail
--channel' = id

内容的にはHaskellテクニック集なので、難しくはありませんが、練習問題の分量が結構多くて大変でした。

第7章 高階関数

基本