Scala vector of any dimension using shapeless

Question

I need to measure distance in n-dimensional euclidean space, so I have to create multidimensional vectors and to be able to compare their dimensions and perform some basic operations like '+' or '-'. So, I thought I'll use type classes + shapeless as shown here:

Implementing a generic Vector in Scala

But after investing much time into this I still cannot understand how to implement this. I mean, I can understand idea that stands behind type classes and can use them, but have no idea how to apply shapeless to them. Thanks in advance for any help, like at least the simplest example showing how to use type classes with shapeless.

Answer 1

The first step is either to find or define a type class with the operations you want to support. scala.math.Numeric is one possibility—it provides addition, subtraction, etc., but the fact that it also requires conversions to and from e.g. Int means it's probably not the right choice here. Projects like algebra and Spire include more appropriate candidates.

Defining the type class

To keep things simple we can just define our own:

trait VectorLike[A] {
  def dim: Int
  def add(x: A, y: A): A
  def subtract(x: A, y: A): A
}

(Note that I'm using the Like suffix to avoid a collision with the collection library's Vector. This is a naming convention you'll see sometimes, but it's not by any means a requirement for working with type classes in Scala—in this context more abstract mathematical names like Monoid or Group are more common.)

Defining instances

Next we can define a type class instance for a two-dimensional vector of doubles, for example:

implicit val doubleVector2D: VectorLike[(Double, Double)] =
  new VectorLike[(Double, Double)] {
    def dim: Int = 2
    def add(x: (Double, Double), y: (Double, Double)): (Double, Double) =
      (x._1 + y._1, x._2 + y._2)
    def subtract(x: (Double, Double), y: (Double, Double)): (Double, Double) =
      (x._1 - y._1, x._2 - y._2)
  }

And now we can use this instance like this:

scala> implicitly[VectorLike[(Double, Double)]].add((0.0, 0.0), (1.0, 1.0))
res0: (Double, Double) = (1.0,1.0)

This is pretty verbose, but it works.

Implicit ops classes

It's often convenient to define an implicit "ops" class to make it look like values of a type with a type class instance have methods that are derived from the type class's operations:

implicit class VectorLikeOps[A: VectorLike](wrapped: A) {
  def dim: Int = implicitly[VectorLike[A]].dim
  def |+|(other: A): A = implicitly[VectorLike[A]].add(wrapped, other)
  def |-|(other: A): A = implicitly[VectorLike[A]].subtract(wrapped, other)
}

Now you can write the following:

scala> (0.0, 0.0) |-| (1.0, 1.0)
res1: (Double, Double) = (-1.0,-1.0)

scala> (0.0, 0.0) |+| (1.0, 1.0)
res2: (Double, Double) = (1.0,1.0)

This isn't necessary—it's just a convenient pattern you'll often see.

Generic instances

While our doubleVector2D instance works, defining these instances for every numeric type is annoying and boilerplate-y. We can improve the situation by providing instances for any two-dimensional vector of numeric types using scala.math.Numeric:

implicit def numericVector2D[A](implicit A: Numeric[A]): VectorLike[(A, A)] =
  new VectorLike[(A, A)] {
    def dim: Int = 2
    def add(x: (A, A), y: (A, A)): (A, A) = 
      (A.plus(x._1, y._1), A.plus(x._2, y._2))
    def subtract(x: (A, A), y: (A, A)): (A, A) = 
      (A.minus(x._1, y._1), A.minus(x._2, y._2))
  }

Note that I've given the Numeric type class instance the same name as the generic type (A). This is a common convention for methods where a single type class instance is required for a type, but not at all necessary—we could have called it numericA or anything else we wanted.

And now we can use our operators on any tuple of types with a Numeric instance:

scala> (1, 2) |+| (3, 4)
res3: (Int, Int) = (4,6)

This is a big improvement, but it's still only for a single vector size.

Deriving instances with Shapeless

We've not seen any Shapeless yet, but now that we want to abstract over tuple arity, it's exactly what we need. We can rewrite our generic instance to work with arbitrary tuples of numeric types. There are a number of ways we could write this, but the following is how I'd start:

import shapeless._

trait HListVectorLike[L <: HList] extends VectorLike[L] { type El }

object HListVectorLike {
  type Aux[L <: HList, A] = HListVectorLike[L] { type El = A }

  implicit def vectorLikeHNil[A]: Aux[HNil, A] =
    new HListVectorLike[HNil] {
      type El = A
      def dim: Int = 0
      def add(x: HNil, y: HNil): HNil = HNil
      def subtract(x: HNil, y: HNil): HNil = HNil
    }

  implicit def vectorLikeHCons[T <: HList, A](implicit
    numeric: Numeric[A],
    instT: Aux[T, A]
  ): Aux[A :: T, A] = new HListVectorLike[A :: T] {
    type El = A
    def dim: Int = instT.dim + 1
    def add(x: A :: T, y: A :: T): A :: T =
      numeric.plus(x.head, y.head) :: instT.add(x.tail, y.tail)
    def subtract(x: A :: T, y: A :: T): A :: T =
      numeric.minus(x.head, y.head) :: instT.subtract(x.tail, y.tail)
  }
}

implicit def numericVector[P, Repr <: HList](implicit
  gen: Generic.Aux[P, Repr],
  inst: HListVectorLike[Repr]
): VectorLike[P] = new VectorLike[P] {
  def dim: Int = inst.dim
  def add(x: P, y: P): P = gen.from(inst.add(gen.to(x), gen.to(y)))
  def subtract(x: P, y: P): P = gen.from(inst.subtract(gen.to(x), gen.to(y)))
}

This looks complex, and it is, but the basic pattern is something you'll see any time you're using Shapeless for generic derivation. I won't describe what's going on in detail here, but see e.g. my blog post here for discussion of a similar example.

Now we can write something like this:

scala> (1, 2, 3, 4) |+| (5, 6, 7, 8)
res1: (Int, Int, Int, Int) = (6,8,10,12)

Or this:

scala> (0.0, 0.0, 0.0, 0.0, 0.0, 0.0) |-| (1.0, 2.0, 3.0, 4.0, 5.0, 6.0)
res4: (Double, Double, Double, Double, Double, Double) = (-1.0,-2.0,-3.0,-4.0,-5.0,-6.0)

And it just works.

Other vector representations

I've been using tuples to represent multi-dimensional vectors in all of the examples above, but you could also use Shapeless's Sized, which is a homogeneous collection that encodes its length at the type level. You could provide VectorLike instances for Sized types instead of (or in addition to) the tuple instances, without making any changes to VectorLike itself.

Which representation you should choose depends on a number of factors. Tuples are easy to write and will look natural to most Scala developers, but if you need vectors with more than 22 dimensions, they're not going to work.