Q:

Cannot destruct transitive type

Say I have the following GADT:
data Stage a b where
    Comb :: Stage a b -> Stage b c -> Stage a c
    FMap :: (a -> b) -> Stage a b

I now want a function that works like this:
run (a `Comb` b) = (a,b)
run (FMap f)     = (FMap f,FMap id)

How would I construct such a function? 
I tried different ways of binding the types but did not succeed. 
Is there an extension I am missing that enables more extensive type bindings? 
This is the error message:
Couldn't match type `t' with `(Stage t1 b, Stage b t2)'
  `t' is a rigid type variable bound by
      the inferred type of run :: Stage t1 t2 -> t at <interactive>:11:5
In the expression: (a, b)
In an equation for `run': run (a Comb b) = (a, b)

A description of what I want to accomplish:
I want to design a DSL and a function run that can try to run some code of the DSL in a couple of different ways (I have multiple different run functions for each way). 
The run function will try to run as much of the code given it as possible, and then report back what code it could not run and what the result of the code it could run was. 

A:

You'll need a type signature for run, because you're pattern matching on a GADT.  Pattern matching on GADT requires type refinement, and that generally only works if there is a type signature. 
But it's unclear what the type signature would be.  If the input value is
a `Comb` b :: Stage x y

then you return (a, b), where
a :: Stage x b
b :: Stage b y

for some unknown b. This is an existential type escaping.  You cannot write
run :: Stage x y -> (State x b, Stage b y)

because this would mean it would have to work for all b, but it only works for some (unknown) b.
Unfortunately, it is not clear why you want to write a function like run.  Why produce a pair?  What do you want to do with this pair later on?  The Comb constructor is defined to combine two stages that have an unknown intermediate type, so this version of run would work:
run :: Stage a b -> Stage a b
run (a `Comb` b) = a `Comb` b
run (FMap f)     = FMap f `Comb` FMap id

Or you could define a more specific datatype only allowing a "pair" of two stages with unknown intermediate type:
data PairStages a b where
  PairStages :: Stage a b -> Stage b c -> PairStages a c

And then:
run :: Stage a b -> PairStages a b
run (a `Comb` b) = PairStages a b
run (FMap f)     = PairStages (FMap f) (FMap id)

But it still feels strange to me that run is returning a pair.  As I said, it's unclear what you want to do with the result of run.  It would seem more useful to have run be a recursive function that actually somehow combines the results of running the components in the Comb case.  For example, like this:
run :: Stage a b -> (a -> b)
run (a `Comb` b) = run b .  run a
run (FMap f)     = f

