How to implement this higher order function

Question

I'm a newbe in functional programming, and I'm trying to solve the following exercise;

---

Given the type

type Cont r a = (a -> r) -> r

Implement the following higher-order function

mapReader :: (a -> b) -> (Cont r a) -> Cont r b

---

The first step would be to simplify the types, which gives:

mapReader :: (a -> b) -> ((a -> r) -> r) -> (b -> r) -> r

Next, define the parameters that need to be provided in this function. These parameters are three functions so we get

mapReader :: (a -> b) -> ((a -> r) -> r) -> (b -> r) -> r
mapReader f g h = _1

From here, we can define the following types:

f :: a -> b
g :: (a -> r) -> r
h :: b -> r
_1 :: r

But now I'm stuck. There are two functions that result in r, and one of them contains another function (a -> r). How can I start defining r? Any hints are much appreciated!

Answer 1

We have

f :: a -> b
g :: (a -> r) -> r
h :: b -> r

and we need

_1 :: r

There are two ways we can make r: g and h.

Let's try using h. h takes an argument of type b. The only way to get one of those is using f. f takes an argument of type a, and ... we don't have any way to get one of those.

So now let's try using g instead:

mapReader f g h = g _2

We're told

_2 :: a -> r

Since we're constructing a function, we can apply lambda abstraction as usual:

mapReader f g h = g (\a -> _3)

a :: a
_3 :: r

But wait ... now we have an a, so we can go back to our first attempt:

mapReader f g h = g (\a -> h (f a))

Or, more compactly,

mapReader f g h = g (h . f)

---

What if instead of going back to the first attempt we did it the second way again?

mapReader' f g h =
  g (\a1 -> g (\a2 -> _4))

_4 :: r

You could go this way forever, but you could also stop here in two different ways:

mapReader2 f g h =
  g (\_ -> g (h . f))

mapReader3 f g h =
  g (\a1 -> g (\_ -> h (f a1)))

Oy! These are three different functions that all have the same type, and as shown this approach can be used to generate an infinite family of functions! How can you decide which one you want? You have to consider the intention. g's argument is the continuation, so you want to compose a function with what you're passing g, not call g multiple times. So mapReader is the "correct" answer.

More precisely, mapReader is supposed to map morphisms for the continuation functor. That requires in particular that

mapReader id = id

That is,

mapReader id g h = g (h . id)
  = g h

That's unconditionally true for the correct definition, but not for any of the others.

Answer 2

Start by looking at what you can do with the three arguments.

1. You can compose f and h: h . f :: a -> r.
2. You can apply g to h . f: g (h . f) :: r.

So you could simply say that mapReader f g h = g (h . f). There's not enough information here to specify what r is; it depends entirely on what arguments g and h are given to mapReader.

Answer 3

So you have

f ::  a -> b
h ::       b -> r
g :: (a ->      r) -> r

There's also the forward functional composition operator,

(>>>) :: (a -> b) -> (b -> r) -> (a -> r)

and the reversed application operator,

(&) :: t -> (t -> r) -> r

so that

f >>> h :: ......... -- what?

and

(f >>> h) & g :: ......... -- what else?

Can you come up with the definitions of (>>>) and (&), just from their types?

---

Let me get you started on the first one.

(>>>) ::   (a -> b)    -> (b -> r)     -> (a  -> r)

means that

(>>>) (f :: a -> b)    :: (b -> r)     -> (a  -> r)
(>>>) (f :: a -> b) (g ::  b -> r)     :: (a  -> r)
(>>>) (f :: a -> b) (g ::  b -> r)  (x ::  a) :: r

So again we write them down

f :: a -> b
g ::      b -> r
x :: a
f x ::    b
g (f x) ::    ....

And that's that.

The most important rule that we used here, is

x   :: a
f   :: a -> r
f x ::      r