# \$ cat /var/log/shin

### 第7章 高階関数

#### 基本

```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 :: a -> a
id = \x -> x

compose :: [a -> a] -> (a -> a)
compose = foldr . 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 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
```