Something catamorphism-like?

gistfile1.hs

newtype Fix f = Fix (f (Fix f))

-- Define List as the fixed point of a type operator
data ListR a t = Nil | Cons a t
type List a = Fix (ListR a)

-- The type operator ListR represents "one layer" of the structure
-- of List. We can do something fold-like with it.
-- My question is, is there a name for f? It's like a catamorphism
-- but doesn't recurse into the data.
f :: ListR a t -> b -> (a -> t -> b) -> b
f Nil n _ = n
f (Cons x xs) _ c = c x xs

-- We can use f to define an actual catamorphism.
fold :: List a -> b -> (a -> b -> b) -> b
fold (Fix xs) n c = f xs n $ \y ys -> c y $ fold ys n c


-- Misc. utilities for playing with the "List" type
---------------------------------------------------
(<<<=) = (.) . (.)

fromList :: [a] -> List a
fromList = foldr (Fix <<<= Cons) (Fix Nil)

toList :: List a -> [a]
toList xs = fold xs [] (:)