Generalization of Seq.group

[favonia]

The Seq.group function introduced by #10583 (and also Haskell's group) has the following behavior where elements are compared against the first element in each group instead of their adjacent elements: (I will write Seq.t in the list notation.)

group (fun x y -> y - x < 2) [0;1;2;4] = [[0;1];[2];[4]] (* because 1-0 < 2 but 2-0 = 2 *)
group (<) [0;1;2;1;2;3] = [[0;1;2;1;2;3]] (* because 0 is the smallest *)

However, I feel this is not very useful. I would hope that the predicate was used on immediately adjacent pairs. That is,

group (fun x y -> y - x < 2) [0;1;2;4] = [[0;1;2];[4]] (* because 1-0 < 2 and 2-1 < 2 *)
group (<) [0;1;2;1;2;3] = [[0;1;2];[1;2;3]] (* because 0 < 1 < 2 and 1 < 2 < 3 *)

When the functional argument is an equality, the two behaviors will agree, and when they do not agree, I believe the second behavior is more useful. The current specification says nothing about non-equality arguments, so this feature request is a generalization. The downside is that this will depart from the corresponding function in Haskell. I am tagging @c-cube and @fpottier for their original contribution in #10583.

[c-cube]

I don't see why not personally, since it shouldn't come at a performance cost and doesn't change anything for predicates that work on equivalence classes (like equality), and assuming it's thoroughly documented :)

[fpottier]

Hi! This sounds possibly OK, but I would like to see what new definition of group you suggest. Currently group is defined in terms of take_while and drop_while; I assume that this would have to change, and that we would have to define new variants of take_while and drop_while. I can imagine that the call take_while (eq x) xs would be replaced with a call of the form take_while_eq eq x xs, and similarly for drop_while, but I have not looked into the details.

I note that we seem to have no test of the function group in the file testsuite/tests/lib-seq/test.ml; this is something that we will want to remedy, especially if we change the definition of group.

[favonia]

I assume it would be something like this (NOT tested):

let rec take_adjacent p x xs () =
  match xs() with
  | Nil ->
      Nil
  | Cons (y, ys) ->
      if p x y then Cons (x, take_adjacent p y ys) else Nil

let rec drop_adjacent p x xs () =
  match xs() with
  | Nil ->
      Nil
  | Cons (y, ys) as node ->
      if p x y then drop_adjacent p y ys () else node

let rec group p xs () =
  match xs() with
  | Nil ->
      Nil
  | Cons (x, xs) ->
      Cons (cons x (take_adjacent p x xs), group p (drop_adjacent p x xs))

[fpottier]

Indeed, this seems to be what I had in mind.

[favonia]

What should we discuss now? No one seems to object to this feature request. Unfortunately, I would not have time to make a PR in the next several weeks, but it seems the PR should involve:

1. Something equivalent to the code I showed above.
2. Test cases for the group function.

Did I miss something?

[fpottier]

An extension of the documentation of the function group.

Also, perhaps we should decide whether the auxiliary functions take_adjacent and drop_adjacent should be public or private.

[favonia]

I prefer not to make those auxiliary functions public yet---at least I don't feel my code above has a nice interface. I might wish to have List.group mimicking Seq.group, though.