How to compose these two functions
I know the title is a bit confusing, the problem is:
Suppose I have a type function a -> c
, another type function b -> d
, how can I get a type function (a -> b) -> (c -> d)
, or not possible at all?
I should probably provide some background. I asked this question because I am having a hard time solving Exercise 9 from the Fun article with phantom types .
data Type t where
...
RFun :: Type a -> Type b -> Type (a -> b)
And the function tequal
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)
Thus, the problem is reduced to compiling a -> c
and b -> d
for obtaining(a -> b) -> (c -> d)
source to share
It's impossible.
Let's assume you have the desired function f :: (a -> b) -> (c -> d)
.
You can simplify its type to (a -> b) -> c -> d
(see why ).
What might the implementation look like f
? It has a first type argument a -> b
and a second 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
(other than _|_
). And even if you have functions g :: a -> c
and h :: b -> d
, they are useless because you don't have anything of type a
or b
, and you cannot link them.
So the only valid implementation is something like
f ab = undefined
or
f = undefined
Regarding the second part of your question, it seems like you can recursively use tequal
to test for type equality of a function: types a -> c
and b -> d
are equal only if a
= b
and c
= d
(this is true because a paper toy system has no type variables).
Here's a sketch of the implementation:
tequal (RFun a c) (RFun b d)
= liftM2 func (tequal a b) (tequal c d)
You can see that the code is almost identical to the case for RPair
. It has something to do with curry.
source to share
As a small addition to Max Taldykin,
Considering
f :: (a -> c) -> (b -> d) -> (a -> b) -> (c -> d)
f ac bd ab = ???
there is only one way to combine arguments
bd . ab :: a -> d
but now we're stuck! We can not build a c -> d
any combination of a -> c
, b -> d
, a -> b
or a -> d
.
On the other hand, if we had c -> a
, then we could plot a
f :: (c -> a) -> (b -> d) -> (a -> b) -> (c -> d)
f ca bd ab = bd . ab . ca
By the way, it is very helpful to take out a pen and paper and draw some arrows and try to connect them to a diagram:
If you try to do the same for f :: (a -> c) -> (b -> d) -> (a -> b) -> (c -> d)
, you will see that there is no way to draw a diagram that connects c -> d
:
and now we cannot connect the dots.
source to share
I believe you are looking for higher order functions , which is basically a function that takes functions as parameters or returns 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
Note that f2 takes a function and applies it to the second parameter, and f3 takes a function and returns f1.
If you do f2 (f3 (f0)) 5 it will return you 5.
Step by step
1- f2 (f3 (f0)) 5 f3 takes function (f0) and returns f1.
2- f2 (f1) 5 f2 takes a function (f1) and applies it to the second parameter (5)
3- f1 (5) f1 applies to 5.
source to share