第7章 高階関数 #3

ちょっと寄り道しすぎたかな。

関数合成演算子

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

この演算は結合法則を満たすという。

f . (g . h) = f . (\x -> g (h x))
            = \y -> f ((\x -> g (h x)) y)
            = \y -> f (g (h y))

(f . g) . h = (\x -> f (g x)) . h
            = \y -> (\x -> f (g x)) (h y)
            = \y -> f (g (h y))

というわけで、確かに簡約すれば同じものになった。つまり、f . g . hのように、中かっこを書かなくてもよい。

C#でも関数を2つ引数にとって匿名関数を返すメソッドを書くことはできるけど、演算子として定義することはできない（デリゲートでは演算子をオーバーロードできない）から、中かっこも減らないし、大してうれしくない。（それに、入れ子になったラムダ式を処理系が最適化してくれるはずがないから、処理効率が心配である。）

文字列の変換器

いきなり型の定義（というか、エイリアス？）が出てきたけど、ここでは深く考えないほうがいいんだろうな。

type Bit = Int

そして、標準ライブラリ関数 iterate も出てきた。こっちはちゃんと理解するために、自分で定義しなおしておこう。

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

ライブラリ関数 repeatも出てきたけど、これは前のエントリで自習して知ってるから省略。

以下、なんだか長いが写経する。ここでは数値の2進表記は逆順に書かれていることに注意。

import Data.Char

type Bit = Int

-- 教科書では、まずsumとiterateを使ってbin2intを定義して、
-- bin2int bits = sum [w * b | (w, b) <- zip weights bits]
--                where weights = iterate (*2) 1
-- それからfoldrを使って書きなおしている。
-- 確かに、sumは集約関数なんだから、foldrで書き直せることは道理だ。
bin2int :: [Bit] -> Bit
bin2int = foldr (\x y -> x + 2 * y) 0

-- そうであるなら、int2binはunfoldで書けるはず。
-- 教科書にはまだunfoldは出てきてないけどね。;-)
int2bin :: Bit -> [Bit]
int2bin 0 = []
int2bin n = n `mod` 2 : int2bin (n `div` 2)

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

-- 文字列をビットストリームに変換する
encode :: String -> [Bit]
encode = concat . map (make8 . int2bin . ord)

-- 8bitごと分解してリスト化する
chop8 :: [Bit] -> [ [Bit] ]
chop8 [] = []
chop8 bits = take 8 bits : chop8 (drop 8 bits)

-- ビットストリームを文字列に変換する
decode :: [Bit] -> String
decode = map (chr . bin2int) . chop8

-- 通信路をモデル化する
channel :: [Bit] -> [Bit]
channel = id

-- 通信をシミュレートする
transmit :: String -> String
transmit = decode . channel . encode

練習問題

問題1

-- question1 f p xs = [f x | x <- xs, p x]
question1 f p xs = ((map f) . (filter p)) xs

問題2

問題4の後で、2引数のラムダ式に書きなおした。2引数のラムダ式の方が理解しやすいと思う。

all' :: (a -> Bool) -> [a] -> Bool
-- all' p = foldr ((&&) . p) True
all' p = foldr (\x y -> p x && y) True

any' :: (a -> Bool) -> [a] -> Bool
-- any' p = foldr ((||) . p) False
any' p = foldr (\x y -> p x || y) False

takeWhile' :: (a -> Bool) -> [a] -> [a]
-- takeWhile' p = foldr (\x -> if p x then (x:) else const []) []
takeWhile' p = foldr (\x y -> if p x then x : y else []) []

dropWhile' :: (a -> Bool) -> [a] -> [a]
-- dropWhile' p = foldr (\x -> if p x then id else (x:)) []
dropWhile' p = foldr (\x y -> if p x then y else x : y) []

takeWhileとdropWhileについては、最初はガードを使った場合分けを考えていたので、foldrを使うより再帰のほうが簡潔かなと思っていた。 問題3を解いているときに「if-then-elseなら1行で書ける！」と気づいたので書きなおしたのだが、その時はなぜか1引数のラムダ式で書いていた。そのせいでconstやidを使うはめになっている。

問題3

問題4の後で、2引数のラムダ式に書きなおした。2引数のラムダ式の方が理解しやすいと思う。

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

filter' :: (a -> Bool) -> [a] -> [a]
-- filter' p = foldr (\x -> if p x then (x:) else id) []
filter' p = foldr (\x y -> if p x then x : y else y) []

問題4

dec2int :: [Int] -> Int
dec2int = foldl (\x y -> x * 10 + y) 0

解きながら「文字列の変換器」を読み返して反省した。foldrやfoldlにラムダ式を食わせるときは、2引数のラムダ式のほうが見やすい。 というわけで、練習問題の回答をさかのぼって修正した。

問題5

たぶん型があわないんじゃないかなと予想して、Hugsで型を見てみる。

filter even :: Integral a => [a] -> [a]
map (^2) :: (Num a, Integral b) => [a] -> [a]
sum :: Num a => [a] -> a

あれ。整数クラスに適用する分には問題なさそうだけど……と思ったが、ここで、composeは標準ライブラリ関数ではなかったことに気づき、教科書を読み返した。

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

ここで目から鱗。そうか、リスト内の関数はすべて同じ型じゃないといけないんだな。

sum . map (^2) . filter even

という関数合成には問題ないけど、sumだけ型が違うからリストには入らない。把握した。

問題6

ん？2つ組のタプルだけでいいの？

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