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