Understanding higher-order function type declaration

1
votes

In the introductory Haskell text, Learn You a Haskell for Great Good, the author defines a function, applyTwice, that two times applies a function f to a parameter x to illustrate the higher order capabilities central to the functional paradigm.

applyTwice :: (a -> a) -> a -> a  
applyTwice f x = f (f x)

To this point, I found Haskell's type declarations clear, but this particular example confuses me. I think this is an opportunity to better understand type declarations.

The author indicates this construct "indicates that the first parameter is a function that takes something and returns that same thing. The second parameter is something of that type also and the return value is also of the same type." (text)

What does this type declaration mean? Why not use (a -> a) -> a, with each -> indicating a transformation of some sort?

2
haskelltype-declaration

2 Answers

3
votes

In between each -> is the type of a parameter to the function, with the last one being the type of the function's return value. So here the shape is _ -> _ -> _ (a function taking two parameters). The first parameter, though, happens to be a function, and has shape _ -> _ (taking one parameter).

So to use applyTwice:

  • pass a function that when given an a will return an a
  • pass an a
  • get an a as the result
2
votes

You should thing a -> b as a function that takes a a and outputs a b - so if f is such a function: f :: a -> b then everytime you feed it an v :: a (written as f v) you get an b: (f v) :: b.

Now of course such a function-type is a type too - higher order ... ;)

Now (a -> a) -> a -> a is (a -> a) -> (a -> a) so this is a function (let's call it applyTwice) that when given an f :: a -> a will produce another function a -> a: applyTwice f :: a -> a which is of course the function that take an v :: a and then does f (f a) (applying f twice).

If you have (a -> a) -> a on the other hand you have to somehow produce an a from a function of type a -> a which is really tricky (think about it: where do you get an a from that you can feed f?