CODEWITHSUNDEEP
haskell
Jeremy Bi
Jeremy Bi

Reputation: 31

How to compose these two functions

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)

Upvotes: 3

Views: 147

Answers (3)

Rein Henrichs
Rein Henrichs

Reputation: 15605

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:

enter image description here

and now we have no way to connect the dots.

Upvotes: 3

max taldykin
max taldykin

Reputation: 12898

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.

Upvotes: 3

Xaphanius
Xaphanius

Reputation: 619

I believe that you are looking for Higher Order Functions, which is basically a function taking functions as parameters or returning other functions.

For example to illustrate a higher order function, you can define the following functions:

f0 :: Int -> Int
f0 x = 0

f1 :: a -> a
f1 x = x

f2 :: (a -> a) -> a -> a
f2 f a = f(a)

f3 :: (a -> a) -> (a -> a)
f3 f = f1

Notice that f2 takes a function and apply it to the second parameter and that f3 takes a function and return the function f1.

If you execute f2(f3(f0)) 5, it is going to return 5 to you.

Step-by-step

1- f2(f3(f0)) 5 f3 takes a function (f0) and will return f1.

2- f2(f1) 5 f2 takes a function (f1) and applies it to the second parameter (5)

3- f1(5) f1 is applied to 5.

Upvotes: 0

Related Questions