Search code examples
haskellfunctional-programmingrecursion-schemes

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
    | Add a a

instance Functor IntF where
    fmap eval (Const i) = Const i
    fmap eval (x `Add` y) = eval x `Add` eval y

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)

run = eval addExpr

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
    instance Monad Ctr
    
    type MAlgebra m f a = f (m a) -> m a
    
    fresh :: Ctr Int
    fresh = Ctr (\i -> (i, i+1))
    
    data IntF a 
      = Val
      | Add a a
    
    malg :: IntF (Ctr String) -> Ctr String
    malg Val = (\x -> "a" ++ show x) <$> fresh
    malg (Add x y) = (\a b -> a ++ " && " ++ b) <$> x <*> y
    
    go = cata malg