5 ms·

The subset relation is defined as "X is a subset of Y if for all x in X, x is in Y". The negation of this is "X is not a subset of Y if there exists some x in X

The subset relation is defined as "X is a subset of Y if for all x in X, x is in Y". The negation of this is "X is not a subset of Y if there exists some x in X, such that x is not in Y". We can see from this that the empty set is NOT NOT a subset of every set. Therefore the empty set is a subset of every set. A similar argument should show that the empty string is a substring of every string. Therefore indexOf(substring, string) should return a non-negative index if substring is the empty string. This reminds me of a discussion on HN a while ago about predicates over the empty set. There was debate over whether "all(x == "foo" for x in my_array)" should evaluate to True or False if my_array is empty. I tried to point out that if it evaluated to False, it would break first order logic in a similar way as I explained above, but people were still trying to argue the opposite case.

adrian_b 3y ago
While an empty substring is a substring of every string, attempting to find its index in any string must signal an error, because there is no univocal value of such an index (all possible index values are equally valid answers). On the other hand, a predicate that tests whether an empty substring is found in a string must indeed return "true". In a function that must return a single value, an error must be signaled both when there is no value that can be returned and when there are multiple values that could be returned. If the index of the substring is defined as the smallest such index, which makes it unique even for multiple substring occurrences, then the search function must return 0 or 1 for an empty substring, whichever is defined to be the first index. Attempting to search an empty string for non-empty or empty substrings should always signal an error, because there are no valid index values that could be returned.
- fasterik 3y ago
  Yeah, I think the convention should be to return the smallest valid index such that the predicate is satisfied, or an error value if the predicate isn't satisfied. As you point out, it's the same as when a non-empty string appears multiple times in a given string. So I think 0 is the only reasonable result in this case, assuming 0-based indexing.
- deleted 3y ago
  [deleted]
- hermitcrab 3y ago
  >While an empty substring is a substring of every string, attempting to find its index in any string must signal an error, because there is no univocal value of such an index (all possible index values are equally valid answers). The operations in question are to find the first (IndexOf) and last (LastIndexOf) indexes. So if the empty exists at every index, you just return the first or last one. >Attempting to search an empty string for non-empty or empty substrings should always signal an error I believe that an empty string is valid input for each parameter and should return 'not found' in some form, rather than an error. It is splitting hairs a bit though.
bryancoxwell 3y ago
What reason could there possibly be for looking for an empty string?
- tharkun__ 3y ago
  Because the string you are trying to find is in some variable which at runtime in some cases for some reason happens to be an empty string and you don't (want to) special case this and just "let it work by itself"?
- fasterik 3y ago
  There are many cases where a user-provided string is passed to the string API. Generally the programmer should handle empty strings as a special case, but when they don't the API needs to return something.
  - bryancoxwell 3y ago
    Thanks!
- ajuc 3y ago
  Avoiding the need to special-case empty input.
- hermitcrab 3y ago
  Is it a sensible thing to do: No. Will users do it anyway: Yes. We have to handle all possible values the user can provide.
tzs 3y ago
> The subset relation is defined as "X is a subset of Y if for all x in X, x is in Y". This might be a bit nit picky, but shouldn't that be "if and only if" or "iff" instead of just "if"? > The negation of this is "X is not a subset of Y if there exists some x in X, such that x is not in Y". We can see from this that the empty set is NOT NOT a subset of every set. In what follows I'm replacing lower case x with lower case e. I'm kind of simple minded, so find that a bit confusing because of using the negated definition and a double not, and also "for all e in X" when X is the empty set because it makes you have to keep for the rest of the definition that e might be nonexistent. This is clearer to me: 1. Rewrite the definition so it is in terms of all e, not all e in X: "X is a subset of Y if and only if for all e, e is in X implies e is in Y". This form of the definition only talks about elements that exist. 2. "e is in X implies e is in Y" is equivalent to "e is not in Y implies e is not in X", which gives us this equivalent definition: "X is a subset of Y if and only if for all e, e is not in Y implies e is not in X". 3. When X is the empty set it is always the case that e is not in X, and so "e is not in Y implies e is not in X" is always true (because both false implies true and true implies true are true), and so X is a subset of Y by the definition of subset.

adrian_b 3y ago

While an empty substring is a substring of every string, attempting to find its index in any string must signal an error, because there is no univocal value of such an index (all possible index values are equally valid answers). On the other hand, a predicate that tests whether an empty substring is found in a string must indeed return "true". In a function that must return a single value, an error must be signaled both when there is no value that can be returned and when there are multiple values that could be returned. If the index of the substring is defined as the smallest such index, which makes it unique even for multiple substring occurrences, then the search function must return 0 or 1 for an empty substring, whichever is defined to be the first index. Attempting to search an empty string for non-empty or empty substrings should always signal an error, because there are no valid index values that could be returned.

fasterik 3y ago
Yeah, I think the convention should be to return the smallest valid index such that the predicate is satisfied, or an error value if the predicate isn't satisfied. As you point out, it's the same as when a non-empty string appears multiple times in a given string. So I think 0 is the only reasonable result in this case, assuming 0-based indexing.
deleted 3y ago
[deleted]
hermitcrab 3y ago
>While an empty substring is a substring of every string, attempting to find its index in any string must signal an error, because there is no univocal value of such an index (all possible index values are equally valid answers). The operations in question are to find the first (IndexOf) and last (LastIndexOf) indexes. So if the empty exists at every index, you just return the first or last one. >Attempting to search an empty string for non-empty or empty substrings should always signal an error I believe that an empty string is valid input for each parameter and should return 'not found' in some form, rather than an error. It is splitting hairs a bit though.

bryancoxwell 3y ago

What reason could there possibly be for looking for an empty string?

tharkun__ 3y ago
Because the string you are trying to find is in some variable which at runtime in some cases for some reason happens to be an empty string and you don't (want to) special case this and just "let it work by itself"?
fasterik 3y ago
There are many cases where a user-provided string is passed to the string API. Generally the programmer should handle empty strings as a special case, but when they don't the API needs to return something.
- bryancoxwell 3y ago
  Thanks!
ajuc 3y ago
Avoiding the need to special-case empty input.
hermitcrab 3y ago
Is it a sensible thing to do: No. Will users do it anyway: Yes. We have to handle all possible values the user can provide.

tzs 3y ago

> The subset relation is defined as "X is a subset of Y if for all x in X, x is in Y". This might be a bit nit picky, but shouldn't that be "if and only if" or "iff" instead of just "if"? > The negation of this is "X is not a subset of Y if there exists some x in X, such that x is not in Y". We can see from this that the empty set is NOT NOT a subset of every set. In what follows I'm replacing lower case x with lower case e. I'm kind of simple minded, so find that a bit confusing because of using the negated definition and a double not, and also "for all e in X" when X is the empty set because it makes you have to keep for the rest of the definition that e might be nonexistent. This is clearer to me: 1. Rewrite the definition so it is in terms of all e, not all e in X: "X is a subset of Y if and only if for all e, e is in X implies e is in Y". This form of the definition only talks about elements that exist. 2. "e is in X implies e is in Y" is equivalent to "e is not in Y implies e is not in X", which gives us this equivalent definition: "X is a subset of Y if and only if for all e, e is not in Y implies e is not in X". 3. When X is the empty set it is always the case that e is not in X, and so "e is not in Y implies e is not in X" is always true (because both false implies true and true implies true are true), and so X is a subset of Y by the definition of subset.