Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype? Let the following datatype be defined:

 data T = A | B T | C T T


That is, B, B T, B (B T), C A A, C (B T) A and so on all are members of T. Now, suppose we define two functions that operate on that type:

f :: T -&gt; T
f A = A
f (B x) = B (B (f x))

g :: T -&gt; T
g A = A
g (B x) = B (B (B (g x)))


There are restrictions on the definition of f and g: first, recursive calls can only be applied directly to a subterm of one of the inputs (guaranteeing termination), and second, they can't use any datatype other than T on their bodies (consider T is the only existing type). In this case, we know that the following function:

h :: T -&gt; T
h A = A
h (B x) = B (B (B (B (B (B (h x))))))


works as the composition f . g. My question is, is it possible/decidable to find the composition of f and g in this form - that is, without any reference to f and g themselves? What is the name of the problem I am trying to solve?
If the functions are sufficiently well-behaved, as in your example, you can express f and g as regular transducers for trees.  Then you can compute the composition of two such transducers, which will also be a regular transducer (I believe), and convert it back to a Haskell function.

Another approach: in some cases, simple let-substitution might suffice.  For instance, given your f and your g, we can identify their composition fg via the following sequence of steps.  We know fg = f . g, so plugging in the definition of g, we get:

fg A = f(g(A)) = f A
fg (B x) = f(g(B x)) = f(B (B (B (g x))))


Now plugging in the definition of f, we get:

fg A = A
fg (B x) = B (B f(B (B (g x))))


Continuing to plug in the definition of f, we get:

fg A = A
fg (B x) = B (B (B B( f(B (g x)))))


And plugging in the definition of f once more:

fg A = A
fg (B x) = B (B (B B( (B (B (f(g x))))))


which simplifies to

fg A = A
fg (B x) = B (B (B (B (B (B (fg x)))))


And now you have your desired recursive definition of their composition.  Notice that this is the same as the function h you wanted to get out.  As far as I know, there's no guarantee that this procedure will always work, but it is easy enough to apply.