Just to elaborate a bit, there is a function in batteries included that does exactly what you are looking for :
val group : ('a -> 'a -> int) -> 'a list -> 'a list list
group cmp l returns list of groups and each group consists of elements judged equal by comparison function cmp. Groups in the resulting list appear in order given by cmp. All groups are always nonempty. group returns [] only if l is empty.
For example group cmp [f;c;b;e;d;a] can give [[a;b];[c];[d;e;f]] if following conditions are met: cmp a b = 0, cmp b c = -1, cmp c d = -1, cmp d e = 0, ...
the cmp function you need is easy to implement :
let classify a1 a2 = match (a1, a2) with
| A _, A _ | B _, B _ | C, C | D, D -> 0
| A _, _ -> -1
| _, A _ -> 1
| B _, _ -> -1
| _, B _ -> 1
| C, D -> -1
| D, C -> 1
There may be some way to factorize that a bit more. Alternatively, you could use ppx_compare to handle the cases where identifiers are not equal :
type a = A of int | B of int list | C | D [@@deriving ord]
let classify a1 a2 = match (a1, a2) with
| A _, A _ | B _, B _ | C, C | D, D -> 0
| _ -> compare_a a1 a2
I guess Base have an equivalent solution to this problem but I am not aware of it.
EDIT :
Actually documentation does not explicitly guarantee that the original order is preserved inside each group and the given example actually does not preserve order… This is a weird design decision to be honest (even if reverting the loop may allow for a more efficient implementation). I just tried it on my machine :
List.group classify [A 3; B []; B [8; 9]; C; A 2; A 6];;
- : a list list = [[A 3; A 2; A 6]; [B []; B [8; 9]]; [C]]
So here order is preserved.