[Haskell-beginners] Function Type Confusion ..

[Brent Yorgey]

On Tue, Jan 27, 2009 at 09:42:54AM -0800, Tom Poliquin wrote:
> 
> I was reading "Arrows and Computation" 
> 
> http://www.soi.city.ac.uk/~ross/papers/fop.ps.gz
> 
> (trying to lose my 'beginner' status) when I saw (on page
> one) 
> 
> add :: (b -> Int) -> (b -> Int) -> (b -> Int)
> add f g b = f b + g b
> 
> It seemed like the type definition was wrong (short at least).

Hi Tom, that's a great paper to read!  I think your confusion seems to
stem from this simple fact: every function in Haskell only takes one
argument.

Functions that look like they take multiple arguments, for example

  add :: Int -> Int -> Int
  add x y = x + y

are really one-argument functions which return functions.  In the
above example, 'add' is a function which takes a single Int, and
returns a function as output.  This output function also takes a
single Int and finally returns an Int.  Observe:

Prelude> let add x y = (x + y :: Int)
Prelude> :t add
add :: Int -> Int -> Int
Prelude> :t add 3
add 3 :: Int -> Int
Prelude> :t (add 3) 5
(add 3) 5 :: Int
Prelude> (add 3) 5
8
Prelude> add 3 5
8

So we could also write the type of 'add' like this:

  add :: Int -> (Int -> Int)

and in fact, this add's real type.  Int -> Int -> Int is just an
abbreviation; -> associates to the right, so we can omit parentheses
that occur at the rightmost end of a type.  As you can see above, by
the same token, function application associates to the left, so 'add 3
5' is really just an abbreviation for '(add 3) 5': ie., first apply
'add' to 3, obtaining another function as output, then apply that
function to 5.

By now I'm sure you can see that 

  (b -> Int) -> (b -> Int) -> (b -> Int) 

is exactly the same type as 

  (b -> Int) -> (b -> Int) -> b -> Int.

You can think of something of this type *either* as something which
takes two arguments of type (b -> Int) and returns a function of type
(b -> Int); *or* as something which takes three arguments, two of type
(b -> Int) and one of type b, and returns something of type Int; these
are in fact just two different ways to think about the same thing.

Hope that is helpful!
-Brent