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?

  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Apr 21 '14 at 15:39
  • $\begingroup$ 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. $\endgroup$ – dokkat Apr 21 '14 at 15:44
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – dokkat Apr 21 '14 at 15:53
  • $\begingroup$ @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. $\endgroup$ – D.W. Apr 21 '14 at 16:15
  • $\begingroup$ Hmm? I'm not sure what you mean...? Take a look? $\endgroup$ – dokkat Apr 21 '14 at 16:27
  • 1
    $\begingroup$ @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. $\endgroup$ – Toxaris Apr 21 '14 at 17:42
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • 2
    $\begingroup$ ...? Mind elaborating further? $\endgroup$ – dokkat Apr 21 '14 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.