Paramorphisms!

ListCase.hs

module ListCase where

listCase :: (a -> [a] -> b) -> [a] -> [b]
listCase f [] = []
listCase f (x:xs) = f x xs : listCase f xs

paraList :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraList c n []       = n
paraList c n (x : xs) = c x xs $ paraList c n xs

listCase' :: (a -> [a] -> b) -> [a] -> [b]
listCase' c = paraList (\ x xs tl -> c x xs : tl) []

newtype Fix f = Fix { unFix :: f (Fix f) }

para :: Functor f => (f (Fix f, b) -> b) -> Fix f -> b
para alg = alg . fmap (\ rec -> (rec, para alg rec)) . unFix

newtype ListF a as = ListF { unListF :: Maybe (a, as) }
instance Functor (ListF a) where fmap f = ListF . fmap (fmap f) . unListF
type List a = Fix (ListF a)

nil :: List a
nil = Fix $ ListF $ Nothing

cons :: a -> List a -> List a
cons = curry $ Fix . ListF .Just

paraList' :: (a -> List a -> b -> b) -> b -> List a -> b
paraList' c n = para $ maybe n (\ (a, (as, b)) -> c a as b) . unListF

listCase'' :: (a -> List a -> b) -> List a -> List b
listCase'' c = paraList' (\ x xs tl -> cons (c x xs) tl) nil

toList :: [a] -> List a
toList = foldr cons nil

fromList :: List a -> [a]
fromList = paraList' (\ x _ tl -> x : tl) []