Just one note, part of the difference in behaviour between String.split and Str.split_delim can be captured by the fact that for any sep and s in which sep does not occur, String.split guarantees the following:

assert (String.split sep sep = [""; ""])
assert (String.split sep s = [ s ])

whereas Str.split_delim has different behaviour whenever either s or sep is the empty string in these cases.

While I trust you that the code is correct, I found the addition particularly hard to proofread given that there is absolutely no comment in the file. Could you either describe here the algorithm you're implementing or add a few comments here and there to say what i, k and others do? (Granted, I'm playing the naive guy, I do have a rough idea of what these variables do, but I still think it would help your chances of being integrated.)

Thanks!

With my library designer hat, I can confirm that this is the right design for a split function. I have written a full blog post about it last summer, which I somehow forgot to publish. An invariant which you could emphasize more is that the returned list of strings is always nonempty -- some implementations of split get it wrong and have split sep "" = [].

I haven't looked at the code, and I have no opinion as to whether that should go into stdlib.

I have no view on the code, but the invariant mentioned in the documentation is the invariant I use with split-like functions, so I also think this is the right design. With gasche, I also make use of the second invariant.

In general, I would like to see more functions in stdlib, providing there is general agreement over the specification, the name, the order of arguments etc. (perhaps I am too optimistic?)

What about exposing functions to search for the first or last occurrence (within a given range) of a substring? split can be implemented quite trivially on top of them, and they are useful on their own.

(One argument against this approach is that a general purpose "search substring" algorithm could be well served by a more clever algorithm (KMP or Boyer-Moore), but this might be counter-productive for their use in 'split', where the delimiter is typically very short.)

@protz I tried to follow the programming guidelines... joke apart I did add some comments but it's still hard to figure out that all edges cases are well treated. @gasche added that invariant to the doc.

In fact, I spoke too fast. An edge case of an edge case is slightly wrong in this patch.

When I wrote my comment, I thought that the non-emptiness invariant was implied by the invariants Daniel asserted, as concat sep (split sep s) = s forces the return list to be non-empty whenever s is non-empty. When s is empty, concat sep "" is specified to return [""] whenever "" "does not contain" sep. But this leaves the split "" "" unspecified. It is still underspecified if you additionally require that it be non-empty.

I think the return value of split "" "" should be either an error or [""] (my preference), but not [""; ""].

@gasche A little bit hard to follow you but "" is a substring of "" so this property mentioned above

assert (String.split sep s = [ s ])

if sep is not in s shall not apply. Now it seems you prefer to have split "" "" = [""], but this would be an exception to the rule that for any sep:

assert (String.split sep sep = [""; ""])

My reasoning is the following: if you split s1 and s2 among the same separator sep, you can merge back the splitting results as follows (relying on the non-emptyness invariant): if split sep s1 is of the form left @ [last], split sep s2 is of the form [first] @ right, then split sep (s1 ^ s2) is equal to left @ (split sep (last ^ first)) @ right.

This is coherent with split sep s = [s] when sep is not in s, with split sep sep = [""; ""] when sep is not empty (this gives split sep (sep^sep) = [""; ""; ""] as expected), but doesn't work if split "" "" is anything else than [""]. More generally, it casts doubt over your treatment of split "" s.

Just mentioning in case this matters: the behavior does not seem to be specified by the disucssed invariants in the case where the delimiter string can overlap with itself (e.g. split "aaa" "aa").

