Hi :: (b & # 8594; c) & # 8594; (a & # 8594; b) & # 8594; (a & # 8594; c) in Haskell

Question

I have a type signature in Haskell:

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

I want to write a specific implementation, but I'm really trying to figure out where to start. I understand that hi accepts a function (b → c), which returns a function (a → b), which finally returns a function (a → c).

Can someone show me an example of a specific implementation? How do you know where to start with something like this and what happens on the left side of the definition?

Answer 1

One way to think about this is with a function that takes (b -> c) and (a -> b) and returns another function (a -> c) . So, let's start with the fact that

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

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

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

Now we have something like a on the right side, and we have the function g :: a -> b , so the reasonable thing (in fact, the only thing we can do) is apply g to a

 hi fg = \a -> ga -- ok, this fails to typecheck... 

The expression ga is of type b and f :: b -> c , and we want to end with c . So one more thing we can do is

 hi fg = \a -> f (ga) 

And this type checks! Now we are starting the cleaning process. We could move a left of the equal sign

 hi fga = f (ga) 

And if you know about the composition . , you may notice that it can be used here

 hi fga = (f . g) a 

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

 hi fg = f . g 

and we can print the operator . to the beginning of an expression using its functional form (.)

 hi fg = (.) fg 

Now g and f are redundant (two more reduction applications this)

 hi = (.) 

So your hi function is nothing more than a compound function.

Answer 2

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

From there, you can solve the exercise yourself.