As I understand, you want something like
cata' :: Functor f => (Int -> f a -> a) -> Fix f -> a
so that you can operate both on f a
and it's index.
If that's true, here's a possible solution.
Associated Int
First we define a new type which will represent Int
-labelled functor:
{-# LANGUAGE DeriveFunctor #-}
data IntLabel f a = IntLabel Int (f a) deriving (Functor)
-- This acts pretty much like `zip`.
labelFix :: Functor f => [Int] -> Fix f -> Fix (IntLabel f)
labelFix (x:xs) (Fx f) = Fx . IntLabel x $ fmap (labelFix xs) f
Now we can define cata'
using cata
and labelFix
:
cata' :: Functor f => (Int -> f a -> a) -> Fix f -> a
cata' alg = cata alg' . labelFix [1..]
where
alg' (IntLabel n f) = alg n f
NOTE: unique Int
s are assigned to each layer, not each functor. E.g. for Fix []
each sublist of the outermost list will be labelled with 2
.
Threading effects
A different approach to the problem would be to use cata
to produce monadic value:
cata :: Functor f => (f (m a) -> m a) -> Fix f -> m a
This is just a specialized version of cata
. With it we can define (almost) cat'
as
cata'' :: Traversable f => (Int -> f a -> a) -> Fix f -> a
cata'' alg = flip evalState [1..] . cata alg'
where
alg' f = alg <$> newLabel <*> sequenceA f
newLabel :: State [a] a
newLabel = state (\(x:xs) -> (x, xs))
Note that Traversable
instance now is needed in order to switch f (m a)
to m (f a)
.
However, you might want to use just a bit more specialized cata
:
cata :: (Functor f, MonadReader Int m) => (f (m a) -> m a) -> Fix f -> m a