spanの小ネタ（再帰パターン編）
もあわせてどうぞ．
Prelude関数にspan :: (a -> Bool) -> [a] -> ([a],[a])という関数があります．この関数は，リストを前後に分けます．条件を満す要素が連続する先頭部分と残りの部分です．
code:haskell
span _ [] = ([],[])
span p xxs@(x:xs)
| p x = case span p xs of
(ys,zs) -> (x:ys,zs)
| otherwise = ([],xxs)
spanはリスト上の再帰関数ですので，再帰パターン(recursion-scheme)のどれかの具体例になっているはずですね．
再帰パターンには，なんとかモルフィズムという名前がついています．foldrはその中でももっとも良く知られているもので，これは，リスト上のcatamorphismの具体例です．ほかにも，unfoldrはリスト上のanamorphismの具体例です．さて，foldrはリストの先頭の要素と残りの部分を畳み込んだ結果とをまとめますが，spanではリストの先頭ではなく，リスト全体が必要になります．このような畳み込みの再帰パターンはparamorphismといいます．リスト上のparamorphismは以下のように定義できます． code:haskell
para :: (a -> (a,b) -> b) -> b -> a -> b para _ z [] = z
para phi z (x:xs) = phi x (xs, para phi z xs)
paraを用いてspanを定義すると以下のようになります．
code:haskell
span p = para phi ([],[])
where
phi x (xs,(ys,zs))
| p x = (x:ys,zs)
| otherwise = ([],x:xs)