Haskellのライブラリ関数filterは、
引数に与えられた述語を、リストの要素すべてに対し適用し、”真”と判定された要素で
リストを作成します。
>filter (even) [1,2,3,4]
>[2,4]
関数filterを、再帰と、foldrを使って再定義してみます。
その前に、関数filterの型定義...
filterの型定義
filter :: (a -> Bool) -> [a] -> [a]
引数を二つとり、リストを返す関数。
その引数は、
”リストの要素一つとり、Bool値を返す関数”を引数1
リストを引数2
...とする関数と定義。
んでは、再帰による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