1
$\begingroup$

Depending on the API/language you use, splitting the string "ABCD" using "" as a delimiter gets you:

  • ["A", "B", "C", "D"] in Java, Javascript, and Go
  • ["", "A", "B", "C", "D", ""] in Rust
  • ["ABCD"] in C#
  • Fails with an Exception in Python3

From the perspective of formal language design, what is the correct result of such an operation? Is it defined?

Disclosure: This question was posted at stack overflow but was closed as opinion-based. I was directed to post my question here instead.

$\endgroup$
5
  • $\begingroup$ Formal language design? Do you mean "design of programming lanaguges" or "theory of formal languages"? $\endgroup$ – Andrej Bauer Jan 11 at 8:41
  • $\begingroup$ I am not familiar with formal languages theory at all so I would go with the former. I used the word Formal here in an attempt to convey "Well-definedness" and coherency with other string functions. In hindsight, my adding the formal-languages tag was probably a mistake. $\endgroup$ – Tenders McChiken Jan 11 at 9:04
  • $\begingroup$ It seems opinion-based to me too. I'm not sure why moving it to a different site would change that conclusion. The question contains a premise that there is a single correct result but I don't think that premise is accurate. You can define it any way you want. $\endgroup$ – D.W. Jan 11 at 18:08
  • $\begingroup$ @D.W. I'm very lousy at presenting questions: What I was asking for is 1) whether a single canonical result for splitting strings by an empty string has been formally defined, and 2) what is it if has been. I'm not asking people to give me their opinion on how a canonical result should look like. Your (and @Andrej's) answer that no such canonical result has been defined is a completely valid and (imho) objective answer. That said, all this confusion is entirely my fault. I apologize for my poorly wording my questions. $\endgroup$ – Tenders McChiken Jan 12 at 14:10
  • $\begingroup$ That's the great thing about definitions: you can define anything you want. In this case I expect which is the best or "canonical" of these definitions is likely to be a matter of opinion. $\endgroup$ – D.W. Jan 12 at 17:27
1
$\begingroup$

Given sequences $A = [a_1, \ldots, a_n]$ and $B = [b_1, \ldots, b_m]$, write $A + B = [a_1, \ldots, a_n, b_1, \ldots, b_m]$ for their concatenation. Given a sequence of sequences $C = [C_1, \ldots, C_n]$, write $\Sigma(C) = C_1 + \cdots + C_n$ for their concatenation.

Define a splitting of a sequence $X$ by a sequence $Y$ to be a sequence of sequences $Z = [Z_1, \ldots, Z_k]$ such that $Z_i \neq Y$ and $Z_i \neq []$ for all $i = 1, \ldots, k$, and $$X = \Sigma [Z_1, Y, Z_2, Y, z_3, \ldots, Y, Z_k].$$

For example, $[[a], [], [b, c]]$ is a splitting of $[a, u, v, u, v, b, c]$ by $[u, v]$.

Splitting by the empty sequence is not unique: $[a, b, c]$ may be split by $[]$ in several ways, among others $[[a],[b],[c]]$, $[[a,b], [c]]$ and $[[a,b,c]]$. From a theoretical point this is a rather trivial and non-interesting observation. The implementors of various string libraries need to deal with splitting by the empty sequence somehow, and as you show, they do.

$\endgroup$
4
  • $\begingroup$ So having a single canoncial result for this operation doesn't make sense. All results are equally correct as long as joining the segments together yields the original string. Got it. $\endgroup$ – Tenders McChiken Jan 11 at 9:17
  • $\begingroup$ I do have two small questions about your answer: According to your definition of the split operation, wouldn't Rust's implementation be incorrect since it yields Z[i] = Y? Also, in your example bellow the definition, did you mean to express the Y as [u,b] or [u,v]? Apologies if these questions are nonsensical. I don't have much experience in the field of Computer Science. $\endgroup$ – Tenders McChiken Jan 11 at 9:25
  • $\begingroup$ @TendersMcChiken: [u,b] was a typo, I fixed it. $\endgroup$ – Andrej Bauer Jan 11 at 14:01
  • 1
    $\begingroup$ @TendersMcChiken: I included the conditions $Z_i \neq Y$ and $Z_i \neq []$ so that the splitting is unique in case $Y \neq []$. If you drop those conditions, then you get many more splittings. For example $[[a, u, v], [b, c]]$ and $[[], [], [], [a], [], [b, c]]$ would both be splittings of $[a, u, v, u, v, b, c]$ by $[u, v]$. I don't know what the Rust designeres where thinking. I would guess they were not thinking about the border-line cases, unless there is something in the documentation indicating otherwise. $\endgroup$ – Andrej Bauer Jan 11 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.