7.8 (1) [f x|x <- xs, p x]をmapとfilterを使って書き直すとどうなるか？

a'::[Int]
a' = map f (filter p xs)
  where
    xs = [1,3..50]
    f  = (*2)
    p  = (<18)

まあ、これはいいかな。

7.8 (2) 標準ライブラリの定義をみないでall,any,takeWhile,dropwhileを定義せよ

-- all
all' :: (a -> Bool) -> [a] -> Bool
all' f [] = True
all' f (x:xs) = if f x then all' f xs else False

--any
any' :: (a -> Bool) -> [a] -> Bool
any' f [] = False
any' f (x:xs) = if f x then True else any' f xs

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

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

最初は少し迷いました。最初に考えたallは、

-- my first code
all' ::Eq a => (a -> Bool) -> [a] -> Bool
all' f xs = if xs == fxs then True else False
         where fxs = [x|x<-xs,f x]

これでも同じ結果にはなると思うのですが、この章のテーマが高階関数なのでこれではダメだと思い直して先の解答にしました。この解答ではリストの要素すべてを評価するので効率の面から言ってもNGでしょう。というか、模範解答は

all p = and . map p
any p = or . map p

ですからそもそもダメだめなんですが...後、takeWhile/dropWhileも模範解答はガードで書いてますね。相変わらずif/else体質です。Haskellではif文は推奨されないのかな？

7.8 (3) foldrを使ってmap f,filter pを定義せよ。

-- foldr :: (a -> b -> b) -> b -> [a] -> b
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) []

これはかなり時間がかかりfoldrの定義とにらめっこで作成しました。最初の解答は恥ずかしながら、

map' f = foldr f []

テキストの二項演算子を使った例に気を取られて演算子の部分をそのままfに置き換えただけの思考停止状態。lengthをfoldlで定義している例を思い出してようやくfoldrの最初の引数、(a -> b -> b)の部分をラムダ式で書けばいいと気がつきました。

7.8 (4) foldlを用いてdec2int::[Int] -> [Int]を定義せよ

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

これは本文中にbin2intの例があったのでなんとかできましたが、p84あたりの重み付けをくくりだしていくやり方など僕には絶対に思いつきそうにもありませんね。普通に再帰で定義するところまでが限界かも。実際、わざわざ以下のような再帰の定義を考えてそれをfoldlで書き直そうとしたものだから全然うまくいかず苦労しました。

dec2int ::[Int] -> Int
dec2int [] = 0
dec2int (x:xs) = (10^(length xs)*x + dec2int xs

それにしても、"foldl (\y x -> 10*y + x)"って、y,xって反対に書いているあたりかなり理解が怪しい節もありますねぇ。

7.8 (5) compose [sum, map (^2), filter even]の誤りを指摘せよ

sum関数とmap,filter関数の単位元が異なるため。次のようにすればOK

compose' ::[a->a] -> (a->a)
compose' = foldr (.) id
sumsqeven = sum . (compose' [map (^2),filter even] )

7.8 (6) 次の高階関数を定義せよ

7.8 (6.1) 引数を組に取る関数をカリー化された関数へ変換するcurry

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

7.8 (6.2) カリー化された関数を引数を組に取る関数へ変換するuncurry

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

curry'ができたらuncurry'もできました。ヒントにあるとおり、まず型を考えるのがHaskellでは王道なのかも。

7.8 (7) unfoldを用いて、関数chop8,map f,iterate fを再定義せよ

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

map1 :: (a -> b) -> [a] -> [b]
map1 f = unfold (null) (\(x:xs) -> f x) (\(x:xs) -> xs)

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

mapとiterateの模範解答は

map f = unfold null ( f . head ) tail
iterate f = unfold (const False) id f

僕は、バ○みたいに垂れ流して書いてしまいましたが、模範解答はいづれも簡潔です。const Falseはともかく、idはスッっと出てくるようになりたいものです。

7.8 (8( パリティビットを用いて軽度の通信エラーを検出できるよう変更せよ

まず、encode時にパリティビットを付加するためmake9を作成しencode処理を修正します。ビット列の合計が奇数かどうかで判定しています。

make9 :: [Bit] -> [Bit]
make9 bits = (make8 bits) ++ p
      where p = if (odd . sum) bits then [1] else [0]

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

次にデコードの時に付加したパリティビットを削除するremovep関数を定義し、decode関数を修正します。また、ビット列を9ビットにするchop9関数も作成します。

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

removep :: [[Bit]] -> [[Bit]]
removep = foldr (\x xs -> pchk x : xs) []

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

パリティビットを落とすremovep関数ではパリティビットチェックするpchk関数を呼び出します。pchkでエラーを検知したらあればその旨を通知するそこで終了となります。

pchk :: [Bit] -> [Bit]
pchk bits | (even.sum) bits = init bits
          | otherwise       = error "prity bit check error"

ここのremovep/pchkの実装は結構悩みました。最初はうまく畳み込むコードが書けず、

isErr :: [Bit] -> Bool
isErr bits | last bits == 1 = (even.sum.init) bits
           | otherwise      = (odd.sum.init)  bits

removep [] = []
removep (x:xs) = if isErr x 
                  then error "parity check failed"
                  else init x : removep xs

としていました。もちろん、七章のお題でもあるのでたたみ込みした方がいいのはわかっていたのですがfold(l|r)はまだいきなり書けません。とりあえず、上記のように愚直に書いてから変換していかないと思考がついて行かないです。

模範解答はパリティを先頭につけています。パリティチェックもズバっとそのビットを比較していて無駄がない。僕はというとsumしてevenとは...ダメダメです(;_;)