I am currently working in Scala 3 with immutable, finite, small circular collections, meaning that there is no proper beginning or end; unlike a standard Vector, each element at index n always has both an element before (even if n is 0) and an element after (even if n is the “last” index).
I wonder if it could be useful for me to create a custom collection to deal with them. So that for instance:
any index, negative or positive is always valid;
methods like sliding can be modified to behave correctly in a circular fashion;
methods like rotateLeft and rotateRight can be added.
I would like to have your suggestions. Something like this exists already? (I haven’t found it) Maybe it is an overkill? Can this be achieved easily by extending and overriding Vector?
Seems a bit specialized – what sort of use cases do you use it for?
In general, it’s the sort of thing where I’d probably recommend starting out by releasing it as a library, and seeing how many people make use of it.
My main concern about it in terms of being a “standard” collection is that I’m not really sure how iteration would behave in a circular object like that, so it’s conceptually a bit different from most…
My use case is 2D geometry and graphs, I keep stumbling on circular collections, adjacent angles of a full 360° circle, sides of a perimeter, nodes of a circular path…
So I started thinking if it would be more elegant and sound to have something like class Perimeter(angles: CircularVector[Double]) instead of class Perimeter(angles: Vector[Double]). And to deal at collection level with all the usual methods related to circularity: rotation, symmetries, knowing that after the last element you have the first one…
As for Iteration is a good point, I would say I would expect a standard behaviour, ending after the last element, not going into an infinite loop, if this is what you had in mind.
Plus I am not hoping to create something tremendously useful, it would be enough if it makes sense for me. More than happy to share it, of course. I was following in the tracks of Implementing Custom Collections (Scala 2.13) | Scala Documentation where it seems that sometimes creating custom collections (even if not so simple) is the right way to go.
What you are talking about is known as a circular or ring buffer. I implemented one in Scala many years ago, but I am not currently using it. The one I implemented was based on an Array and was not immutable. The whole thing was 48 lines long, including blank lines, so it’s very easy to implement. I would develop an immutable version if I had a use for it.
Hey, you may want to add that to the scala-collection-contrib library so you don’t have to do all the ceremony of publishing a library for a single file.
On a different level, I am noticing that all the methods I wrote for Vector can be generalized for Seq. So I have already tested a more general draft version RingSeq. And now the dumb question: which is in this case the correct way to work with bounds and higher kinds?
I have gone this way and it seems to work:
trait RingSeq:
/* for improved readability, a Vector index */
type Index = Int
/* and a RingVector index, any value is valid */
type IndexO = Int
extension[A, B <: Seq[A]](ring: B)
private def index(i: IndexO): Index =
java.lang.Math.floorMod(i, ring.size)
def applyO(i: IndexO): A =
ring(index(i))
def rotateRight(step: Int): B =
if ring.isEmpty then ring
else
val j: Index = ring.size - index(step)
(ring.drop(j) ++ ring.take(j)).asInstanceOf[B]
...
but as soon as I wrote the first asInstanceOf[B] I felt horribly guilty as a student who has not done the proper homework.
A naive (really!) attempt to fix this by shifting the “plugin point” to SeqOps for sequence types that always produce their own type as the result of combinator ops:
extension[A, B[_] <: SeqOps[A, B, B[A]]](ring: B[A])
// ...
def rotateRight(step: Int): B[A] =
if ring.isEmpty then ring
else
val j: Index = ring.size - index(step)
ring.drop(j) ++ ring.take(j)
This seems to work with List, Vector and Queue at least. However, for a clean and stable solution, it’s probably best to work through the guide @BalmungSan linked to - there also seems to be a page on adding custom operations, which may or may not apply to your use case. (I haven’t ventured into this specific area, yet.)
Scala 3 vs Scala 2: I am sure back porting to Scala 2 must be feasible, I’ll take a look at it once I am confident and happy with the Scala 3 version. Personally after I moved to Scala 3 I try as much as possible to avoid switching codes, not good for my mental health
Custom Collections vs Scala 3 extension: adding to the previous point, Custom Collections has been -as I wrote at the start of the thread- my starting point, but then I shifted to Scala 3 extension because most of the Seq collections would be exactly the same, instead of overriding 7 methods I can just add their O ring counterpart.
What I want to add is that I can truly see some merit and usefulness in a working RingSeq and I would like (with some help from the community, since I am not a super expert on these abstractions) to reach a point where it can be safely shared.
Uh, yes. Looks like it always matches to SeqOps[Any, B, B[Any]] - which isn’t wrong, as SeqOps is covariant in A, but I’d have expected the most specific match.
When tinkering with explicit casts, I ran into what looked like a compiler hang/infinite loop:
scala> List(1,2,3).rotateRight(1)
-- Info:
[[syntax trees at end of typer]] // rs$line$2
package repl {
final lazy module val rs$line$2: repl.rs$line$2 = new repl.rs$line$2()
final module class rs$line$2() extends Object() { this: repl.rs$line$2.type =>
val res0: List[Any] =
RingSeq.rotateRight[Any, List](List.apply[Int]([1,2,3 : Int]*))(1)
}
}
val res0: List[Any] = List(3, 1, 2)
scala> (List(1,2,3): scala.collection.immutable.SeqOps[Int, List, List[Int]]).rotateRight(1)
[warn] In the last 10 seconds, 5.759 (58.3%) were spent in GC. [Heap: 0.01GB free of 1.00GB, max 1.00GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.
Killed
No idea what to make of this, I’m afraid - I’m neither fluent with custom collection extensions nor with in-depth Scala 3 (yet). Perhaps somebody more knowledgeable can chime in?
On initial question: I have not found a simple way to return an empty That , see SeqDecorator line 84, any suggestion?
I haven’t tested but what about:
bf.fromSpecific(coll)(collection.View.Empty)
// Or
bf.fromSpecific(coll)(Seq.empty)
Unfortunately I made no real progress in evolving RingSeq in Scala 3 or Scala 2, with IsSeq and SeqOps, will keep trying.
Yeah, abstracting over collections is a complex science. I personally have never been able to do something more advanced than just consuming anything that can behave as a collection; every attempt to do something else has ended in failure.
Good luck!
@BalmungSan thank you for the suggestion, I would say that bf.fromSpecific(coll)(collection.View.Empty) is correct.
I am really cautious about jumping to any conclusion since I just added a test for an empty Seq that is failing in really strange fashion:
[error] one error found
[error] /.../scala-collection-contrib/src/test/scala/scala/collection/decorators/SeqDecoratorTest.scala:55:35: diverging implicit expansion for type scala.math.Ordering[T1]
[error] starting with method Tuple9 in object Ordering
[error] assertEquals(empty.rotateRight(1), empty)
Looks like it always matches to