foldr-filter

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

引数に与えられた述語を、リストの要素すべてに対し適用し、”真”と判定された要素で

リストを作成します。

>filter (even) [1,2,3,4]

>[2,4]

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

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

filterの型定義

filter :: (a -> Bool) -> [a] -> [a]

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

その引数は、

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

リストを引数２

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

んでは、再帰によるfilterの定義へ。

再帰の基底条件

リストの要素に対しての操作なので、リストの要素がなくなることが、再帰の基底条件ですね。

再帰のアイディア

リストの先頭から、述語を適用し、真判定された場合のみ、リスト要素をcons. ついで、再帰実施

プログラム

再帰によるfilterの定義

my_filter :: (a -> Bool) -> [a] -> [a]

my_filter p [] = []

my_filter p (x:xs)

| p x = x : my_filter p xs

| otherwise = my_filter p xs

出来まちた。

次に、ライブラリ関数foldrによるfilterの定義を実施します。

foldrを使ってfilterを実装する

関数filterは、

引数に与えられた述語を、リストの要素すべてに対し適用し、

”真”と判定された要素でリストを作成する機能を持つのでした。

リスト要素それぞれに、述語(even)を適用するケースで考えると、

>filter (even) [1,2,3,4]

>[2,4]

これは結局、

1 : (2 : (3 : (4: [] ) ) )

⬆（上）のリストを、次のリストに変換したいというリクエストに他なりません。

2 : (4: [] )

すると、適用すべきλ式は、

(\x accum -> if p x then x : accum else accum)

ここで、p = (even)

実際に、λをリストに適用し、簡約を進めると、

λ 1 : (λ 2 :(λ 3: (λ 4 []) ) )

= 2 : (4 : [] )

= (2, 4)

プログラム

以上をまとめて実装すると、こんな感じでfilterをfoldrで実現出来ます。

foldrによるfilterの定義

foldr_filter :: (a -> Bool) -> [a] -> [a]

foldr_filter f xs = foldr (\x accum -> if f x then x : accum else accum) [] xs