Recursive given not working

[andrelfpinto]

Compiler version

3.3.0

Minimized code

I tried my best to minimize the code without losing the "essence" of the problem:

opaque type Labelled[Name <: Singleton & String, Value] = Value

object Labelled:
  def apply[Name <: Singleton & String, Value](
      name: Name,
      value: Value
  ): Labelled[Name, Value] = value

sealed abstract class LabelledList

object LabelledList:
  final case class Cons[
      Name <: Singleton & String,
      Value,
      Tail <: LabelledList
  ](
      col: Labelled[Name, Value],
      tail: Tail
  ) extends LabelledList

  case object Empty extends LabelledList

  type FromTuple[Tup <: Tuple] <: LabelledList = Tup match {
    case EmptyTuple  => Empty.type
    case (n, v) *: t => Cons[n, v, FromTuple[t]]
  }

  trait Enc[Tup <: Tuple]:
    def enc(tup: Tup): FromTuple[Tup]

  given e: Enc[EmptyTuple] with
    def enc(emptyTuple: EmptyTuple) = Empty

  given ne[N <: Singleton & String, V, T <: Tuple: Enc]: Enc[(N, V) *: T] with
    def enc(tuple: (N, V) *: T) =
      val (n, v) *: t = tuple
      Cons(Labelled(n, v), summon[Enc[T]].enc(t))

class BugTests extends munit.FunSuite {
  test("empty") {
    val obtained = LabelledList.e.enc(EmptyTuple)
    val expected = LabelledList.Empty

    assertEquals(obtained, expected)
  }

  test("1-tuple") {
    val obtained = LabelledList.ne.enc(
      ("col2" -> 2) *: EmptyTuple
    )
    val expected = LabelledList.Cons(
      Labelled("col2", 2),
      LabelledList.Empty
    )

    assertEquals(obtained, expected)
  }

  test("2-tuple") {
    val obtained = LabelledList.ne.enc(
      ("col1" -> 1) *: ("col2" -> 2) *: EmptyTuple
    )
    val expected = LabelledList.Cons(
      Labelled("col1", 1),
      LabelledList.Cons(
        Labelled("col2", 2),
        LabelledList.Empty
      )
    )

    assertEquals(obtained, expected)
  }
}

Output

[error] ./Bug.test.scala:61:8
[error] Found:    ((String, Int), (String, Int))
[error] Required: (Nothing, Nothing) *: EmptyTuple.type
[error]
[error] The following import might make progress towards fixing the problem:
[error]
[error]   import munit.Clue.generate
[error]
[error]       ("col1" -> 1) *: ("col2" -> 2) *: EmptyTuple
[error]        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error] ./Bug.test.scala:71:5
[error] missing argument for parameter ev of method assertEquals in trait Assertions: (implicit loc: munit.Location, ev:
[error]   LabelledList.Cons[("col1" : String), Int,
[error]     LabelledList.Cons[("col2" : String), Int, LabelledList.Empty.type]]
[error]  <:< LabelledList.Cons[Nothing, Nothing, LabelledList.Empty.type]): Unit
[error]     assertEquals(obtained, expected)
[error]     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Expectation

Both tests empty and 1-tuple work, but 2-tuple doesn't. I would expect it to just work recursively.

Maybe similar to #18211, but I couldn't say for sure.

[jchyb]

More aggressive minimization:

object LabelledList:

  trait Enc[Tup <: Tuple]:
    def enc(tup: Tup): Unit

  given e: Enc[EmptyTuple] with
    def enc(emptyTuple: EmptyTuple) = ()

  given ne[N <: Singleton & String, V, T <: Tuple: Enc]: Enc[(N, V) *: T] with
    def enc(tuple: (N, V) *: T): Unit = ()

object BugTests:

  def main() =
    val works = LabelledList.ne.enc(
      ("col1" -> 1) *: EmptyTuple
    )

    val fails = LabelledList.ne.enc(
      ("col1" -> 1) *: ("col2" -> 2) *: EmptyTuple
    )

[dwijnand]

