Haskellのライブラリ関数mapは、
引数に与えられた関数を、リストの要素すべてに対し適用し、リストを返します。
>map (+1) [1,2,3,4]
>[2,3,4,5]
関数mapを、再帰と、foldrを使って再定義してみます。
その前に、関数mapの型定義...
mapの型定義
map :: (a -> b) -> [a] -> [b]
引数を二つとり、リストを返す関数。
その引数は、
”リストの要素一つとり、値を返す関数”を引数1
リストを引数2
...とする関数と定義。
んでは、再帰によるmapの定義へ。
再帰の基底条件
リストの要素に対しての操作なので、リストの要素がなくなることが、再帰の基底条件ですね。
再帰のアイディア
リストの先頭から、関数を適用し、結果をcons. ついで、再帰実施
プログラム
再帰によるmapの定義
my_map :: (a -> b) -> [a] -> [b]
my_map f [] = []
my_map f (x:xs) = f x : my_map f xs
出来まちた。
次に、ライブラリ関数foldrによるmapの定義を実施します。
...の前に、foldrの機能について、さらっと記載します。
foldrの機能
foldrは、リストを”与えられた関数”で右結合し、空リストに、初期値を与えます。
⬇のようなリストを例に取り、foldr (λx accum → x * accum) 1を適用したケースを考えます。
1 : (2 : (3 : (4 : [ ] ) ) )
foldrに与える第一引数は、λ関数 ( x * accum )、第二引数は、初期値 1
この場合、
λ 1 ( λ 2 ( λ 3 ( λ 4 1) ) )と展開され、更に簡約を進めると、
= 1 * (2 * (3 * (4 * 1) ) )
= 24
となります。
これって、再帰で定義した下記の関数productの簡約と同じです。
関数productの再帰的定義
my_product :: (Num a) => [a] -> a
my_product [] = 1
my_product (x:xs) = x * my_product xs
上の関数に、リスト [1, 2, 3, 4]を与えたとき、
= 1 * (2 * (3 * (4 * 1) ) )
= 24
という簡約を得るでしょう。
要は、foldrは、再帰と同じです。
別例として、foldr (λx accum → x + accum) 0を適用した場合、
1 : (2 : (3 : (4 : [ ] ) ) )は、
λ 1 + (λ 2 + (λ 3 + (λ 4 0) ) )と、展開されます。簡約を進めると、
= 1 + (2 + (3 + (4 + 0) ) )
= 10
foldrを使ってmapを実装する
関数mapは、
引数に与えられた関数を、リストの要素すべてに対し適用し、リストを返す機能でした。
リスト要素それぞれに、(+1)を適用するケースで考えると、
>map (+1) [1,2,3,4]
>[2,3,4,5]
これは結局、
1 : (2 : (3 : (4: []) ) )
⬆(上)のリストを、次のリストに変換したいというリクエストに他なりません。
2 : (3 : (4 : (5 : []) )
すると、適用すべきλ式は、
(λx accum -> f x : accum)
ここで、f = (+1)
実際に、λをリストに適用し、簡約を進めると、
λ 1 : (λ 2 :(λ 3: (λ 4 []) ) )
= 2 : (3 : (4 : (5: []) ) )
= (2, 3, 4, 5)
プログラム
以上をまとめて実装すると、こんな感じでmapをfoldrで実現出来ます。
foldrによるmapの定義
foldr_map :: (a -> b) -> [a] -> [b]
foldr_map f xs = foldr (\x accum -> f x : accum) [] xs