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

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

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。ときどきごっちゃになんねん」 「（PythonやClojureの）reduceはfoldlです」

エスカレーターとエレベーター　……ちょっと時々ごっちゃになるねん

— 春日歩(大阪) (@osakabot) 2017年4月5日

とにかくややこしい。

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

になる。

foldrでfilter

まず、より簡単なfilterをfoldrで定義してみる：

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を満たしていたか」も判断基準になってくるから。

foldrとreverseでdropWhile

ということで、一番簡単な解決法は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や無限リストなどは扱えなくなってしまう。

foldrでdropWhile

というわけで本命：

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を起こしてうまくいかない。なんとなく直観的にはわかるのだが説明はできない・・・