# 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 -> T
f A = A
f (B x) = B (B (f x))

g :: T -> 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 -> 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?

• What are we given? Are we given the source code of f and g? Only black-box access to f and g? Are there further restrictions on the body of f and g, such as they cannot contain conditional statements? Do you have any requirements on what form of h you will accept? – D.W. Apr 21 '14 at 15:39
• They can not contain conditional statements as the only datatype available is T (conditionals are generally functions on Bool). Imagine a very limited subset of Haskell. You have full access to the source of f and g. The requirement of h is that you don't have a reference to f and g itself, ie, it must be fully inlined - except if that is impossible in some cases. Then, for those cases, a reference to f and g is acceptable. – dokkat Apr 21 '14 at 15:44
• And if that is desirable, the problem I am trying to solve is exactly that of inlining/fusing two recursive functions on T. I know the problem is difficult for arbitrary recursive functions, but I don't know how hard it is for that kind of restricted, provably terminating functions. I didn't have many attempts as I don't know exactly what is the problem I am facing, but I tried two different things, reducing the problem to context-free-grammars, as you've seen, and blindly inserting g inside the body of f and watching if it fits. In some cases it does and the result is correct. – dokkat Apr 21 '14 at 15:49

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.

• That is exactly what I tried, DW, but it didn't work in some cases such as f (B (B x)) = B (B x) and g (B (B (B x))) = B (B (B x))), where h should be h (B (B (B (B (B (B x)))))) = B (B (B (B (B (B (h x))))) (this is where the other question come from). After many manual attempts I decided to ask help as this is probably a known problem with a proper name I could research about. I guess "regular transducers" are the keywords I need, let me research now. Thank you. Edit: I can't upvote you with this account. – dokkat Apr 21 '14 at 15:53
• @dokkat, glad this helps. I'm not clear on why simply plugging in doesn't work on that example, though. To have a full definition of f, it needs to cover all possible cases of what the input looks like, so you need to specify the values of f (B A) and f A and g (B (B A)) and g (B A) and g A; once you do that, I think you might be able to make plugging-in work, if you also apply a case split on x as many times as needed. – D.W. Apr 21 '14 at 16:15
• Hmm? I'm not sure what you mean...? Take a look? – dokkat Apr 21 '14 at 16:27
• @dokkat: About your lpaste: (1) Your f and g are not toal. (2) You have to perform a case split on x in order to inline g so that eventually you can inline f. – Toxaris Apr 21 '14 at 17:42
• 1. Your definition of f is not complete. What is f (B A)? Your definition of f doesn't say. We might need to have a complete definition of f and g for my technique to work. I suggest you start by extending your definition of f and g to cover all cases. 2. The answer to your "Now what?" is to case-split. Once you have a complete definition for f, you'll discover there are two cases, depending on whether g x = A or g x = B y. To resolve which is the case, you can case-split on x, based upon which of the patterns in the definition of g is matched by x. – D.W. Apr 21 '14 at 17:45

What is the name of the problem I am trying to solve?

This is a form of supercompilation.

• ...? Mind elaborating further? – dokkat Apr 21 '14 at 17:52