Lazy Grouping

This task is about implementing a groupOn function.

>>> groupOnOrd head ["cat", "car", "apple", "croissant", "battery"]
[('c',["cat","car","croissant"]),('a',["apple"]),('b',["battery"])]

The function you need to implement is called groupOnOrd :: Ord k => (a -> k) -> [a] -> [(k,[a])]. Given a "key" function, which generates the key for each group, your function should put each of the elements of the input list into a list paired with its key. This function should obey some properties:

• The order of the groups in the output list should be the same as the order in the input. For instance, above 'c' is encountered first, so it is the first group.
• There should be no duplicate groups. Again, using the above output as an example, even though "croissant" is disjoint from "cat" and "car", it is put in the same group as them because it starts with the same letter.

Your solution should be fully lazy. That means that the following should be well defined:

>>> map fst . groupOnOrd id $ [1..]
[1..]

>>> groupOnOrd id $ cycle [1,2,3]
(1,repeat 1):(2,repeat 2):(3,repeat 3):⊥

>>> groupOnOrd (`rem` 3) [1..]
(1,[1,4..]):(2,[2,5..]):(0,[3,6..]):⊥

Finally, while all of the properties above can be satisfied by implementing a function with just an Eq constraint, in order for your function to be efficient you will have to make use of Ord somehow.