代表的な高階関数5選(Haskell)
この記事では代表的な高階関数を5つご紹介します。関数内部の仕組み・使用例を中心にまとめていきたいと思います。
関数名 | 機能 |
---|---|
filter | リストへ述語関数を適用、Trueになるモノを返却 |
map | リストへ関数を適用する |
zip/zipWith | 複数のリストを1つのリストへまとめる |
foldl/foldr | リストを1つの値へまとめる |
scanl/scanr | foldl/rの途中経過を残すver |
(基本的な高階関数の作り方についてはこちらの記事もご参照下さい。)
(高階関数の読み解き方についてはこちらの記事でまとめています。)
filter関数
リストへ述語関数を適用し、Trueとなるモノを返却します。 述語関数とはTrue/Falseを返却する関数のことです。filter関数を実装したのがこちらです。(a -> Bool)
という型の関数とaのリストを引数として受け取り、aのリストを返却する関数です。
filter' :: (a -> Bool) -> [a] -> [a]
filter' p [] = []
filter' p (x:xs)
| p x = x: filter' xs
| otherwise = filter' f xs
空でないリストの場合、先頭の要素が述語を満たすかどうか?で処理を切り分けています。p x
がTrueに評価されたら、その要素は新しいリストへと含まれます。そして残りの要素xs
が更にfilter'関数へとかけられます。Falseに評価された場合(otherwiseのとき)リストへは含まれません。filter関数の使用例は以下です。
Prelude> filter (<3) [1,2,3,4,5]
[1,2]
Prelude> filter (==3) [1,2,3,4,5]
[3]
map関数
リストへ関数を適用するための関数です。 5つの中で最も使用頻度が高く、またファンクターやモナドを理解するためにも重要な関数です。リストの先頭から1つずつ関数を適用する仕組みとなっています。
map' :: (a -> b) -> [a] -> [a]
map' _ [] = []
map' f (x:xs) = f x : map` f xs
map関数の使用例は以下です。1引数の関数を渡す際には部分適用が効果的です。2引数の関数(+
や++
、*
など)であっても、引数を片方だけ渡せば1引数の関数になります。片方だけ引数を渡して1引数の関数にした後に、map関数へ渡していきましょう。
Prelude> map (+3) [1,2,3]
[4,5,6]
Prelude> map (++ "a") ["a","b","c"]
["aa","ba","ca"]
zip/zipWith関数
2つのリストを受け取って、1つのリストやタプルを作るための関数です。zipWithの方が動きを理解しやすいのでこちらから解説します。
zipwith関数
2つのリストの各要素へ関数を適用し、1つのリストへと結合します。 2引数の関数を渡す必要がある点に注目して下さい。これまでは1引数の関数だったので(+3)
のように片方だけ引数を渡していました。zipWithでは2引数の関数が必要となります。
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
関数の第1引数a
と最初のリスト[a]
が同じデータ型であることに注目して下さい。なぜならリスト[a]
は第1引数として渡す必要があるからです。同じように第2引数b
と2番目のリスト[b]
もデータ型は同じで、関数へ渡される仕組みとなっています。
Prelude> zipWith (+) [1,2,3] [4,5,6]
[5,7,9]
Prelude> zipWith (*) [1,2,3] [4,5]
[4,10]
Prelude> zipWith (++) ["a","b","c"] ["d","e","f"]
["ad","be","cf"]
zip関数
2つのリストを受け取って、タプルのリストを作ります。
zip' :: [a] -> [b] -> [(a,b)]
zip' = zipWith(,)
zip関数を作るには2つの関数が必要となります。zipWith関数と,
関数です。zipWithは2つのリストの各要素へ関数を適用し、1つのリストへ結合する関数でした。2つのリストへ適用する関数として、ここでは,
を部分適用しています。
Prelude> :t (,)
(,) :: a -> b -> (a, b)
,
関数はタプルを作るための関数です。
Prelude> zip [1,2,3] [4,5]
[(1,4),(2,5)]
foldl/foldr関数
リストの要素へ関数を適用しながら1つの値へと変換します。リストの要素を1つの値へとまとめ上げる処理を「畳み込み」とも呼びます。
foldl関数
リストへ左畳み込みを行い、1つの値へと変換する関数です。具体例をお見せします。
Prelude> foldl (+) 0 [1,2,3,4]
10
まず初期値とリストの先頭へ2項関数を適用します。その結果が新しい初期値となり、次のリストの先頭の要素と一緒にまた関数が適用されていきます。初期値、リストの先頭の要素へ関数が適用されていき、リストの要素がなくなるまでこの処理が行われます。図にすると以下のような形です。
関数の型としては以下のように定義されています。2項関数、初期値、リストの3つを引数に取ることがわかります。
Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldlを使えばsum関数を以下のようにカンタンに実装できます。再帰を使うよりもシンプルですよね。
-- foldlを使ったパターン
sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0
-- 再帰を使ったパターン
sum'' :: Num a => [a] -> a
sum'' [] = 0
sum'' (x:xs) = x + (sum'' xs)
foldr関数
リストへ右側から畳み込みを行い、1つの値へと変換する関数です。左と右で順番が違うだけで計算結果が変わることもあります。特に注意したいのが引き算です。
Prelude> foldl (-) 0 [1,2,3,4]
-10
Prelude> foldr (-) 0 [1,2,3,4]
-2
foldrの実装例は以下です。関数(f)、初期値(e)、リスト([])の3つを受け取る関数となっています。
foldr' :: (a -> b -> b) -> b -> [a] -> b
foldr' _ e [] = e
foldr' f e (x:xs) = f x (foldr' f e xs)
空リストの時はそのまま初期値eが返却されます。空リストでない場合、関数で先頭の要素と再帰の結果を畳み込んでいきます。
scanl/scanr関数
foldl/rと同じように初期値とリストへ畳み込みを行います。ただし途中の計算過程も残すのがポイントで、リストからリストを返却する関数となっています。foldl/rの途中の計算過程を残すver..と考えても良いかもしれません。使用例は以下です。scanlとfoldlを比較しながら載せていきます。
Prelude> scanl (+) 0 [1,2,3,4]
[0,1,3,6,10]
Prelude> foldl (+) 0 [1,2,3,4]
10
関数は以下のように定義されています。リストを返却する点に注目して下さい。
Prelude> :t scanl
scanl :: (b -> a -> b) -> b -> [a] -> [b]
Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
scanrはリストの右側から畳み込みを行い、途中の計算過程もリストとして返却します。こちらもfilterrと比較しながら考えます。
Prelude> scanr (-) 0 [1,2,3,4]
[-2,3,-1,4,0]
Prelude> foldr (-) 0 [1,2,3,4]
-2
Discussion