catamorphism

Exposes a Template Haskell function for generating catamorphisms. https://github.com/frerich/catamorphism

Latest on Hackage:0.7.0.0

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

BSD3 licensed by Frerich Raabe

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 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) (+)
Depends on 2 packages:
Used by 1 package:
comments powered byDisqus