Understanding Data.Function.on type signature

Question

I'm still a beginner when it comes to Haskell syntax and functional programming languages so when I look at the type declaration for Data.Function.on which is on :: (b -> b -> c) -> (a -> b) -> a -> a -> c, my interpretation is that it takes four parameters: (b -> b -> c), (a -> b), a, a, and returns c. However, when I look at the general use syntax for Data.Function.on which is (*) `on` f = \x y -> f x * f y, it is only taking two function parameters, not four, so how does the type signature relate to the usage syntax?

Answer 1

my interpretation is that it takes four parameters

All Haskell functions take one argument. Some of them just return other functions.

The best way to look at the signature for on is as a higher-order function: (b -> b -> c) -> (a -> b) -> (a -> a -> c). This says "if you give me a binary operator that takes bs and gives a c and a way to get bs from as, I will give you a binary operator that takes as and gives a c". You can see this in the definition:

(*) `on` f = \x y -> f x * f y

Answer 2

The Haskell arrow for function types hides a simple but clever idea. You have to think of -> as an operator, like + and -, but for types. It takes two types as arguments and gives you a new type consisting of a function. So in

Int -> String

You have the types Int and String, and you get a function from an Int to a String.

Just like any other operator, you need a rule for a chain of them. If you think of -, what does this mean?

10 - 6 - 4

Does it mean (10 - 6) - 4 = 0, or does it mean 10 - (6 - 4) = 8? The answer is the first one, which is why we say that - is "left associative".

The -> operator is right associative, so

foo :: Int -> String -> String

actually means

foo :: Int -> (String -> String)

Think about what this means. It means that foo doesn't take 2 arguments and return a result of type String, it actually takes 1 argument (the Int) and returns a new function that takes the second argument (the String) and returns the final String.

Function application works the same way, except that is left associative. So

foo 15 "wibble"

actually means

(foo 15) "wibble"

So foo is applied to 15 and returns a new function which is then applied to "wibble".

This leads to a neat trick: instead of having to provide all the parameters when you call a function (as you do in just about every other programming language), you can just provide the first one or the first few, and get back a new function that expects the rest of the parameters.

This is what is happening with on. I'll use a more concrete version where 'f' is replaced by 'length'.

(*) on length

you give on its first two parameters. The result is a new function that expects the other two. In types,

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

In this case (*) has type Num n => n -> n -> n (I'm using different letters to make this less confusing), so that is matched with the type of the first argument to on, leading to the conclusion that if type b is substitued by n then type c must be as well, and and must also be a Num instance. Therefore length must return some numeric type. As it happens the type of length is [d] -> Int, and Int is an instance of Num, so that works out. So at the end of this you get:

(*) `on` length :: [d] -> [d] -> Int