Implementing Laws-Based Testing for Vector Operations

[Quafadas]

The vecxt library provides cross-platform vector operations using Array[Double] as the underlying representation. We want to introduce a laws-based testing framework to verify algebraic properties (e.g., Monoid, Semigroup laws) for vector operations, similar to how cats tests its abstractions.

The Core Challenge

Scala's type system cannot practically encode a Monoid typeclass for vectors at compile time because:

Array length is runtime information: Array[Double] doesn't encode its length in the type
Traditional Monoid requires standalone empty: Monoid[A] requires a parameterless empty: A value
Vector operations require dimension matching: We need to ensure operations like + only combine vectors of the same length
For example, a true monoid needs:

trait Monoid[A]:
  def empty: A  // ← How do we know what length this should be?
  def combine(x: A, y: A): A

Proposed Solution: Scoped Dimension Context

The recommended approach uses dimension as implicit context, creating monoid instances scoped to a specific dimension.

Core Type Definitions

package vecxt.laws

import cats. kernel. {Monoid, Semigroup, Eq}
import vecxt.BoundsCheck

// Dimension as an opaque type for type safety
opaque type Dimension = Int

object Dimension:
  def apply(n: Int): Dimension = n
  
  extension (d: Dimension)
    def size: Int = d

VectorMonoid Typeclass

/** A Monoid for Array[A] scoped to a specific dimension. 
  * 
  * This trait extends cats.kernel.Monoid, making it compatible with
  * the entire cats laws testing infrastructure.
  * 
  * @tparam A The element type (must form a Semigroup)
  */
trait VectorMonoid[D <: Dimension, A] extends Monoid[Array[A]]:
  /** The dimension this monoid operates on */
  def dimension: Dimension
  
  /** The identity element - an array of zeros of the correct dimension */
  def empty: Array[A]
  
  /** Combine two arrays element-wise */
  def combine(x: Array[A], y:  Array[A]): Array[A]
  
  /** Validate that an array has the expected dimension */
  protected def validateDim(arr: Array[A]): Unit =
    if arr.length != dimension. size then
      throw new VectorDimensionException(
        s"Expected dimension ${dimension.size}, got ${arr.length}"
      )

class VectorDimensionException(msg: String) extends IllegalArgumentException(msg)

Factory Methods

package vecxt.laws

import cats. kernel.{Monoid, Semigroup, CommutativeMonoid}
import vecxt.BoundsCheck

// Dimension type
opaque type Dimension = Int

object Dimension:
  def apply(n: Int): Dimension = n
  
  extension (d:  Dimension)
    def size: Int = d

class VectorDimensionException(msg: String) extends IllegalArgumentException(msg)

// VectorMonoid with dimension in type parameter
trait VectorMonoid[D <: Dimension, A] extends Monoid[Array[A]]:
  def dimension: D
  def empty: Array[A]
  def combine(x: Array[A], y: Array[A]): Array[A]
  
  protected def validateDim(arr: Array[A]): Unit =
    if arr.length != dimension.size then
      throw new VectorDimensionException(
        s"Expected dimension ${dimension. size}, got ${arr.length}"
      )

object VectorMonoid:
  // Now safe - dimension is in the type
  def apply[D <:  Dimension, A](using vm: VectorMonoid[D, A]): VectorMonoid[D, A] = vm
  
  def forDimension[D <: Dimension, A: Semigroup](dim: D)(
    emptyFn: => Array[A],
    combineFn: (Array[A], Array[A]) => Array[A]
  )(using bc: BoundsCheck.BoundsCheck = BoundsCheck.DoBoundsCheck.yes): VectorMonoid[D, A] = 
    new VectorMonoid[D, A]:
      val dimension:  D = dim
      
      def empty = emptyFn
      
      def combine(x: Array[A], y: Array[A]) =
        inline if bc == BoundsCheck.DoBoundsCheck.yes then
          validateDim(x)
          validateDim(y)
        combineFn(x, y)

// Commutative variant
trait VectorCommutativeMonoid[D <: Dimension, A] 
  extends VectorMonoid[D, A] with CommutativeMonoid[Array[A]]