@alainfrisch you meant split "aa" "aaa". You are right, we need to specify matching algorithm more clearly: starting from the beginning of the string looks for sep and then cuts. The current implementation is wrong in my eyes (I'm doing the matching from the end to avoid a List.rev. I will change that.

@gasche Interesting, I just note however that if you compare the resulting concatenation of the string, you get the same string i.e:

String.concat sep ((String.split sep s1) @ (String.split sep s2)) = 
String.concat (String.split sep (s1 @ s2))

Besides note that with the current implementation the property you mention doesn't hold for any s in split "" s. Just to make things clear here's an example:

# let s1 = split "" "12";;
val s1 : string list = [""; "1"; "2"; ""]
# let s2 = split "" "34";;
val s2 : string list = [""; "3"; "4"; ""]
# split "" "1234";;
- : string list = [""; "1"; "2"; "3"; "4"; ""]
# [""; "1"] @ split "" "23" @ ["4"; ""];;
- : string list = [""; "1"; ""; "2"; "3"; ""; "4"; ""]

So either:

1. I keep it as it is now.
2. I fix split "" s so that split "" "" = [""] and split "" s has no leading and trailling empty string.
3. Require sep to be non empty.

My gripe with 2. is that it treats "" specially w.r.t. to how split works with other non empty separator. 2. would be fine with me if leading and trailing seps would not generate empty strings, i.e. if we had for all sep and s with sep not in s:

assert (String.split sep sep = [""]); (* rather than ["",""] as it is now *)
assert (String.split sep (sep ^ s) = [s]); (* rather than ["", s] as it is now *)
assert (String.split sep (s ^ sep) = [s]); (* rather than [s, ""] as it is now *)

But we would loose the round trip with String.concat so I prefer not.

I tend to be in favor of 3. what do you think ? Spliting with the empty string seems a bad idea anyway especially since, as we see, can be filled with misunderstandings. What do you think ?

The round-trip to concat is an absolute requirement. I agree that either (2) or (3) are acceptable.

My suspicion is that users would find split "" "abc" = ["a"; "b"; "c"] a useful behavior in many situations, and it doesn't break the natural contracts for the function, so I would be tempted to accept it. You could always fail specifically in the split "" "" case.

Another way to find peace as an obsessive API designer is to let the code speak: find a way to write the function that seems simple (even better, "elegant"), and respect the way it handles edge cases. Your treatment of empty separators in the current implementation is a bit ad-hoc, but maybe another implementation could "explain" by its conciseness how splitting on empty strings should be done.

How often do we need to split with anything else than a single character? Treating only this case makes it easy to specify the exact behavior and leads to a more efficient implementation.

Actually the "restricted version" of Split.string I was talking about did only that and sure it was much simpler... But one of the advantage of having a string is that you could still split utf-8 strings at a given UTF-8 encoded char.

I gave up on 2. failing to be able to give a reasonable, terse, explanation. I updated my PR with 3.

Also I now do the match from beginning to end. I tried to explain the match strategy in the doc to make it clear that matches don't overlap and run from start to end. So here are the properties of what is currently implemented (I added @alainfrisch's overlapping example):

let () = 
  assert (try ignore (String.split "" ""); false with Invalid_argument _ -> true); 
  assert (try ignore (String.split "" "123"); false with Invalid_argument _ -> true);
  assert (String.split "," "" = [""]); 
                       (* Str = [] *) 
  assert (String.split "," "," = [""; ""]); 
  assert (String.split "," ",," = [""; ""; ""]); 
  assert (String.split "," ",,," = [""; ""; ""; ""]); 
  assert (String.split "," "123" = ["123"]); 
  assert (String.split "," ",123" = [""; "123"]);
  assert (String.split "," "123," = ["123"; ""]); 
  assert (String.split "," "1,2,3" = ["1"; "2"; "3"]); 
  assert (String.split "," "1, 2, 3" = ["1"; " 2"; " 3"]); 
  assert (String.split "," ",1,2,,3," = [""; "1"; "2"; ""; "3"; ""]);
  assert (String.split "," ", 1, 2,, 3," = [""; " 1"; " 2"; ""; " 3"; ""]);
  assert (String.split "<>" "" = [""]); 
                        (* Str = [] *) 
  assert (String.split "<>" "<>" = [""; ""]);
  assert (String.split "<>" "<><>" = [""; ""; ""]);
  assert (String.split "<>" "<><><>" = [""; ""; ""; ""]);
  assert (String.split "<>" "123" = [ "123" ]);
  assert (String.split "<>" "<>123" = [""; "123"]);
  assert (String.split "<>" "123<>" = ["123"; ""]);
  assert (String.split "<>" "1<>2<>3" = ["1"; "2"; "3"]);
  assert (String.split "<>" "1<> 2<> 3" = ["1"; " 2"; " 3"]);
  assert (String.split "<>" "<>1<>2<><>3<>" = [""; "1"; "2"; ""; "3"; ""]);
  assert (String.split "<>" "<> 1<> 2<><> 3<>" = [""; " 1"; " 2"; ""; " 3";""]);
  assert (String.split "<>" ">>><>>>><>>>><>>>>" = 
          [">>>"; ">>>"; ">>>"; ">>>" ]);
  assert (String.split "<->" "<->>->" = [""; ">->"]);
  assert (String.split "aa" "aa" = [""; ""]); 
  assert (String.split "aa" "aaa" = [""; "a"]);
  assert (String.split "aa" "aaaa" = [""; ""; ""]);
  assert (String.split "aa" "aaaaa" = [""; ""; "a"]);
  assert (String.split "aa" "aaaaaa" = [""; ""; ""; ""]);
  ()

