top page > computer > haskell > web_lecture > for_programmer > dropwhile_foldr.html
更新日:
文責: 重城良国

関数foldrで関数dropWhileを定義

ウォームアップ

関数dropWhileの関数foldrによる定義がすこし難しいので。

[x1, x2, x3, ...]の先頭の連続する偶数を落とす関数fun1があったとする。それでは[x, x1, x2, x3, ...]の先頭の連続する偶数を落とす関数fun2はfun1で表現できるだろうか。これは不可能だ。x1, x2, x3が偶数だったとき関数fun1はそれらを落としてしまう。しかしxが奇数だったとき関数fun2の結果にはそれらが含まれる。fun1にBool値の引数を追加してそれがTrueのときのみ先頭の連続する偶数を落とすようにすれば良い。そうすればfun2はxが奇数だったならfun1にFalseを与えて呼び出せば良いことになる。

[4, 8, 2, 3, 6, 5, 4, 4]に対して上記のことを行う関数fun1は以下のようになる。

% ghci
Prelude> let fun1 b = if b then [3, 6, 5, 4, 4] else [4, 8, 2, 3, 6, 5, 4, 4]

xが奇数のときfun2はどう表されるだろうか。xが偶数のときはどうだろうか。x = 4の場合とx = 9の場合でそれぞれfun1を使ってfun2を表現してみよう。ちなみに説明の都合上fun2と書いているがこの段階ではfun2は単なるリストだ。

次にfun2がさらにfun3から使われることを考えてfun2もBool値をとるようにする。x = 4の場合とx = 9の場合とでそれぞれ書いてみよう。

引数xをとりfun1をfun2に変換する関数convを書いてみよう。let conv x f = ...のように定義する。これを使ってconv x fun1がfun2になることを確認しよう。

できたらとりあえず一度これらについては忘れてしまおう。

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

定義

foldrを使うためには「条件を満たさないものがまだない」ということを示すフラグが必要になる。

step x f True
| p x = f True
| otherwise = x : f False
step x f False = x : f False

dropWhileB p (x : xs) b = step x (dropWhileB p xs) b
dropWhileB _ _ _ = []

step x (dropWhileB p xs) bを展開してみる。

dropWhileB p (x : xs) True
| p x = dropWhileB p xs True
| otherwise = x : dropWhileB p xs False
dropWhileB p (x : xs) False = x : dropWhileB p xs False
dropWhileB _ _ _ = []

まずは展開前と展開後のコードをよく見くらべてみよう。同じであることがわかるだろうか。次に展開後のコードの動きを追ってみよう。値xが条件pを満たさなくなったあとは第3引数のBool値はずっとFalseのままになる。うえのコードの仮引数bを消す。

dropWhileB p (x : xs) = step x (dropWhileB p xs)
dropWhileB _ _ = const []

foldrで表現できる。

dropWhileB p = foldr step (const [])

フラグの初期値としてTrueを与える。

dropWhileF p = foldr step (const []) True

ローカル関数で書き直す。

dropWhileF p xs = foldr s (const []) xs True
where
s x f True
| p x = f True
| otherwise = x : f False
s x f False = x : f False

「関数foldrで関数splitAtを定義」へもどる 「関数foldrで関数spanを定義」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics