More specifically, I want to transform a tree of SomeExpr to a tree of (SomethingElse, SomeExpr), "prefixing" each node with a default value in the process.
The result have essentially the same structure as the input.

data ASTAttachment = AA {} deriving (Eq,Read,Show,Ord,Typeable,Data)
type family AST a :: *
type instance AST () = ASTExpr ()
type instance AST AA = (AA, ASTExpr AA)
data ASTExpr a
    = ALiteral String
    | AApplication [AST a] (ASTOp a)
    | ARef String
    | ABind (AST a) String
    | AMany (ASTMany a)
data ASTOp a
    = AOSym String
    | AOAlpha String
    | AOMany (ASTMany a)
data ASTMany a
    = AMSimple [AST a]
    | AMAggeregate [AST a]
deriving instance Typeable ASTMany
deriving instance Typeable ASTOp
deriving instance Typeable ASTExpr
deriving instance Data (ASTMany ())
deriving instance Data (ASTOp ())
deriving instance Data (ASTExpr ())

Currently I have values of type (AST ()),  and I need to transform them to (AST ASTAttachment) in the obvious way.
Now I'm stuck at "derive instance Data (ASTExpr ASTAttachment)", where ghc reports "Multiple declarations of '$cSomeConstructor'".
Even if I can get past this, I still don't know how to use SYB to transform between trees of different types.