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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Formal language design? Do you mean "design of programming lanaguges" or "theory of formal languages"? $\endgroup$
    – Andrej Bauer
    Commented Jan 11, 2021 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
    Commented Jan 11, 2021 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. ♦
    Commented Jan 11, 2021 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
    Commented Jan 12, 2021 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. ♦
    Commented Jan 12, 2021 at 17:27

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Jan 11, 2021 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
    Commented Jan 11, 2021 at 9:25
  • $\begingroup$ @TendersMcChiken: [u,b] was a typo, I fixed it. $\endgroup$
    – Andrej Bauer
    Commented Jan 11, 2021 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
    Commented Jan 11, 2021 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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