`foldr`で`dropWhile`と不動点コンビネータ 補足
以下の記事の補足:
式をいじっていて気付いたのだが、不動点コンビネータを使った解は:
dropWhile p = foldr (const f) undefined (repeat undefined) where f _ [] = [] f g ys@(x:xs) = if p x then g xs else ys
に落とし込める。(fix
とdropWhileNR
関数を別にしていたから当初気付かなかった)
これはそもそも別解の:
dropWhile p xs = foldr f id xs xs where f x g ys@(_:zs) | p x = g zs | otherwise = ys
から式変形で導出できる。x
とys
の最初の要素が同一なので:
dropWhile p xs = foldr f id xs xs where f _ g ys@(z:zs) | p z = g zs | otherwise = ys
あるいはif
を使って:
dropWhile p xs = foldr f id xs xs where f _ g ys@(z:zs) = if p z then g zs else ys
に変形できる。そうすると、foldrの第三引数になっているxs
の要素はDon't Careパターンに適用されるだけなのでrepeat undefined
で代用できそう:
dropWhile p xs = foldr f id (repeat undefined) xs where f _ g ys@(z:zs) = if p z then g zs else ys
上記のコードには問題があって、dropWhile (<5) [1..4]
などでエラーを起こす。
実はfoldr
の第三引数のxs
は、要素は使われなかったがリスト自体の長さは「いつ第二引数のid
を返すか」を判定するのに使われていた。具体的にはxs
が空リストになった時にid
を返す。
なので明示的にその停止条件を入れる:
dropWhile p xs = foldr f id (repeat undefined) xs where f _ _ [] = [] f _ g ys@(z:zs) = if p z then g zs else ys
これはf _ _ [] = id []
と同じ。foldr
の第二引数も使わないのでundefined
で代用できる:
dropWhile p xs = foldr f undefined (repeat undefined) xs where f _ _ [] = [] f _ g ys@(z:zs) = if p z then g zs else ys
そしてdropWhile p xs = foldr f undefined (repeat undefined) xs
のxs
も、それ以降の定義ではまったく使われないので両辺から消してしまう:
dropWhile p = foldr f undefined (repeat undefined) where f _ _ [] = [] f _ g ys@(z:zs) = if p z then g zs else ys
f _
は(const f)
と同義だ。f
の第一引数は必ずDon't Careパターンで無視されているので:
dropWhile p = foldr (const f) undefined (repeat undefined) where f _ [] = [] f g ys@(z:zs) = if p z then g zs else ys