remove Discrete typeclass in favor of one of the cats Enumerable typeclasses

[johnynek]

see:

https://github.com/typelevel/cats/blob/master/kernel/src/main/scala/cats/kernel/Enumerable.scala

I don't know the minimal thing we are using, maybe Previous and Next or PartialPrevious and PartialNext would be enough.

It would be nice to remove Discrete and standardize on the cats versions.

[ashleymercer]

Have taken a bit of a look at this today as part of the LSUG day, and it turned out to be a bit bigger than I expected!

I think the correct approach is to remove Discrete and use cats BoundedEnumerable instead, since this correctly models types which have a finite domain. I have a couple of questions which need answering please @larsrh before I can proceed :)

(Aside: there's a missing BoundedEnmerable[Byte] instance, I'll make a PR to cats to add this)

Discrete currently wraps around (sorry, Lars, my original reading of this was correct after all).

BoundedEnumerable is more explicit about this: you can either get partialPrevious/Next as Option[Int], or you can explicitly allow wrapping (cyclePrevious/Next); I think wrapping is (almost?) never what we're likely to want so we'll need to decide the behaviour in each case:

• for Range I should be able to work it out. The one question I had was Range.toIterator, which seems to allow the range to run backwards if start > end (this would be equivalent to a scala.Range with a negative step size). Is this intentional? If it's allowed, it has implications for other places where we check bounds, since I think they often assume the range is running forwards. I assume Range should not be allowed to wrap? [1]

• I'm not massively familiar with Diet as a data structure but again it looks like I should be able to figure it out, assuming you're happy with the behaviour that the most extreme nodes are bounded to the min/max value of the key type (i.e. again no wrapping)?

• as discussed I think we can do without the adj method altogether - it's only used in one place (when stitching Ranges together)

• inverse might be generally useful but isn't provided by cats out of the box - do you think it's worth asking to add it there? Or should I just add it as an extension method in cats-collections?

[1] It would arguably be more general to allow Range which did wrap (e.g. "produce all negative integers down to Int.MinValue then wrap to Int.MaxValue and continue) but that's probably a lot harder to write, and I'm not sure I can think of many cases where it would actually be useful...

[ashleymercer]

Some more colour on Range: I think this test (and others like it) should pass but currently don't. Should this be the desired behaviour?

test("contain items within [start, end] (invert)"){
  val range = Range(100, 1)
  scala.Range(1, 100).foreach(i => range.contains(i) should be (true))
}

It would be logical, I think - but it would probably require some internal re-engineering of Range to know whether it's running forwards or backwards (and then similarly for things like contains(range: Range[A]) we need to compare to whether the other range is forwards or backwards).

[larsrh]

I personally believe that a Range where start > end should be empty. In that case, your proposed test should fail.

As for inverse, I'd probably try to get it into Cats first (another patch release is overdue anyway), and if that fails, go for the extension method.

Would that be alright with you?

[ashleymercer]

I personally believe that a Range where start > end should be empty

In that case, would you be happy for me to remove the logic to run in reverse from toIterator? This behaviour is actually documented so I guess it would be a breaking change (but possibly not an issue since cats-collections is still pre-1.0)?

I'd probably try to get it into Cats first

Okay, I'll raise a ticket there and see what the feedback is :)

[larsrh]

This behaviour is actually documented so I guess it would be a breaking change (but possibly not an issue since cats-collections is still pre-1.0)?

Uh, nothing is ever simple 😅 Let's keep it as it is, then. I wonder though why the test fails, then.

[larsrh]

@ashleymercer Since #358 cats-collection depends on Cats 2.4.0, so the missing instance is available.