PriorityQueueMonoid- Is it strictly a monoid?

[rban1]

Going by the definition of Monoid
The following properties are to be satisfied to be called a Monoid

Assosiativity- a op (b op c) = (a op b) op c
Left Identity- zero op a = a
Right Identity a op zero = a

In such a case, PriorityQueueMonoid seems to be not strictly satisfying the identity laws as there is a case where if I have a queue > max size the identity will limit it to max size.

[johnynek]

A queue that is already too long is not a valid input. We could enforce this with a private type wrapper that you have to call to get into. We don't do this.

If this is a concern for you, you can make a wrapper that does this and use that in your code.

Since this monoid has to be set up, it is not risky currently.

By the way, my current take is that parameterized monoids like this should have that parameter at the type level PriorityQueue[Size, A] where Size is some type level marker of size. Often you only have a few values that make sense and they can be made in user code, or you can use Shapeless Nat if you have Nat values you want to parameterize on, such as this case.

[rban1]

Thanks for your comment Oscar. Wondering if you think if this way of building monoids are in the right spirit though?

For eg: In the priorityqueue monoid the restriction is on one dimension (size) and the claim is queue that is too long is not a valid input( which is being enforced by the build function)

To extend this, instead of one dimension if I have k dimensions and make the claim that monoid laws are obeyed under certain conditions of the k dimensions(like size less than maxsize, elements less than a certain value) and have a build function which enforces these constraints.

Seems like the any datastructure with very restrictive constraints can then be morphed to a monoid. Wanted to heat your perspective on it

[johnynek]

Well, SIP-35 is pretty much my top scala wishlist item: https://docs.scala-lang.org/sips/opaque-types.html but I don't know if I will see it anytime soon, sadly.

If we had SIP-35, we would do things like:

import shapeless.Nat

object PriorityQueue {
  opaque type Value[N <: Nat, +A] = some.ImmutablePriorityQueue[A]

  object Value {
    def apply[N <: Nat, A](iq: some.ImmutablePriorityQueue[A])(implicit N: ToInt[N]): Value[N, A] =
     iq.takeRight(N()) 

    implicit def pqMonoid[N <: Nat, A](implicit N: ToInt[N]): Monoid[Value[N, A]] = ... 
  }
}

This would be nice.

That said, backwards compatibility is a huge concern for me so I would almost certainly not consider removing this monoid especially since it is already non-default.