Data.Morphism.Cata

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) (+)

Documentation

data CataOptions

Values of the CataOptions type can be passed to makeCata in order to customize the generated catamorphism. At this point, only the name of the function can be changed.

Constructors

CataOptions

Fields

• cataName :: String

  The desired name for the catamorphism. An empty string will make makeCata derive the catamorphism name from the type by just taking the type name and making the first letter lower-case.

defaultOptions :: CataOptions

The default catamorphism generation options; the catamorphism will be named after the type, e.g.

$(makeCata defaultOptions ''Bool)

defines a function bool.

makeCata :: CataOptions -> Name -> Q [Dec]

The makeCata function creates a catamorphism for the given type.