How to write a function in SML/NJ that sorts the elements from a list into equivalence classes?

I have to write a function in SML/NJ that sorts the elements from a list into equivalence classes. The order of elements inside each equivalence class should be the same as in the original list. The equivalence relation is given with a function f, which returns true, if two elements are equivalent.

The function should look like this:

fun equivalenceClasses (f: ''a * ''a -> bool, xs: ''a list): ''a list list

I can use only anonymous functions and the structures List, ListPair and Math.

I have no idea how to do it. Can somebody please help me?

Solution

Suppose I gave you a list of equivalence classes. Can you figure out how to insert one more element into that list?

For example, suppose the elements are strings and the equivalence classes are strings of equal length. Then the list [["fox","the","dog"],["brown","jumps"],["over","lazy"]] is a list of equivalence classes, because e.g. "fox" is the same length as "dog" and "brown" is the same length as "jumps", etc.

If we now insert the string "quick" into this list of classes, what should the result look like? Clearly it should be added to the list ["brown","jumps"], so perhaps the result looks like [["fox","the","dog"],["quick","brown","jumps"],["over","lazy"]]

Once you've solve that problem, the rest is easy. Here's a hint:

fun equivalenceClasses (f, xs) =
  case xs of
    [] => ???
  | x :: xs' => let
                  val c = equivalenceClasses xs'
                in
                  ???
                end