Sorted Sequences

[benhutchison]

I have a situation where I'd like to state/require that a Seq is sorted via a type. I also recall similar situations arising in the past.

In my case, it's a Seq resulting from a database query, and I know the rows are unique and sorted. The algorithm that crunches the rows relies on the ordering of the input data for correctness. In my example, the sorting is by two columns, a stock code and then a date.

I know Scala has sorted sets and maps, but that's a different use case IMO; here I'm streaming in already sorted data that's naturally a Seq, and want to state that in the type signature.

What I imagine is a type SSeq[A, O], a subtype of Seq[A] where O <: Ordering[A] that certifies that the Seq is sorted by that ordering.

Further, there seem to be many operations on Seqs that preserve sortedness, such as filtering, partitioning, and taking subsequences. Some extension method variants on SSeqs that preserve sortedness would be required to realise the full value of a constraint.

Has anyone attempted or explored something like this Iron (or another refined type library)?

[Iltotore]

I am not aware of such initiative thought it should not be very complicated to do:

• Add a Sorted constraint
• Make a SSeq newtype
• Add extension for sortedness-friendly Seq methods