This module exposes a makeCata function which can create catamorphisms for arbitrary Haskell types. Catamorphisms are functions which deconstruct some value by replacing each data constructor with a custom function yielding a new value. See http://www.haskell.org/haskellwiki/Catamorphisms for a more in-depth discussion of catamorphisms in Haskell.

The Haskell base package already comes with a couple of standard catamorphisms such as bool (for Bool values), maybe (for Maybe values) values, either for (Either values) values and foldr (for lists). These catamorphisms could have been generated using makeCata as follows:

-- Defines 'bool :: a -> a -> Bool -> a'
$(makeCata defaultOptions ''Bool)

-- Defines 'maybe :: b -> (a -> b) -> Maybe a -> b'
$(makeCata defaultOptions ''Maybe)

-- Defines 'either :: (a -> c) -> (b -> c) -> Either a b -> c'
$(makeCata defaultOptions ''Either)

-- Defines 'fold :: b -> (a -> b -> b) -> [a] -> b', i.e. 'flip foldr'. Note
-- that a custom catamorphism name has to be specified since '[]' is not a
-- valid function name.
$(makeCata defaultOptions { cataName = "fold" } ''[])

However, catamorphisms are especially useful for recursive data structures. Consider the following simple example which defines a basic data type for modelling sums of numbers, supporting variables:

import Data.Morphism.Cata
import Data.Maybe (fromJust)

data Expr a = Number a
            | Variable Char
            | Sum (Expr a) (Expr a)

-- Defines 'cataExpr :: (a -> b) -> (Char -> b) -> (b -> b -> b) -> Expr a -> b'
$(makeCata defaultOptions { cataName = "cataExpr" } ''Expr)

The makeCata invocation defines a cataExpr function which works like a fold on Expr values; it can be used to implement various useful other functions:

-- Evaluate an Expr, given some variable bindings
eval :: Num a => [(Char, a)] -> Expr a -> a
eval vars = cataExpr id (fromJust . (`lookup` vars)) (+)

-- Pretty-prints an Expr
pprint :: Show a => Expr a -> String
pprint = cataExpr show show (\a b -> a ++ " + " ++ b)

-- Counts the number of variables used in an expr
numVars :: Expr a -> Int
numVars = cataExpr (const 1) (const 0) (+)