Inconsistent Range behavior when dealing with reverse ranges

[isomarcte]

I've noticed some inconsistencies with how several methods on Range and that use Range are defined when dealing with ranges which go different directions.

Range.contains

contains for Range is not symmetric around reverse.

scala> val a = Range(1, 10)
a: cats.collections.Range[Int] = Range(1,10)

scala> val b = a.reverse
b: cats.collections.Range[Int] = Range(10,1)

scala> a.contains(b)
res0: Boolean = true

scala> b.contains(a)
res1: Boolean = false

Perhaps most troubling,

scala> Range(1, 10).contains(Range(15, 9))
res0: Boolean = true

This is made more confusing when looking at how Range is used with Diet.

scala> val a = Range(1, 10)
a: cats.collections.Range[Int] = Range(1,10)

scala> val b = a.reverse
b: cats.collections.Range[Int] = Range(10,1)

scala> Diet.fromRange(b) === Diet.fromRange(a)
res0: Boolean = false

scala> Diet.empty.addRange(b) === Diet.fromRange(a)
res1: Boolean = true

There are a few ways to remedy this that come to mind, though I think the most simple would be to change Range to be defined as always going in one direction. If a Range is desired that is going in the inverse order, then an newtype (perhaps Inverse) could be used.

[satorg]

I would say it is by design: Range defines boundaries but not specify Order upon creation. Then every single method has to provide the Order implicitly for itself. In particular, both the contains methods take the implicit Order parameter. Therefore, if we reverse Range then the Order used for its methods has also be reversed:

scala> val rng1 = Range(1, 10)
rng1: cats.collections.Range[Int] = Range(1,10)

scala> rng1.contains(5)
res0: Boolean = true

scala> val rng2 = rng1.reverse
rng2: cats.collections.Range[Int] = Range(10,1)

scala> rng2.contains(5) // won't work since it uses a regular Order for Int
res1: Boolean = false

scala> rng2.contains(5)(Order.reverse(Order[Int]))
res2: Boolean = true

That said, I personally find such an approach controversial quite a bit.

[armanbilge]

Range defines boundaries but not specify Order upon creation. Then every single method has to provide the Order implicitly for itself.

Yes, this is one of the things I think we should consider changing for 1.0. See my comment in #277 (comment).

Indeed, this design was rejected for the new HashMap and HashSet, on grounds of be a "Haskell cargo-cult". So at the very least, this library now has inconsistent designs.

[satorg]

this is one of the things I think we should consider changing for 1.0

If we could change that, then perhaps it would be a cool change. Would we consider making Range to be not "all-inclusive" only? I mean, if we could create a Range instance having one or both boundaries that would be exclusive, then it would make this type way more useful.

[armanbilge]

See also some discussion in #315 (comment).

[isomarcte]

Just to clarify, are we saying that we intentionally want the usage of non-coherent instances to be normative? Like, we demand either Order[Int] or Order.reverse(Order[Int]) on Range creation as a design feature to change the ordering of the Range?

Using HashSet as an example, is this an intended usage?

scala> val sillyButValidHash: Hash[Int] = new Hash[Int] { override def hash(a: Int): Int = 1; override def eqv(x: Int, y: Int): Boolean = Eq[Int].eqv(x, y)}
sillyButValidHash: cats.Hash[Int] = $anon$1@1f21f982

scala> HashSet(1) === HashSet(1)(sillyButValidHash)
res0: Boolean = true

scala> HashSet(1).add(2) === HashSet(1)(sillyButValidHash).add(2)
res1: Boolean = false

scala> HashSet(1).add(2).iterator.toList === HashSet(1)(sillyButValidHash).add(2).iterator.toList
res2: Boolean = true

I personally would never want this to be intended behavior, as if I have more than one instance of HashSet[A] I completely lose the ability to reason about how they relate to each other, unless I've defined them in the same local scope.

