What counts as distinct and consistent?

Question

There are some questions requiring distinct and consistent output. It's obvious what they mean for submissions printing to stdout. But how does that apply to the return values of functions?

For example, in Python, if a function always returns 1 for one case and "a" for another, we could say they are distinct and consistent. But what if it returned lambda:1? The problem is, (lambda:1) == (lambda:1) is false. And their string representations could change if run again.

If that shouldn't be acceptable, it would be difficult to justify how non-constant, non-static C strings are consistent, as they are technically pointers which may have different values even if the strings are the same.

If that should be acceptable, how should it be defined exactly? Someone could think it's a good idea to create two instances of a class to represent two different results. But in other cases, someone may prefer generating even the classes on the fly.

Should we have a standard for all cases or make it flexible? And what would be acceptable exactly?

If we use the simple approach to allow writing their own comparison functions, it would leave a loophole that they simply return the input and do everything in the comparison function.

Answer 1

Outputs are consistent if they are equal in the sanest and most obvious way of comparing them. For example, if you have two char * strings in C or C++, and you try

a == b

you will get a falsy value even if the strings are equal. But every half-decent C programmer knows that you don't compare strings with ==. That's the reason this SO question has almost 50,000 views at the time I'm writing this answer. Your python example is similar. For example:

(lambda: 1) == (lambda: 1)

is false. And comparing lambda functions by their string representation is completely nonsensical.

But it's still perfectly obvious that the two values are conceptually the same. They're both unnamed functions that return one. In fact, there's even a sane way to compare them. For example:

(lambda: 1)() == (lambda: 1)()

Now to be fair, this is a pretty flexible/laissez faire approach. It's pretty close to an "I know it when I see it" policy. But that's because this is mostly an edge case. I'm not aware of any cases where this little detail happens to matter, and I can barely think of any hypothetical cases where it would.

But if this wasn't accepted by default that you can choose the most obvious way of comparing return values, I can imagine pointless arguing like:

Well sure, a and b happen to have the same values in them. But so what? They're not in the same location!

(&a) == (&b)

is false, so technically you failed all of the test-cases.

which is clearly ridiculous.

Answer 2

For a result to be consistent, it must belong to a type that's comparable

Integers are possible to compare consistently. Strings are possible to compare consistently (you can do it character by character). In general, anything that can be represented as a simple recursive data structure (think a Lisp list) can be compared simply via iterating over it recursively. These are known as comparable types; languages with particularly advanced type systems often have an interface, typeclass, or equivalent that marks the type as possible to compare. For example, Haskell has Eq. (Note that the comparison is typically not done with == or the equivalent, but rather requires a function to compare; in Java, strings (and every other reference type, for that matter) are compared with .equals().)

Although the majority of types are comparable (PPCG problems normally use strings, integers, and lists of other types that are used), there are some types that inherently aren't. Most notably, functions are mathematically impossible to compare, at least in a Turing-complete language. Languages with strong enough type systems are aware of this. Here's what happens if I try the example in the OP in Haskell:

Prelude> (\() -> 1 :: Integer) == (\() -> 1 :: Integer)

<interactive>:8:23:
    No instance for (Eq (() -> Integer))
      (maybe you haven't applied enough arguments to a function?)
      arising from a use of ‘==’
    In the expression: (\ () -> 1 :: Integer) == (\ () -> 1 :: Integer)
    In an equation for ‘it’:
        it = (\ () -> 1 :: Integer) == (\ () -> 1 :: Integer)

So, if an answer belongs to a comparable type, we can determine if it's consistent by comparing all the output values to see if they're equal. If it doesn't, I suspect it can't be consistent by definition.

Note that in some cases, an output may be consistent in a less powerful language even though it's inconsistent in a more powerful language; for example, a language in which all functions are deterministic and always terminate, and in which all base types had finitely many values, would make it possible to compare first-order functions by verifying that they had the same behaviour for all possible arguments (something that can't be done in general because you can't compare the nontermination behaviour of functions due to the halting problem).