How to compose these two functions

Question

I know the title is a bit unclear, the problem is:

Suppose I have a function of type a -> c, another function of type b -> d, how can I get a function of type (a -> b) -> (c -> d), or is it impossible in general?

---

Probably I should provide some background. I asked this question because I have difficulty solving Exercise 9 from the paper Fun with phantom types.

data Type t where
  ...
  RFun :: Type a -> Type b -> Type (a -> b)

And the tequalfunction

tequal :: Type t -> Type u -> Maybe (t -> u)
...
tequal (RFun a b) (RFun c d) = -- should do something with (tequal a c) (tequal b d)

So the problem boils down to composing a -> c and b -> d to get (a -> b) -> (c -> d)

Answer 1

This is impossible.

Suppose you have desired function f :: (a -> b) -> (c -> d).

You can simplify it's type to (a -> b) -> c -> d (See why).

How could implementation of f look like? It has first argument of type a -> b and second of type c:

f ab c = ...

What can you do with ab? It's a function but you can't apply it because you don't have anything of type a (except _|_). And even if you have functions g :: a -> c and h :: b -> d they are of no use because you don't have anything of type a or b and you can't compose them.

So the only valid implementation is something like

f ab = undefined

or

f = undefined

---

Regarding second part of your question, it seems that you can recursively use tequal to check function type equality: types a -> c and b -> d are equal only if a = b and c = d (this is valid because toy type system from the paper don't have type variables).

Here is a sketch of implementation:

tequal (RFun a c) (RFun b d)
  = liftM2 func (tequal a b) (tequal c d)

You can note that the code is almost identical to the case for RPair. This is somehow related to currying.

Answer 2

As a small supplement to max taldykin's answer,

Given

f :: (a -> c) -> (b -> d) -> (a -> b) -> (c -> d)
f ac bd ab = ???

there's really only one way to combine the arguments

bd . ab :: a -> d

but now we're stuck! We have no way to construct a c -> d from any combination of a -> c, b -> d, a -> b, or a -> d.

On the other hand, if we had a c -> a then we could construct a

f :: (c -> a) -> (b -> d) -> (a -> b) -> (c -> d)
f ca bd ab = bd . ab . ca

By the way, it can be very helpful to get out a pen and paper and draw some arrows and try to connect them into a diagram:

If you try to do the same for f :: (a -> c) -> (b -> d) -> (a -> b) -> (c -> d) then you'll see that there's no way to draw a diagram that connects c -> d:

and now we have no way to connect the dots.