I was under the impression that binding the instance at the method or at the class was mostly for convenience (and preventing damage to internal state of an already allocated structure) and not as a mechanism for using alternative instances. I would expect to use newtypes (ideally opaque types) to index alternative implementations.

[armanbilge]

The problem is if you take the instance at the call site then you can do this:

HashSet(1).add(2)(sillyButValidHash)

Which is also bad. Oscar just summarized this nicely in #277 (comment).

I still believe that in a language like scala where typeclasses are first class values and we don't have coherence, it doesn't make since to consume required typeclasses at callsites if using the wrong one invalidates the datastructure (which it does for hashmaps and trees with Hash and Order respectively).

[armanbilge]

I would expect to use newtypes (ideally opaque types) to index alternative implementations.

👍 yes, this is the only safe way.

[isomarcte]

👍 You scared me for a minute.

So coming back to Range. If we define ranges as intervals going in a single direction, then I think we can make the interface consistent and relatively easy to use. This would require the use of a newtype for reversing direction. I'm happy to POC that if there are no objections. It would also make the case for moving Inverse to cats-collections more compelling.

My intended strategy would probably be to introduce a new class Interval and deprecate Range.

Thoughts?

[armanbilge]

Sure, maybe Interval is a better name for the concept anyway.

[satorg]

@isomarcte I think there are two strategies possible:

1. As you suggested, to make a type that always uses a single direction and then create a newtype for the inverse directions.
   • PROS: (as I can see it) the direction is unified and alway apparent.
   • CONS: the range type and its inverse counterpart become two different types and thus cannot be compared to each other directly. I.e. we have to either implement separate methods for correlating those types or make a conversion before each comparison.
2. Another way could be to keep Range being bi-directional but latching its Order upon a new instance creation. Therefore, when we call .reverse we can also reverse the Order.
   • PROS: a single type that is "up" to be compared with a counterpart regardless of each other's direction.
   • CONS: the Range becomes more complex and has to maintain more complex structure rather than just boundaries.

Also as I mentioned above, I personally would find useful to have Range that could have non-inclusive boundaries, e.g. [0..10) which is similar to Scala's 0 until 10 .

All above is my personal perception of course.

[armanbilge]

Thanks for that distinction, at least for me I think that helped clarify things.

I think (1) is an "interval": it is a set of things, in some natural order. Whereas (2) is a "range" since you are not only specifying the set, but in which order to iterate it. I am not sure if that means we have to reverse the Order instance: the direction is a property of the "range", and not of its element. I think :)

[satorg]

I am not sure if that means we have to reverse the Order instance: the direction is a property of the "range", and not of its element.

In theory yes, it should not be the property of Range. But the way it is currently implemented is that Order is used to correlate the Range's boundaries with other items of the same type (including boundaries of another Range). Therefore, currently Order magically becomes a property of the Range itself. And yeah, I agree it should not be so...

[isomarcte]

@satorg RE 1.CONS

Assuming the inclusion of Inverse from the aforementioned PR, do you think something along these lines would work?

val a: Interval[Int] = Interval(1, 10)
val b: Interval[Inverse[Int]] = a.reverse

def reverse: Interval[Inverse[A]] = 
  Interval(Inverse(end), Inverse(start))
def contains(value: Interval[A]): Boolean = ???
def containsInverse(value: Interval[Inverse[A]]): Boolean = 
  contains(value.reverse)

// Just a rough sketch. I might be able to do something interesting so that
// (a: Interval[Inverse[A]]).reverse => Interval[A], and not
// Interval[Inverse[Inverse[A]]]
:t reverse 
Interval[A] => Interval[Inverse[A]]
:t contains 
Interval[A] => Interval[A] => Boolean
:t containsInverse
Interval[A] => Interval[Inverse[A]] => Boolean

And I'm completely fine making it exclusive on the upper bound. I think that would even be required, since if we require that start <= end, then the only want to define the empty interval is to have the upper bound be exclusive.

[isomarcte]

I can also just make a POC PR as well, if that would be easier for discussion.