Haskell list catamorphism

ListAlgebra.hs

{-# LANGUAGE RankNTypes #-}

module ListAlgebra
  ( ListAlgebra(..)
  ) where

newtype ListAlgebra a = ListAlgebra (forall b. b -> (a -> b -> b) -> b)

nil :: ListAlgebra a
nil = ListAlgebra const

cons :: a -> ListAlgebra a -> ListAlgebra a
cons a (ListAlgebra f) = ListAlgebra (\b accf -> accf a (f b accf))

instance Show a => Show (ListAlgebra a) where
  show (ListAlgebra f) =
    let accf a b = show a ++ "," ++ b
    in  "[" ++ (f "]" accf)

Now write tail ;)