hi :: (b -> c) -> (a -> b) -> (a -> c) in Haskell

Question

I have the following type signature in Haskell:

hi :: (b -> c) -> (a -> b) -> (a -> c)

I want to write a concrete implementation of it but I'm really struggling to understand where to start. I understand that hi takes a function (b -> c) which returns a function (a ->b) which finally returns a function (a -> c).

Can anyone show me an example of a concrete implementation? How do I know where to start with something like this and what goes on the left side of the definition?

Answer 1

One way to think of this is as a function that takes a (b -> c) and an (a -> b) and returns another function (a -> c). So let's start with that

hi f g = undefined       -- f :: b -> c, g :: a -> b

We know that the return type has to be a function (a -> c) -

hi f g = \a -> undefined -- f :: b -> c, g :: a -> b

We now have something of type a on the right hand side, and we have a function g :: a -> b so a sensible thing to do (in fact, the only thing we can do) is to apply g to a

hi f g = \a -> g a       -- ok, this fails to typecheck...

The expression g a has type b, and f :: b -> c, and we want to end up with a c. So again, there's only one thing we can do -

hi f g = \a -> f (g a)

And this type checks! We now start the process of cleaning up. We could move the a to the left of the equality sign

hi f g a = f (g a)

And, if you happen to know about the composition operator . you could notice that it can be used here

hi f g a = (f . g) a

Now the a is redundant on both sides (this is called eta reduction)

hi f g = f . g

and we can pull the . operator to the front of the expression by using its function form (.)

hi f g = (.) f g

Now the g and the f are both redundant (two more applications of eta reduction)

hi = (.)

So your function hi is nothing more than function composition.

Answer 2

You read it wrong: The -> operator is right-associative. Thus, your signature is: (b->c) -> ((a->b) -> (a->c)). So you can read it as : given a function from b to c, it returns a function that takes a function from a to b to finally returns a function from a to c.

From there, you should be able to resolve the exercise by yourself.