spanの小ネタ(再帰パターン編)

spanの小ネタ(使い方編) spanの小ネタ(変奏編) もあわせてどうぞ． Prelude関数にspan :: (a -> Bool) -> [a] -> ([a],[a])という関数があります．この関数は，リストを前後に分けます．条件を満す要素が連続する先頭部分と残りの部分です． 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の具体例で