catamorphism-0.6.0.0: A package exposing a helper function for generating catamorphisms.

Data.Morphism.Cata

Description

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) (+) Synopsis # Documentation 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 FieldscataName :: StringThe 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. The default catamorphism generation options; the catamorphism will be named after the type, e.g. $(makeCata defaultOptions ''Bool)

defines a function bool.

The makeCata function creates a catamorphism for the given type.