7

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?

jcm
  • 5,499
  • 11
  • 49
  • 78

2 Answers2

27

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.

Chris Taylor
  • 46,912
  • 15
  • 110
  • 154
  • Ugh, I don't think I understand this part: 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 - how can you just decide to apply g to a? – jcm Mar 17 '14 at 11:03
  • 1
    A very comprehensive answer! For FP enthusiasts, I'd add that «the only thing we can do for this type» is a very interesting property called a free theorem: http://stackoverflow.com/questions/12421085/good-introduction-to-free-theorems) – Yuuri Mar 17 '14 at 11:10
  • 1
    @cookiemonster You have a thing of type `a`, and you have a function with the right type to be applied to things of type `a`, and when you have those two things it's up to you whether to apply the function or not (but in this case you have to do *something* and applying the function is the only thing the type system allows you to do, so ...) – Chris Taylor Mar 17 '14 at 11:43
  • @ChrisTaylor ok, I think that makes sense. How about this statement: "We now start the process of cleaning up. We could move the a to the left of the equality sign" - how can you just decide to move a? How is this possible? – jcm Mar 17 '14 at 11:54
  • 2
    @cookiemonster Because the two definitions `f a = e` and `f = \a -> e` mean the same thing, for any expression `e`. This kind of transformation (replacing one thing with another when they know they are equal) is called [equational reasoning](http://www.haskellforall.com/2013/12/equational-reasoning.html) and is a very powerful approach to writing code. – Chris Taylor Mar 17 '14 at 12:01
  • 1
    To eliminate the typecheck-failing stage, we can write `hi f g = \a -> (\b -> undefined) (g a)` or `hi f g = const undefined (g a)` :) – Earth Engine Jan 06 '15 at 21:29
4

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.

Ralph
  • 31,584
  • 38
  • 145
  • 282
Nicolas
  • 24,509
  • 5
  • 60
  • 66