object VectorCommutativeMonoid:
  def apply[D <: Dimension, A](using vcm: VectorCommutativeMonoid[D, A]): VectorCommutativeMonoid[D, A] = vcm
  
  def forDimension[D <: Dimension, A:  Semigroup](dim: D)(
    emptyFn: => Array[A],
    combineFn: (Array[A], Array[A]) => Array[A]
  )(using bc: BoundsCheck.BoundsCheck = BoundsCheck.DoBoundsCheck.yes): VectorCommutativeMonoid[D, A] = 
    new VectorCommutativeMonoid[D, A]:
      val dimension: D = dim
      def empty = emptyFn
      def combine(x: Array[A], y: Array[A]) =
        inline if bc == BoundsCheck.DoBoundsCheck.yes then
          validateDim(x)
          validateDim(y)
        combineFn(x, y)


def processVectors[D <:  Dimension, A: Semigroup](
  dim: D,  // Explicit dimension witness
  vectors: List[Array[A]]
)(using vm: VectorMonoid[D, A]): Array[A] =
  require(vectors.forall(_.length == dim.size), "All vectors must match dimension")
  vectors.foldLeft(vm.empty)(vm.combine)

// Usage forces dimension to be explicit
given myDim: Dimension = Dimension(3)
given VectorMonoid[myDim. type, Double] = ... 

processVectors(myDim, vectors)  // Dimension is explicit and checked

Laws Testing Integration
Test Setup
The implementation is fully compatible with cats laws out of the box:

package vecxt.laws

import cats.kernel.laws.discipline.{MonoidTests, CommutativeMonoidTests}
import cats.kernel.Eq
import munit.DisciplineSuite
import org.scalacheck. {Arbitrary, Gen}
import vecxt.all.{given, *}

class VectorMonoidLawsSpec extends DisciplineSuite: 
  
  def testMonoidLaws(n: Int): Unit =
    // Create dimension with stable identifier
    val testDim = Dimension(n)
    
    // Now this given has type VectorMonoid[testDim.type, Double]
    given VectorMonoid[testDim.type, Double] = 
      VectorMonoid.forDimension(testDim)(
        Array.fill(n)(0.0),
        _ + _
      )
    
    given Arbitrary[Array[Double]] = Arbitrary(
      Gen.listOfN(n, Arbitrary.arbitrary[Double]).map(_.toArray)
    )
    
    given Eq[Array[Double]] = Eq.instance((a, b) =>
      a.length == b. length && 
      a.zip(b).forall { case (x, y) => Math.abs(x - y) < 1e-6 }
    )
    
    // Type parameter ensures we get the right monoid
    checkAll(
      s"VectorMonoid[dim$n, Double]",
      MonoidTests[Array[Double]].monoid
    )
  
  testMonoidLaws(3)
  testMonoidLaws(10)
  testMonoidLaws(100)

end VectorMonoidLawsSpec

Laws Checked Automatically
By using MonoidTests[Array[Double]].monoid, cats automatically verifies:

Left Identity: combine(empty, x) === x
Right Identity: combine(x, empty) === x
Associativity: combine(combine(x, y), z) === combine(x, combine(y, z))
combineAll: Combining all elements in a list
combineN: Repeated combination N times
repeat0: combineN(x, 0) === empty
collect0: combineAll(Nil) === empty
isEmpty: Testing for identity element
For CommutativeMonoidTests, it additionally checks:

Commutativity: combine(x, y) === combine(y, x)
Implementation Plan
Phase 1: Core Infrastructure
Files to create:

vecxt/laws/src/Dimension.scala - Dimension type definition
vecxt/laws/src/VectorMonoid.scala - VectorMonoid trait and companion
vecxt/laws/src/VectorCommutativeMonoid.scala - Commutative variant
Dependencies to add:

val catsVersion = "2.10.0"  // or latest
val disciplineVersion = "1.5.1"
val scalacheckVersion = "1.17.0"

object laws extends Cross[VecxtLawsModule](scalaVersions) {
  trait VecxtLawsModule extends CrossScalaModule {
    def ivyDeps = Agg(
      ivy"org.typelevel::cats-kernel:$catsVersion",
      ivy"org.typelevel::cats-kernel-laws:$catsVersion",
    )
  }
}

object lawsTests extends Cross[VecxtLawsTestsModule](scalaVersions) {
  trait VecxtLawsTestsModule extends CrossScalaModule with TestModule. Munit {
    def moduleDeps = Seq(laws(), vecxt())
    def ivyDeps = Agg(
      ivy"org.typelevel::cats-kernel-laws:$catsVersion",
      ivy"org. typelevel::discipline-munit:$disciplineVersion",
      ivy"org.scalacheck::scalacheck:$scalacheckVersion",
    )
  }
}