I think a good case can be made for (3) if you read the current description of the matching procedure in the documentation. You cannot skip the empty separator --- its length is 0 --- so it makes no sense to have an empty separator, the matching procedure would loop.

In general, I would like to see more functions in stdlib, providing there is general agreement over the specification, the name, the order of arguments etc. (perhaps I am too optimistic?)

In extlib :

split : string -> string -> (string * string)
nsplit : string -> string -> string list

and the order of arguments is reversed..

PS Having the invariants being discussed here is surely nice

@ygrek I never found extlib to be particularly well designed, so I'm not sure it should be taken as an example:

• Having the argument reversed is not what you want in the average case. I guess it must come from dogma that the main "object" should be the first argument, which is a wrong dogma in a language with currying. You want to write List.rev_map (String.split ",") (lines file) and not List.rev_map (fun s -> String.split s ",") (lines file).
• A case could be maybe made for the name, but I note that if you look at perl, ruby, python, racket, scala, javascript to name a few, all have that function named split

• Having the argument reversed is not what you want in the average case. I
  guess it must come from dogma that the main "object" should be the first
  argument, which is a wrong dogma in a language with currying. You want to
  write List.rev_map (String.split ",") (lines file) and not List.rev_map
  (fun s -> String.split s ",") (lines file).

Since the two arguments have the same type, it would be good that the
separator be labeled.

val split : sep:string -> string -> string

@Chris00, agreed but my understanding of the stdlib is that the String module shall have no labels and StringLabels have them, that's what my patch does.

I gave up on 2. failing to be able to give a reasonable, terse, explanation. I updated my PR with 3.

Same with me. The code really says sep = "" should return an infinite list of empty strings, so forbidding it is more reasonable.

My point was about "agreed upon" names and conventions, should probably also take batteries into account. Proposed design is no doubt superior.

Indeed, using nsplit would make life easier for extlib or batteries user.

I'm not sure it's a good idea to take into account what these extended libraries do. Since there are many of them and they don't agree on their names, we can say that their names are not necessarily the "agreed upon" names. For example js core's split is this split but restricted to char separators. I think that the fact that every other programming language out there uses split for that function is a quite good argument.

Also if we agree that the argument order of this split is the right one, using nsplit would actually be more confusing and error prone to extlib or batteries users.

A split that would be quite more useful to me would take a function as a splitter rather than a string (or a char).

Although I have no hope at all that it will ever make it to stdlib, please let me share with you my idea of a far more powerful design (however it probably has poor performance compared to classic split functions for classic cases):

