catamorphism: Exposes a Template Haskell function for generating catamorphisms.

[ bsd3, development, library ] [ Propose Tags ]

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 for a more in-depth discussion of catamorphisms in Haskell.

The Haskell base package already comes with a couple of standard catamorphisms, such as maybe (for Maybe values). The maybe function could have been generated using makeCata as follows:

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

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 'expr :: (a -> b) -> (Char -> b) -> (b -> b -> b) -> Expr a -> b'
$(makeCata defaultOptions ''Expr)

The makeCata invocation defines a expr 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 = expr id (fromJust . (`lookup` vars)) (+)

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

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




Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Versions [RSS],,,,,,,,,
Dependencies base (>=4.6 && <4.12), template-haskell (>=2.8 && <2.14) [details]
License BSD-3-Clause
Copyright Copyright (c) 2014, 2015, 2016, 2017, 2018 Frerich Raabe <>
Author Frerich Raabe
Category Development
Home page
Bug tracker
Source repo head: git clone
Uploaded by frerich at 2018-04-15T19:54:33Z
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 6684 total (30 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-04-15 [all 1 reports]