This isn't a bug. You can't call LabelledList.ne.enc and expect that to magically backtrack the term argument to enc to the type args of ne.

[andrelfpinto]

Thank you @dwijnand for your time answering this. Can you explain me why it works for empty and 1-tuple and not for 2-tuple?

[dwijnand]

It works for empty, because you're using LabelledList.e, which takes an EmptyTuple. It works for 1-tuple, because you're taking LabelledList.ne, without type arguments, so type inference finds that it can instantiate T with EmptyTuple, using LabelledList.e as Enc[T], so it can only handle a tuple-1.

[andrelfpinto]

Hi, @dwijnand, thank you for the explanation.

I tried a different approach using extension methods and it still didn't work (not even the 1-tuple):

   trait Enc1[Tup <: Tuple]:
     extension (tup: Tup) def enc: FromTuple[Tup]

   given e: Enc1[EmptyTuple] with
     extension (tup: EmptyTuple) def enc = Empty

   given ne[N <: Singleton & String, V, T <: Tuple: Enc1]: Enc1[(N, V) *: T] with
     extension (tuple: (N, V) *: T) def enc =
       val (n, v) *: t = tuple
       Cons(Labelled(n, v), t.enc)

   val obtained = (
     ("col2" -> 2) *: EmptyTuple
   ).enc

[error] value enc is not a member of Tuple1[(String, Int)].
[error] An extension method was tried, but could not be fully constructed:
[error]
[error]     bug1.LabelledList.ne[N, V, T].enc()

In this case, wouldn't the types be available for constructing ne[N, V, T]?

[dwijnand]

I don't understand why the complication. Why not strip it back to something like this, that works:

opaque type Labelled[Name <: String, Value] = Value

object Labelled:
  def apply[Name <: String, Value](name: Name, value: Value): Labelled[Name, Value] = value

sealed abstract class LabelledList

object LabelledList:
  final case class Cons[
      Name <: String,
      Value,
      Tail <: LabelledList
  ](
      col: Labelled[Name, Value],
      tail: Tail
  ) extends LabelledList

  case object Empty extends LabelledList

  type FromTuple[Tup <: Tuple] <: LabelledList = Tup match {
    case (n, v) *: t => Cons[n, v, FromTuple[t]]
    case _           => Empty.type
  }

  trait Enc[Tup <: Tuple]:
    def enc(tup: Tup): FromTuple[Tup]

  given e: Enc[EmptyTuple] with
    def enc(emptyTuple: EmptyTuple) = Empty

  given ne[N <: String, V, T <: Tuple: Enc]: Enc[(N, V) *: T] with
    def enc(tuple: (N, V) *: T) =
      val (n, v) *: t = tuple
      Cons(Labelled(n, v), summon[Enc[T]].enc(t))

  def enc[Tup <: Tuple](tup: Tup)(using enc: Enc[Tup]): FromTuple[Tup] = enc.enc(tup)

class BugTests:
  val t0 = LabelledList.enc(EmptyTuple)
  val t1 = LabelledList.enc(("col2" -> 2) *: EmptyTuple)
  val t2 = LabelledList.enc(("col1" -> 1) *: ("col2" -> 2) *: EmptyTuple)

[andrelfpinto]

Hi @dwijnand, thank you again for your time. It indeed worked without the Singleton. I'm sorry that I didn't undertand this was the problem and thought that it might be a bug. Can you point me where can I read more about that and understand why it only works without Singleton?

Unfortunately with your suggestion this would compile, defeating the purpose of Labelled:

    val obtained = LabelledList.enc(
      ("col1" -> 1) *: ("col2" -> 2) *: EmptyTuple
    )
    val expected = LabelledList.Cons(
      Labelled("col1", 1),
      LabelledList.Cons(
        Labelled("cols00000000000000000000000002", 2),
        LabelledList.Empty
      )
    )

    assertEquals(obtained, expected)

[dwijnand]

Hi @dwijnand, thank you again for your time.

I appreciate that.

I can't remember what has been said recently about Singleton. I think it's been found to not be a solid solution, but I'm not sure what the alternative is. @smarter @mbovel what am I forgetting?