Is it possible to use SYB to transform the type?

Question

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.

Answer 1

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:

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