Default typeclasses for Int

[denisrosset]

The type Int has two default typeclasses:

• the Lattice instance is provided by IntIsBitString,
• the Order instance is provided by IntAlgebra,

but these two instances are not compatible.

The IntAlgebra Order instance would be compatible with the min/max lattice for Int; for the IntIsBitString lattice, the set inclusion partial order should be used instead.

This is a problem when several instances of a particular algebraic structure is possible, and not all combinations are meaningful. Plus, I do not see the way to encode compatibility of typeclasses using the Scala type system.

We should either make one of the instances optional, or document this trap.

[FJValverde]

Hi,

Since the discussion is public, I hope the intrusion is not badly taken! ;)

This problem with typeclasses is going to crop up the more and more people use Spire:

• How neatly does Spire solve the problem that a single carrier set (type) is carrying many different algebraic structures (typeclasses, I guess)? I would thank you guys is this was explicitly addressed in the docs.
• Can two different algebras (e.g. two different ways of being a lattice) be invoked on the same carrier set (e.g. ints) in the same program? (I guessed a number of implicits are needed that would collide).

In fact, part of my work is building “custom” lattices on different carrier sets and the examples you point out are only two of the lattices structures that you could impose on integers (of the handful of them that we seem to be able to invoke: Check Gondran and Minoux’ 2008 book). I would be very thankful if this situation could we made a little bit clearer for us users of the lib.

Regards,

Francisco

On 18/11/2014, at 12:36, Denis Rosset <notifications@github.com mailto:notifications@github.com> wrote:

The type Int has two default typeclasses:

the Lattice instance is provided by IntIsBitString, the Order instance is provided by IntAlgebra, but these two instances are not compatible.

The IntAlgebra Order instance would be compatible with the min/max lattice for Int; for the IntIsBitString lattice, the set inclusion partial order should be used instead.

This is a problem when several instances of a particular algebraic structure is possible, and not all combinations are meaningful. Plus, I do not see the way to encode compatibility of typeclasses using the Scala type system.

We should either make one of the instances optional, or document this trap.

— Reply to this email directly or view it on GitHub https://github.com/non/spire/issues/326.

[denisrosset]

Hi Francisco,

you can mix and match type classes by importing the in the scope where they are used.

If you happen to use two kind of e.g. lattices in the same scope for the same primitive type, I would wrap those types in value classes to differentiate their usage.

Indeed, it can be tricky to decide which implicits you want in scope in Scala.

[non]

Right, so we can definitely use imports to force consistency.

@FJValverde: if you find having to import different instances to be difficult to reason about, another option is to tag your underlying type (carrier set) and then define your own instances for those.

For example, you can do it with value classes as below:

class BitwiseInt(val toInt: Int) extends AnyVal
class OrderedInt(val toInt: Int) extends AnyVal

object BitwiseInt {
  implicit val lattice = new Lattice[BitwiseInt] { ... }
}

object OrderedInt {
  implicit val lattice = new Lattice[OrderedInt] { ... }
}

Spire doesn't do this by default for a couple of reasons:

1. People working with primitive types probably don't want to have to do a conversion step before using Spire.
2. There are a some cases where value classes impose a bit of overhead.

However, for a lot of problems that approach is fine.

One other thing I want to clear up: I wouldn't say that Int has two default type classes. Rather, I would say that Int has two instances to many type classes. There's no conceptual reason why:

implicit val intAlgebra = new IntHasRing with IntHasOrder with ... {}

should be preferred to:

implicit val intRing = new IntHasRing {}
implicit val intOrder = new IntHasOrder {}
...

[non]

I meant to add that this definitely needs to be cleared up before the next release. Adding lattices to Spire seems useful, but unfortunately they are general enough that "managing" them will be a bit tricky. I'm not sure how bad the current "incompatibility" is. Maybe you can elaborate @denisrosset?

From my point of view things seem to be working as I'd expect:

// uses Order[Int] to do (Int < Int) logically
def abc[A: Order](x: A, y: A): A = x < y

// uses Heyting[Int] to do (Int & Int) bitwise
def xyz[A: Heyting](x: A, y: A): A = x & y

I'm not sure it would be a good idea to change either of these behaviors. If someone wants to use their lattice as a partial ordering, maybe they should need to opt-into that explicitly? What do you think?

[non]

Also, thanks for all the feedback! Lattices are not something I've worked with much (as is probably obvious) so it's quite likely the initial design may need some work.

[denisrosset]

The current lattice definitions are fine; I had actually written some for my library Alasc ( https://github.com/denisrosset/alasc ) and I'm in the process of replacing them with the standard ones provided by Spire.

It's also good to separate partial orders and lattices, so that one can define type classes for one or the other. But when using them together, an additional set of laws apply (see https://github.com/non/spire/blob/master/scalacheck-binding/src/main/scala/spire/laws/LatticePartialOrderLaws.scala ); in the case of Int, the default type class for the lattice and the default type class for the (partial) order are incompatible.

Thus, those who'd like to use Ints in a lattice should be careful about the spire.std.int._ import.

There should be some documentation about the default type classes provided for primitives, in the cases where there is ambiguity (for ex. here).

[non]

OK, I see. Thanks for adding the laws!

One small point, I think it is usually a better idea to say:

def xyz[A](implicit A0: Lattice[A], A1: PartialOrder[A]) = ...

rather than saying

def xyz[A](implicit A: Lattice[A] with PartialOrder[A]) = ...

The latter definition will cause problems for people trying to use several pre-existing type class instances together. Does this make sense?

[tixxit]

I think documentation is our best best here for now. The other solution I can think of is that, in these situations, another typeclass is needed that traps the 2 compatible instance together. It's a bit ugly/boilerplate-y though, so people may prefer documentation / being careful with imports.

[denisrosset]

@non, agree with you last point, it was corrected in a later commit of #323 that was ignored during the merge.

[denisrosset]

@tixxit, the master typeclass approach has limits, because it leads to an explosion of boilerplate: there are two variants of PartialOrder/Order, several variants of Lattices, giving ~20 typeclasses for the combinations.

[non]

Argh, OK, I'll try to clean that up. Sorry! (You even warned me.)

[tixxit]

@denisrosset Oh yeah, you don't have to convince me. One of the reasons I started removing the scalar type class from VectorSpace (PR soon, hopefully). Just got way too complex fast - which is why I'd just prefer the documentation route.