Monthly Downloads: 11
Programming language: Haskell
License: BSD 3-clause "New" or "Revised" License
Tags: Development    

catamorphism alternatives and similar packages

Based on the "Development" category.
Alternatively, view catamorphism alternatives based on common mentions on social networks and blogs.

Do you think we are missing an alternative of catamorphism or a related project?

Add another 'Development' Package



Build Status

This project builds an Haskell module Data.Morphism.Cata which exports a makeCata function which can be used to generate catamorphisms for Haskell types. The base package features a couple of standard catamorphisms such as bool, maybe, either, or foldr, all of which could be generated by 'makeCata'. However, catamorphisms are mostly useful for custom recursive data structures. For instance, given a simple type for modelling expressions involving numbers, variables and sums as in

{-# LANGUAGE TemplateHaskell #-}

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

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

You can use the following makeCata invocation to generate a function for folding Expr values - the function will be called cataExpr:

{- This 'makeCata' invocation defines a function

    cataExpr :: (a -> b)                   -- Number constructor
             -> (Char -> b)                -- Variable constructor
             -> (b -> b -> b)              -- Sum constructor
             -> Expr a
             -> b
$(makeCata defaultOptions { cataName = "cataExpr" } ''Expr)

This catamorphism can be used to define a whole bunch of other useful functions such as

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