Scala 3 given/implicit resolution doesn't work as expected

53 Views Asked by At

I'm working on the Chapter 11 Case Study: CRDTs from the excellent book "Scala with Cats". The code in the book is written using Scala 2, but I've modified it for Scala 3, specifically 3.3.1. This has worked for all the exercises in the book, except for the following.

The goal of this case study is to merge increment-only counters, mimicking an eventually consistent system. Although somewhat long, I show my code below.

// KeyValueStore.scala
trait KeyValueStore[F[_, _]]:
  def put[K, V](f: F[K, V])(k: K, v: V): F[K, V]

  def get[K, V](f: F[K, V])(k: K): Option[V]

  def getOrElse[K, V](f: F[K, V])(k: K, default: V): V =
    get(f)(k).getOrElse(default)

  def values[K, V](f: F[K, V]): List[V]

object KeyValueStore:
  given KeyValueStore[Map] with
    def put[K, V](f: Map[K, V])(k: K, v: V): Map[K, V] =
      f + (k -> v)

    def get[K, V](f: Map[K, V])(k: K): Option[V] =
      f.get(k)

    override def getOrElse[K, V](f: Map[K, V])(k: K, default: V): V =
      f.getOrElse(k, default)

    def values[K, V](f: Map[K, V]): List[V] =
      f.values.toList

object KeyValueStoreSyntax:
  extension [F[_, _], K, V](f: F[K, V])(using kvs: KeyValueStore[F])
    def put(key: K, value: V) =
      kvs.put(f)(key, value)

    def get(key: K): Option[V] =
      kvs.get(f)(key)

    def getOrElse(key: K, default: V): V =
      kvs.getOrElse(f)(key, default)

    def values: List[V] =
      kvs.values(f)

// BoundedSemiLattice.scala
import cats.kernel.CommutativeMonoid

trait BoundedSemiLattice[A] extends CommutativeMonoid[A]:
  def combine(a1: A, a2: A): A
  def empty: A

object BoundedSemiLattice:
  given intInstance: BoundedSemiLattice[Int] with
    def combine(a1: Int, a2: Int): Int =
      a1 max a2

    val empty: Int = 0

// GCounter.scala
import cats.kernel.CommutativeMonoid
import cats.syntax.semigroup.catsSyntaxSemigroup
import cats.syntax.foldable.toFoldableOps

// 11 Case Study: CRDTs
trait GCounter[F[_, _], K, V]:
  def increment(f: F[K, V])(k: K, v: V)(using CommutativeMonoid[V]): F[K, V]

  def merge(f1: F[K, V], f2: F[K, V])(using BoundedSemiLattice[V]): F[K, V]

  def total(f: F[K, V])(using CommutativeMonoid[V]): V

object GCounter:
  import KeyValueStoreSyntax.*

  given [F[_, _], K, V](using KeyValueStore[F], CommutativeMonoid[F[K, V]]): GCounter[F, K, V] with
    def increment(f: F[K, V])(key: K, value: V)(using m: CommutativeMonoid[V]): F[K, V] =
      val total = f.getOrElse(key, m.empty) |+| value
      f.put(key, total)

    def merge(f1: F[K, V], f2: F[K, V])(using BoundedSemiLattice[V]): F[K, V] =
      f1 |+| f2

    def total(f: F[K, V])(using CommutativeMonoid[V]): V =
      f.values.combineAll

The problem is with the test I wrote.

import org.scalatest.funspec.AnyFunSpec
import org.scalatest.matchers.should.Matchers.shouldBe

class GCounterSpec extends AnyFunSpec:
  it("should reconcile counters"):
    val g1 = Map("a" -> 7, "b" -> 3)
    val g2 = Map("a" -> 2, "b" -> 5)

    val counter = summon[GCounter[Map, String, Int]]

    val merged = counter.merge(g1, g2)
    merged `shouldBe` Map("a" -> 7, "b" -> 5)

    val total = counter.total(merged)
    total `shouldBe` 12

The merge method is supposed to use the BoundedSemiLattice[Int] instance, and take the maximum of Map values for the same key, but instead it is adding up the values using the Monoid instance for Int. Thus, the merged map is "a" -> 9, "b" -> 8, which is not expected.

As shown, a BoundedSemiLattice extends CommutativeMonoid, but the Scala 3 implicit resolution rules say that:

An implicit a defined in A is more specific than an implicit b defined in B if A extends B

So, the code should use BoundedSemiLattice. Why is it not doing so? I've checked that replacing Scala 3 using with Scala 2 implicit doesn't change anything.

The code shown above is also available on my GitHub, and can be cloned to reproduce the problem. A Scala 2 version is available here. FWIW, the Scala 2 version seems to work, even when compiled using Scala 3.

0

There are 0 best solutions below