Phase 2: Basic Instances
Create instances for common operations:

vecxt/laws/src/instances/DoubleInstances.scala:

package vecxt.laws.instances

import cats.kernel. Semigroup
import vecxt.laws.{Dimension, VectorCommutativeMonoid}
import vecxt.all.{given, *}
import vecxt.BoundsCheck

object double: 
  /** VectorCommutativeMonoid for Array[Double] with element-wise addition */
  given vectorAdditionMonoid(using dim: Dimension, bc: BoundsCheck.BoundsCheck): VectorCommutativeMonoid[Double] =
    VectorCommutativeMonoid.forDimension(dim)(
      emptyFn = Array.fill(dim.size)(0.0),
      combineFn = (x, y) => x + y
    )
  
  /** VectorMonoid for Array[Double] with element-wise multiplication 
    * Note: Not commutative in general, but element-wise is
    */
  given vectorMultiplicationMonoid(using dim:  Dimension, bc: BoundsCheck.BoundsCheck): VectorCommutativeMonoid[Double] =
    VectorCommutativeMonoid.forDimension(dim)(
      emptyFn = Array.fill(dim.size)(1.0),
      combineFn = (x, y) => x *: * y  // element-wise multiplication
    )

Phase 3: Comprehensive Tests
vecxt/laws/test/src/VectorMonoidLawsSpec.scala:

Full test suite as shown in "Laws Testing Integration" section above.

Phase 4: Documentation
site/docs/laws. md:

Markdown

Laws Testing

vecxt provides laws-based testing infrastructure to verify algebraic properties of vector operations.

Overview

Vector operations form algebraic structures (Monoids, Semigroups, etc.) that must satisfy certain laws. The vecxt laws module provides:

• Type-safe dimension tracking
• Integration with cats laws
• Automatic property-based testing

Usage

Defining a Dimension Context

import vecxt.laws.*
import vecxt.all.{given, *}

given dim:  Dimension = Dimension(3)

Creating Monoid Instances

given VectorCommutativeMonoid[Double] = 
  VectorCommutativeMonoid.forDimension(dim)(
    emptyFn = Array.fill(3)(0.0),
    combineFn = (x, y) => x + y
  )

Using in Computations

def sumVectors(vectors: List[Array[Double]])(using vm: VectorMonoid[Double]): Array[Double] =
  vectors. foldLeft(vm.empty)(vm.combine)

Testing Your Own Operations

See the Laws Testing Guide for details on how to test custom vector operations.
Benefits of This Approach

✅ Advantages

• True Monoid Laws: empty doesn't need a parameter - it's a proper monoid
• Type-Safe Dimensions: Dimension is part of the implicit scope
• Works with Array[Double]: No wrapping, no allocations, no performance overhead
• Cats Compatible: Directly extends cats.kernel.Monoid - plug into existing infrastructure
• Practical: Handles runtime-determined dimensions via given instances
• Testable: Can test laws for arbitrary dimensions
• Clear Semantics: "This monoid operates in dimension N" is explicit in the type
• Integrates with BoundsCheck: Uses vecxt's existing bounds checking system
• Zero Overhead: When bounds checks disabled, dimension validation disappears

⚠️ Considerations

• Dimension Tracking: Need to ensure correct given Dimension is in scope
• Runtime Checks: Dimension validation happens at runtime (but can be disabled)
• Multiple Givens: Operations on different dimensions need separate given instances
• Learning Curve: Users need to understand the dimension context pattern

Success Criteria

• Create a new laws test module
• Laws module compiles on JVM, JS, and Native
• All cats Monoid laws pass for Array[Double] with addition
• All cats CommutativeMonoid laws pass for Array[Double] with addition
• Tests run for dimensions: 1, 3, 10, 100, 1000
• Integration with vecxt's existing BoundsCheck system works
• Documentation explains the dimension context pattern
• Zero runtime overhead when bounds checks disabled
• Tests pass on all three platforms
• CI passes

Should dimension validation throw or return Either/Validated?

Throw... we want either blistering performance or early failure.

References

cats kernel laws
cats MonoidTests
[vecxt BoundsCheck system](https://github.com/Quafadas/vecxt/blob/main/site/docs/bounds. md)