`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

に落ち着く。あまり複雑なこともせずに式変形で不動点コンビネータが導き出されるのは面白い。

Arantium Maestum