Arantium Maestum

プログラミング、囲碁、読書の話題

`foldr`を使って`dropWhile`を定義する

Haskell高階関数foldrdropWhileを定義せよ、という問題を見たのでやってみる。

foldr

foldrの定義は以下のとおり:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f e [] = e
foldr f e (x:xs) = f x (foldr f e xs)

「わかってるねんで?foldrがreduce、foldlがfold。ときどきごっちゃになんねん」 「(PythonClojureの)reduceはfoldlです」

とにかくややこしい。

foldr (+) 0 [1, 2, 3] = 1 + (2 + (3 + 0)))
foldl (+) 0 [1, 2, 3] = ((0 + 1) + 2) + 3

でどっちにベースの要素eがつくかでleft/rightを判断するのがよさそう。

dropWhile

dropWhile高階関数を使わずに定義するなら:

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p [] = []
dropWhile p ys@(x:xs) = if p x then dropWhile p xs else ys

になる。

foldrfilter

まず、より簡単なfilterfoldrで定義してみる:

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr f []
  where f x xs = if p x then (x:xs) else xs

filterがなぜ簡単かというと、xを含むかどうかはp xの結果のみで決定できるからだ。

逆に言うとdropWhileが複雑なのはp xだけでなく、「以前の要素がpを満たしていたか」も判断基準になってくるから。

foldrreversedropWhile

ということで、一番簡単な解決法はreverseを使ってリストを逆転させてしまうこと。

dropWhile p = reverse . foldr f [] . reverse
  where f x xs = if p x && (null xs) then xs else x:xs

これでfoldr f e (x:xs)の結果を返す時、foldr f e xsの結果を判断材料にできる。

しかし問題も大きい。そもそもO(n)の処理を三回やっているし、さらに重要なのは遅延評価の強みを消してしまっていること。dropWhileの第一要素を計算するためにリストすべてをいったん調べなければいけない。とくにundefinedが含まれるpartial listや無限リストなどは扱えなくなってしまう。

foldrdropWhile

というわけで本命:

dropWhile p = fst . foldr f ([], [])
  where f x xst = case p x of
                    True -> (fst xst, ys)
                    False -> (ys, ys)
                  where ys = x : snd xst

foldrなのでリストの右側から考えて

  • 今後左側の要素がすべてpを満たした場合
  • 左側にpを満たさない要素があった場合

の結果リストをタプルで持っている。

これで

Prelude> take 5 $ dropWhile even ([2, 4, 6, 7, 8] ++ [1..])
[7,8,1,2,3]

のように無限リストにも対応出来る。

パターンマッチによる失敗例

ちなみにこれは:

dropWhile p = fst . foldr f ([], [])
  where f x (a, b) = case p x of
                      True -> (a, c)
                      False -> (c, c)
                    where c = x : b

としてしまうと無限リストなどの場合stack overflowを起こしてうまくいかない。なんとなく直観的にはわかるのだが説明はできない・・・