let split f s =
  let res = ref [] in
  let b = Buffer.create 42 in
  let rec loop i s =
    if i >= String.length s then
      let bc = Buffer.contents b in
      Buffer.clear b;
      res := bc :: !res;
    else
      match f i s with
      | `Split ->
         let bc = Buffer.contents b in
         Buffer.clear b;
         res := bc :: !res;
         loop (i+1) s
      | `Continue ->
         Buffer.add_char b (s.[i]);
         loop (i+1) s
      | `Split_with (add, new_i, new_s) ->
         Buffer.add_string b add;
         let bc = Buffer.contents b in
         Buffer.clear b;
         res := bc :: !res;
         loop new_i new_s
  in
  loop 0 s;
  List.rev !res
(* val split :
   (int ->
   string -> [< `Continue | `Split | `Split_with of string * int * string ]) ->
   string -> string list *)

let _ = (* split on " " *)
  split (fun i s -> match s.[i] with ' ' -> `Split | _ -> `Continue) "hello foo bar"
(* ["hello"; "foo"; "bar"] *)

let _ = (* split on "foo" *)
  split
    (fun i s ->
       if String.length s > i+3 && String.sub s i 3 = "foo" then
         `Split_with ("", i+3, s)
       else `Continue)
    "hello foo bar"
(* ["hello "; " bar"] *)

let split_on_string sep s =
  if sep = "" then invalid_arg "split_on_string";
  let ls = String.length sep in 
  split
    (fun i s ->
       if String.length s > i+ls && String.sub s i ls = sep then
         `Split_with ("", i+ls, s)
       else `Continue)
    s
(* val split_on_string : string -> string -> string list *)

let _ =
  split_on_string "foo" "hello foo bar baz"
(* ["hello "; " bar baz"] *)

let _ =
  split_on_string "foo" ""
(* [""] *)

let _ =
  split_on_string "" ""
(* Exception: Invalid_argument "split_on_string". *)

let split_on_spaces s =
  split
    (fun i s ->
       match s.[i] with
       | ' ' ->
         let rec loop i =
           if String.length s > i && s.[i] = ' ' then
             loop (i+1)
           else
             `Split_with("", i, s)
         in loop i
       | _ -> `Continue 
    )
    s
(* val split_on_spaces : string -> string list *)

let _ = split_on_spaces "plop                plop          "
(* ["plop"; "plop"; ""] *)

let split_sentences s =
  split
    (fun i s ->
       match s.[i] with
       | '.' | '!' | '?' ->
         let b = Buffer.create 42 in
         let rec loop i =
           if String.length s > i then
             match s.[i] with
             | '.' | '!' | '?' | ' ' ->
               Buffer.add_char b s.[i];
               loop (i+1)
             | _ ->
               `Split_with(Buffer.contents b, i, s)
           else
             `Split_with(Buffer.contents b, i, s)
         in loop i
       | _ -> `Continue)
    s
(* val split_sentences : string -> string list *)

let _ = split_sentences "Bonjour, comment ça va?! Ça va. Merci. Au revoir! Déjà?? Oui!!"
(* ["Bonjour, comment ça va?! "; "Ça va. "; "Merci. "; "Au revoir! "; "Déjà?? "; "Oui!!"; ""] *)

@dbuenzli: regarding "you could still split utf-8 strings at a given UTF-8 encoded char", this is also true with a single char delimiter, as long as the delimiter is actually a ASCII character. I believe it is by far the most common case even when manipulating utf-8 strings. Considering the advantages of the simple version (simpler and more efficient implementation, simple specification, no risk of confusing the two arguments), I think I'd be in favor of that one.

Another useful function would a "split2", which splits a string in two at the first occurrence of a delimiter.

@alainfrisch There are quite a few unicode delimiters (for example the unicode line or paragraph separators (U+2028, U+2029), or the various dashes) that are well beyond the ASCII repertoire. I still think that having a sequence of bytes for delimiters is a good thing to have (I'll again invoke the argument of other programming languages which all allow you to split with a string). I think the current specification I gave in the documentation is not hard to comprehend; if you don't think so please tell how it can be improved.

Regarding split2 which I would rather call cut or something like this, we can sure add a lot of things (e.g. rsplit, that would try to match from the end). However I'm just trying to make one single addition in the very lean and conservative (which I actually see as a virtues) standard library that I miss very much without trying to open a pandora box. I'd rather have only that one in than proposing much more but get everything rejected.