# Chaining values with catamorphisms

Suppose I have definitions as follows (where `cata` is the catamorphism):

``````type Algebra f a = f a -> a

newtype Fix f = Fx (f (Fix f))

unFix :: Fix f -> f (Fix f)
unFix (Fx x) = x

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
``````

I was wondering if there would be some way to modify the definition of `cata` so that I could chain some object such as an `int` through it such that I could generate unique handles for things within the alg function, i.e. "a0", "a1", "a2", ..., etc.

Edit: To make this more clear, I'd like to be able to have some function `cata'` such that when I have something similar to the following definitions

``````data IntF a
= Const Int

instance Functor IntF where
fmap eval (Const i) = Const i

alg :: Int -> Algebra IntF String
alg n (Const i) = "a" ++ show n
alg n (s1 `Add` s2) = s1 ++ " && " ++ s2

eval = cata' alg

addExpr = Fx \$ (Fx \$ Const 5) `Add` (Fx \$ Const 4)

``````

then `run` evaluates to "a0 && a1" or something similar, i.e. the two constants don't get labeled the same thing.

Solution

• Just sequence them as monads.

``````newtype Ctr a = Ctr { runCtr :: Int -> (a, Int) } -- is State Int

instance Functor Ctr
instance Applicative Ctr

type MAlgebra m f a = f (m a) -> m a

fresh :: Ctr Int
fresh = Ctr (\i -> (i, i+1))

data IntF a
= Val