What does Haskell's Data.Function.on do?

Question

I am finding it hard to find examples of on in Haskell and I don't understand the explanation on Hoogle's Data.Function page. Please, can I have examples of its use and examples of problems/code where using it makes a solution simpler or more efficient?

Answer 1

Suppose we have a function f that takes two arguments. We want a similar function which acts as f, but only after both its arguments have been modified by some other function g.

We could write a new definition

new_f x y = f (g x) (g y)

or, exploiting on,

new_f = f `on` g

Nicely, the latter can be used directly, without defining a new symbol new_f. (Using a lambda is also viable, but not as nice)

This is typically used with compare, a library binary function that checks the ordering between its two arguments. So, we can use

sortBy (compare `on` name)   somePeopleList
sortBy (compare `on` age)    somePeopleList
sortBy (compare `on` height) somePeopleList
...

to sort according different criteria. Above, we assume that name, etc. are functions that can extract the relevant information from a person.

(In more modern Haskell we also have sortBy (comparing age) somePeopleList, or even sortOn age somePeopleList for the same task)

Answer 2

The type signature for on is

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

And, really, there's only one reasonable (non-bottom) implementation of this function.

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

Or, written with an infix argument as they do in the GHC source,

(.+.) `on` g = \x y -> g x .+. g y

So the body of the function is fairly simple. The question is: Why would we care.

The most common use case for on, in my experience, is when augmenting sorting or comparing functions with compare.

In Python, if we wanted to sort a list of people based on their names, we might write

my_list.sort(key=lambda person: person.name)

Haskell's sortBy takes a comparison function to sort by, so we would write the same in Haskell as

sortBy (\x y -> getName x `compare` getName y) myList

But that's just on. So really it's

sortBy (compare `on` getName) myList

"Sort by comparison on name". It actually reads almost like English.

Now, for sorting in particular, this paradigm is so common that more recent versions of Haskell provide sortOn, which takes a Python-style key argument

sortOn getName myList

But there's a whole collection of "By" functions that work on lists, and the Haskell devs didn't write "On" variants for each of them.

Some examples:

-- Remove entries which have the same name as someone else
nubBy ((==) `on` getName) someList
-- Insert into a list sorted by salary, preserving the ordering
insertBy (compare `on` getSalary) newEmployee employees
-- Find the student with the highest grade
maximumBy (compare `on` getGrade) myStudents

So, generally, on will be used with a function whose name ends in "By".

Answer 3

Complementing the existing answers, from the viewpoint of some theoreticians, Haskell's Data.Function.on is an implementation of what some call the psi combinator. Quoting Smullyan^†:

A psi bird is a bird Ψ satisfying the condition Ψxyzw = x(yz)(yw)

---

_{† Raymond M. Smullyan, To mock a mockingbird, Oxford University Press, 2000.}

---

Related

• How can Data.Function's `on` function be generalized to work with n-ary functions?

• Implementing Smullyan's arithmetical birds in Haskell