Examples

CPS, Continuation Monad, and Writer Monad の例。

part :: (a -> Bool) -> [a] -> [a]
part p l = let f []     z = z
               f (x:xs) z = if p x then x : f xs z
                                   else f xs (z++[x])
            in f l []

をいろいろに書いてみる*1。

CPS *2

part1 p = f id
  where	
    f c [] = c []
    f c (x:xs) | p x = x:f c xs
	       | otherwise = f (c . (x:)) xs

Continuation Monad

外に吐き出すためにmapContを使う。

part1' p xs = runCont (f xs) id
  where
    f [] = return []
    f (x:xs)
      | p x = mapCont (x:) $ f xs
      | otherwise = f xs >>= return . (x:)

右結合

条件を充たさない方のリストも右結合になっている。

part2 p xs = uncurry ($) $ f xs
  where
    f [] = (id, [])
    f (x:xs)
      | p x = appFst ((x:) .) $ f xs
      | otherwise = appSnd (x:) $ f xs


appFst f ~(x, y) = (f x, y)
appSnd f ~(x, y) = (x, f y)

Writer Monad

part2' p xs = r
  where (r, w) = runWriter $ f xs
	f [] = return w
	f (x:xs)
	  | p x = f xs >>= return . (x:)
	  | otherwise = tell [x] >> f xs

おまけ

part0 p = uncurry (++) . partition p

*1:[id:yokoyamatetsuo:20050219#p5]より

*2:論文は読んでないけれど多分vanish_appがやっていること