foldr-map

Haskellのライブラリ関数mapは、

引数に与えられた関数を、リストの要素すべてに対し適用し、リストを返します。

>map (+1) [1,2,3,4]

>[2,3,4,5]

関数mapを、再帰と、foldrを使って再定義してみます。

その前に、関数mapの型定義...

mapの型定義

map :: (a -> b) -> [a] -> [b]

引数を二つとり、リストを返す関数。

その引数は、

”リストの要素一つとり、値を返す関数”を引数１

リストを引数２

...とする関数と定義。

んでは、再帰による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