カリー化関数

カリー化された関数とは、複数の引数を取る代わりに、常に１つの引数を取る関数
Haskellの関数はすべてカリー化されている
カリー化より、関数を本来より少ない引数で呼び出したとき、部分適用されたが得られる

セクション

中置関数に対しても、セクションを使用して部分適用することができる
中置関数をセクションするには片側だけに値を置いて括弧で囲む

10で割る例

divideByTen :: (Floating a) => a -> a
divideByTen = (/10)

大文字か調べる関数の例

isUpperAlphanum :: Char -> Bool
isUpperAlphanum = (`elem` ['A'..'Z'])

高階実演

Haskellでは関数は関数を受け取ることができる
また、関数を戻り値として返すこともできる

関数を受け取り、２回適用する関数の例

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

zipWithの実装

２つのリストを受け取って、２つのリストの各要素にその関数を適用し、１つのリストに結合する関数 zipWith' を実装する。

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

flipの実装

関数を引数にとり、元の関数の最初の２つの引数を入れ替える関数 flip' を実装する。

flip' :: (a -> b -> c) -> (b -> a -> c)
flip' f = g where g x y = f y x

flip'は次のようにも書ける

flip'' :: (a -> b -> c) -> b -> a -> c
flip'' f x y = f y x

関数プログラマの道具箱

map関数

map関数は、関数とリストを受け取り、その関数をリストの全ての要素に適用したリストを返す。

map関数の定義

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

filter関数

filter関数は、述語とリストを受け取り、そのリストの要素のうち、述語を満たすものリストを返す。

filter関数の定義

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
 | p x = x : filter p xs
 | otherwise = filter p xs

コラッツの数列

"１から１００までの数のうち、長さが１５以上のコラッツ列の開始数になるものはいくつあるか？"を解く。

コラッツ数の定義

任意の自然数から開始する
数が１なら終了
数が偶数なら、２で割る
数が奇数なら、３倍して１足す
新しい値で上記を繰り返す

数列を生成する関数 chain

chain Integer -> [Integer]
chain 1 = [1]
chain n
  | even n = n (n `div` 2)
  | otherwise = n : chain (3 * n + 1)

実際に問題を解く関数

numLongChains :: Int
numLongChains length (filter isLong (map chain [1..100]))
  where isLong xs = length xs > 15

ラムダ式

ラムダ式とは一回だけ必要な関数を作るときに使う無名関数
通常、高階関数に渡す関数を作るためだけに使われる

構文

\引数 -> 関数の本体

numLongChainsをラムダ式を使って書き直した例

numLongChains :: Int
numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))

畳み込み

畳み込み（fold）を使うと、データ構造（リストなど）を単一の値にまとめることができる
リストを走査して、何かを返したいときに使用すると便利
畳み込みは２引数関数、初期値（アキュムレータ）、畳み込むリストを受け取る

foldlで左畳み込み

foldl の型 (b -> a -> b) -> b -> [a] -> b

sum 関数

sum' :: (Num a) => [a] -> a
sum' xs = foldl (+) 0 xs

foldrで右畳み込み

foldr の型 (a -> b -> b) -> b -> [a] -> b

map を右畳み込みで実装する例

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

右と左畳み込みの違い

右畳み込みは無限リストに対しても、動作する
左畳み込みは無限リストに対して、動作しない

elem を右畳み込みで実装する例

elem' :: Eq a => a -> [a] -> Bool
elem' y ys = foldr (\x acc -> if x == y then True else acc) False ys

elem' 'a' "bac" => foldr (\x acc -> if x == 'a' then True else acc) False "bac"

foldl1 foldr1

foldl1 はアキュムレータの初期値を先頭の要素とし、左畳み込みを行う
foldr1 はアキュムレータの初期値を末尾の要素とし、右畳み込みを行う

maximum関数はfoldl1を使うと以下のようになる

maximum' :: Ord a => [a] -> a
maximum' = foldl1 max

いくつかの畳み込みの例

畳み込みを使って標準ライブラリの関数を実装する。

reverse

reverse' :: [a] -> [a]
reverse' xs = foldr (\x acc -> x:acc) [] xs

product

product' :: Num a => [a] -> a
product' = foldl (*) 1

filter

filter' :: (a -> Bool) -> [a] -> [a]
filter' p = foldl (\x acc -> if p x then x:acc else acc) []

last

last' :: [a] -> a
last' = foldl1 (\_ x -> x)

スキャン

scanlとscanr関数はfoldlとfoldrのアナロジーで中間状態すべてをリストとして返す。

実行例

scanl (+) 0 [1,2,3] -- 出力：[0,1,3,6]
scanr (+) 0 [1,2,3] -- 出力：[6,5,3,0]

scanlは最終要素に最終結果が入る
scanrは先頭要素に最終結果が入る

自然数の平方根を小さいものから足していったとき、1000を超えるのは何個目か？

{- map sqrt [1..] : 自然数の平方根 -}
length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..])) + 1  -- 出力：131

$を使った関数適用

$の型：($) :: (a -> b) -> a -> b
$の優先順位は最も低い
括弧の数を少なくしたいとき、役にたつ

sum (filter (>10) (map (*2) [2..10]))
sum $ filter (>10) $ map (*2) [2..10] -- $を使うとこのように書ける

$関数は関数適用それ自身を関数として扱えるようにするために使える

map ($ 3) [(4+), (10*), (^2), sqrt]

関数合成

数学の関数合成は (f * g)(x) = f(g(x)) と定義される
Haskellの関数合成も同様に (.) を使って関数合成が定義されている
(.) の型：(b -> c) -> (a -> b) -> a -> c
関数合成は右結合（i.e. f ( g (h x)) は (f . g . h) x）

数のリストに対して、そのリストを負の数にする例

-- 各要素の絶対値をとって、符号反転する
map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24] -- 出力：[-5,-3,-6,-7,-3,-2,-19,-24]
-- 関数合成を使うと、簡潔に書ける
map (negate . abs) [5,-3,-6,7,-3,2,-19,24] -- 出力：[-5,-3,-6,-7,-3,-2,-19,-24]

多引数関数の関数合成

複数の引数をとる関数の合成を考える。

sum (replicate 5 (max 6.7 8.9))
-- 上は次のように書ける
sum . replicate 5 $ max 6.7 8.9

たくさん括弧がある式を関数合成を使って書き直す場合の手順
1. 一番内側の関数とその引数を書き出す
2. $をその前に置く
3. $の前に置かれた関数から最後の引数を取り除く
4. 間にどっとを置いて合成する

replicate 2 (product (map (*3) (zipWith max [1,2] [4,5])))
-- 1,2を適用する
replicate 2 (product (map (*3) $ zipWith max [1,2] [4,5]))
-- 3を適用する
replicate 2 (product . map (*3) $ zipWith max [1,2] [4,5])
-- さらに3を適用する
replicate 2 . product . map (*3) $ zipWith max [1,2] [4,5]

ポイントフリースタイル

ポイントフリースタイルで関数を定義するやり方が、関数合成のもう１つの一般的な使い道（ポイントとは fn x = f (g x) のような関数定義の中で使用する一時変数xのこと）

sum' :: (Num a) => [a] -> a
sum' xs = foldl (+) 0 xs
-- これはポイントフリースタイルで書き直すと次のようになる
sum' = foldl (+) 0

fn x = ceiling (negate (tan (cos (max 50 x))))
-- これをポイントフリースタイルで書き直すと次のようになる
fn = ceiling . negate . tan . cos . max 50

感想

この章は長かった・・・