Is it possible to use SYB to transform the type?

I want to write a rename function to replace String names (which represent hierarchical identifiers) in my AST with GUID names (integers) from a symbol table carried as hidden state in a Renamer monad.

I have an AST a type that is parameterized over the type of name. Names in the leaves of the AST are of type Name a:

data Name a = Name a

Which makes it easy to target them with a SYB transformer.

The parser is typed (ignoring the possibility of error for brevity):

parse :: String -> AST String

and I want the rename function to be typed:

rename :: AST String -> Renamer (AST GUID)

Is it possible to use SYB to transform all Name String's into Name GUID's with a transformer:

resolveName :: Name String -> Renamer (Name GUID)

and all other values from c String to c GUID by transforming their children, and pasting them back together with the same constructor, albeit with a different type parameter?

The everywhereM function is close to what I want, but it can only transform c a -> m (c a) and not c a -> m (c b).

My fallback solution (other than writing the boiler-plate by hand) is to remove the type parameter from AST, and define Name like this:

data Name = StrName String
          | GuidName GUID

so that the rename would be typed:

rename :: AST -> Renamer AST

making it work with everywhereM. However, this would leave the possibility that an AST could still hold StrName's after being renamed. I wanted to use the type system to formally capture the fact that a renamed AST can only hold GUID names.

Solution

One solution (perhaps less efficient than you were hoping for) would be to make your AST an instance of Functor, Data and Typeable (GHC 7 can probably derive all of these for you) then do:

import Data.Generics.Uniplate.Data(universeBi) -- from the uniplate package
import qualified Data.Map as Map

rename :: AST String -> Renamer (AST GUID)
rename x = do
    let names = nub $ universeBi x :: [Name String]
    guids <- mapM resolveName names
    let mp = Map.fromList $ zip names guids
    return $ fmap (mp Map.!) x

Two points:

I'm assuming it's easy to eliminate the Name bit from resolveName, but I suspect it is.
You can switch universeBi for something equivalent in SYB, but I find it much easier to understand the Uniplate versions.