Creating an instance of the self type in Scala

Question

I am not sure whether the title of the question is phrased correctly in Scala type terminology... I am facing a problem that is somewhat analogous to what Scala collections manage with CanBuildFrom.

There is a hierarchy of higher-kinded types and a parallel hierarchy of containers (not necessarily collections) of those types. An operation that, say, filters the items in the container, should return the exact type of the container that the operation is executed on, with the items filtered.

The problem I am encountering is that I can't find the right approach to restricting the implicit evidence requirement to the exact type of container to be constructed without passing the container type explicitly.

A simplified version of the setup I'm dealing with is below. I'd appreciate some advice on how to approach this issue.

@implicitNotFound(msg = "Cannot construct a ${B} from ${A} with arguments of type ${Args}.")
trait CanConstruct[A, -Args, +B] {
  def apply(args: Args): B
}

class A1

trait C1[A <: A1] {
  def a: A
  def active: Boolean
}
trait C1s[C <: C1[A] forSome {type A <: A1}] {
  def values: Seq[C]
  // @note something like def active[From <: C1s[_]]... will find implicits
  //       but will be happy to use a super-type's implicit for a subtype's      
  def active[To[_ <: C]](implicit builder: CanConstruct[To[_], Seq[C], To[C]]): To[C] =
    builder(values.filter(_.active))
}

class C2(val a: A1, val active: Boolean) extends C1[A1]
class C2s[C <: C2](val values: Seq[C]) extends C1s[C]
object C2s {
  class C2CanConstruct[C <: C2] extends CanConstruct[C2s[_], Seq[C], C2s[C]] {
    def apply(args: Seq[C]): C2s[C] = new C2s(args)
  }
  implicit def C2CanConstruct[C <: C2] = new C2CanConstruct[C]
}

class C3s[C <: C2](values: Seq[C]) extends C2s[C](values)
object C3s {
  class C3CanConstruct[C <: C2] extends CanConstruct[C3s[_], Seq[C], C3s[C]] {
    def apply(args: Seq[C]): C3s[C] = new C3s(args)
  }
  implicit def C3CanConstruct[C <: C2] = new C3CanConstruct[C]
}

val a = new A1()
val cs = Seq(new C2(a, true), new C2(a, false))

// How can active pick the corresponding C?CanConstruct implicit automatically?
// i.e., new C2s(cs).active returns C2s[...] and 
//       new C3s(cs).active returns C3s[...]
new C2s(cs).active[C2s]
new C3s(cs).active[C3s]

Update:

The type member approach in the answer below is promising, but fails to handle the case where C1 has type parameters (Scastie). I omitted that detail in the original question formulation with the desire to strike a balance between necessary & unnecessary complexity. When it comes to the type member approach, it seems the additional complexity is necessary.

user_11882002 · Answer

Edit 2: Here's a fixed version of the Scastie you linked. The problem there was that every use of C1.T/C2.T is different, so C <: C1.T was not necessarily the same thing as T <: C1.T. The link above is almost the same as Dmytro Mitin's answer so I'm not putting it here. The only thing different is that it uses type T = C1[_] instead of type T = C1[A] forSome {type A <: Config}.

An alternative without implicits:

@annotation.implicitNotFound(
  msg = "Cannot construct a ${To} from ${From} with arguments of type ${Args}."
)
trait CanConstruct[+From, -Args, +To] {
  def apply(args: Args): To
}

class Config

trait C1[Cfg <: Config] {
  type Config = Cfg
  def config: Config
}
object C1 {
  type T = C1[_]
}
trait C1s[C <: C1.T] {
  type From <: C1s[_]
  type To[T <: C] <: C1s[T]
  def values: Seq[C]
  protected def builder: CanConstruct[From, Seq[C], To[C]]
  def filter(f: C => Boolean): To[C] =
    builder(values.filter(f))
}

class C2[Cfg <: Config](val config: Cfg, val active: Boolean) extends C1[Cfg]
object C2 {
  type T = C2[_]
}
abstract class C2s[C <: C2.T](val values: Seq[C]) extends C1s[C] {
  type From <: C2s[_]
  type To[T <: C] <: C2s[T]
}
object C2s {
  def apply[C <: C2.T](values: Seq[C]) =
    new C2s(values) { 
      type From = C2s[_]
      type To[T2 <: C] = C2s[T2] 
      val builder = new CanConstruct[C2s[_], Seq[C], RefinedC2s[C]] {
        def apply(args: Seq[C]) = C2s(args)
      }
    }
}

//Final because its type members are invariant
final class C3s[C <: C2.T](values: Seq[C]) extends C2s[C](values) {
  type From = C3s[_]
  type To[T <: C] = C3s[T]
  protected val builder = new CanConstruct[C3s[_], Seq[C], C3s[C]] {
    def apply(args: Seq[C]): C3s[C] = new C3s(args)
  }
}

val cfg = new Config
val cs = Seq(new C2(cfg, true), new C2(cfg, false))

val c2s = C2s(cs).filter(_.active).filter(_.active)
val c3s = new C3s(cs).filter(_.active).filter(_.active)

Scastie

Edit: You can also make To an abstract type member. The issue here is that To will have to be abstract in C2, meaning that the implicit won't be found. To work around this, we can make a refined type like type RefinedC2s[T <: C2] = C2s[T] { type To[T <: C2] = C2s[T] }, and make an apply method in your companion object that returns it (you won't have to do this for C3s). You'll also have to make the constructor protected to make sure no one creates a C2 with an abstract To.

trait C1 {
  def active: Boolean
}
trait C1s[C <: C1] {
  type To[T <: C] <: C1s[T]
  //R is so that it can be RefinedC2s instead of C2s
  def active[R <: To[C]](implicit builder: CanConstruct[To[_], Seq[C], R]): R = 
    builder(values.filter(_.active))
}

class C2s[C <: C2](val values: Seq[C]) extends C1s[C] {
  type To[T <: C2] <: C2s[T]
}
object C2s {
  type RefinedC2s[T <: C2] = C2s[T] { type To[T <: C2] = C2s[T] }
  def apply[C <: C2](values: Seq[C]) = new C2s(values) { type To[T <: C2] = C2s[T] }
  class C2CanConstruct[C <: C2] extends CanConstruct[C2s[_], Seq[C], RefinedC2s[C]] {
    def apply(args: Seq[C]) = C2s(args)
  }
}

class C3s[C <: C2](values: Seq[C]) extends C2s[C](values) {
  type To[T <: C2] = C3s[T]
}

You can use it like this, and don't need to worry about casting to RefinedC2s each time.

val c2s = C2s(cs).active.active.active.active.active
val c3s = new C3s(cs).active.active

Scastie

Consider making an implicit class to add active as an extension method. This makes it a whole lot easier than using To as a type parameter (or as a type member, which I previously experimented with)

Here's a naive attempt at doing this. I've removmed a and A1 because they mostly just cluttered up the example. I also made A covariant in CanBuildFrom so that I could pass it C2s[Nothing], etc., because I had no idea what it was supposed to do.

import scala.language.existentials

@annotation.implicitNotFound(msg = "Cannot construct a ${B} from ${A} with arguments of type ${Args}.")
trait CanConstruct[+A, -Args, B] {
  def apply(args: Args): B
}

trait C1 {
  def active: Boolean
}
trait C1s[C <: C1] {
  def values: Seq[C]
}

implicit class CsOps[C <: C1, Cs[_ <: C] <: C1s[_ <: C]](cs: Cs[C]) {
  def active(implicit builder: CanConstruct[Cs[Nothing], Seq[C], Cs[C]]): Cs[C] = 
    builder(cs.values.filter(_.active))
}

class C2(val active: Boolean) extends C1
class C2s[C <: C2](val values: Seq[C]) extends C1s[C]

object C2s {
  class C2CanConstruct[C <: C2] extends CanConstruct[C2s[Nothing], Seq[C], C2s[C]] {
    def apply(args: Seq[C]): C2s[C] = new C2s(args)
  }
  implicit def C2CanConstruct[C <: C2] = new C2CanConstruct[C]
}

class C3s[C <: C2](values: Seq[C]) extends C2s[C](values)

object C3s {
  class C3CanConstruct[C <: C2] extends CanConstruct[C3s[Nothing], Seq[C], C3s[C]] {
    def apply(args: Seq[C]): C3s[C] = new C3s(args)
  }
  implicit def C3CanConstruct[C <: C2] = new C3CanConstruct[C]
}

val cs = Seq(new C2(true), new C2(false))

val c2s: C2s[C2] = new C2s(cs).active
val c3s: C3s[C2] = new C3s(cs).active

c2s -> C2s(List(C2(true))): C2s[C2]
c3s -> C2s(List(C2(true))): C3s[C2]

Scastie

user_5249621 · Answer

Regarding your updated question (with "real-world" code) try the following modified version of @user's second approach with abstract type member To. I modified upper bounds of To's parameter in C1s (necessary), C2s (necessary), C3s (optional) (otherwise overriding of To doesn't work) and made the type class CanConstruct covariant with respect to To (otherwise implicit is not found).

@annotation.implicitNotFound(msg = "Cannot construct a ${To} from ${From} with arguments of type ${Args}.")
trait CanConstruct[+From, -Args, +To] {
  def apply(args: Args): To
}

class Config

trait C1[Cfg <: Config] {
  type Config = Cfg
  def config: Config
}
object C1 {
  type T = C1[A] forSome {type A <: Config}
}
trait C1s[C <: C1.T] {
  type To[T <: /*C1.T*/C] <: C1s[T]
  def values: Seq[C]
  def filter[R <: To[C]](f: C => Boolean)(implicit builder: CanConstruct[To[_], Seq[C], R]): R =
    builder(values.filter(f))
}

class C2[Cfg <: Config](val config: Cfg, val active: Boolean) extends C1[Cfg]
object C2 {
  type T = C2[A] forSome {type A <: Config}
}
class C2s[C <: C2.T](val values: Seq[C]) extends C1s[C] {
  type To[T <: /*C2.T*/C] <: C2s[T]
}
object C2s {
  type RefinedC2s[C <: C2.T] = C2s[C] { type To[T <: /*C2.T*/C] = C2s[T] }
  def apply[C <: C2.T](values: Seq[C]) = new C2s(values) { type To[T <: /*C2.T*/C] = C2s[T] }
  class C2CanConstruct[C <: C2.T] extends CanConstruct[C2s[_], Seq[C], RefinedC2s[C]] {
    def apply(args: Seq[C]) = C2s(args)
  }
  implicit def C2CanConstruct[C <: C2.T] = new C2CanConstruct[C]
}

class C3s[C <: C2.T](values: Seq[C]) extends C2s[C](values) {
  type To[T <: /*C2.T*/C] = C3s[T]
}
object C3s {
  class C3CanConstruct[C <: C2.T] extends CanConstruct[C3s[_], Seq[C], C3s[C]] {
    def apply(args: Seq[C]): C3s[C] = new C3s(args)
  }
  implicit def C3CanConstruct[C <: C2.T] = new C3CanConstruct[C]
}

val cfg = new Config
val cs = Seq(new C2(cfg, true), new C2(cfg, false))

implicitly[CanConstruct[C2s[_], Seq[C2[Config]], C2s[C2[Config]]]]
implicitly[CanConstruct[C3s[_], Seq[C2[Config]], C3s[C2[Config]]]]

val c2s = C2s(cs).filter(_ => true)
val c3s = new C3s(cs).filter(_ => true)
// val idontwork = new C2s(cs).filter(_ => true) //Doesn't work because `To` is abstract

c2s
c3s

https://scastie.scala-lang.org/JW9ZTNtnS1afRYvhBHqtWw

Honestly your type model becomes pretty complicated. You should reconsider whether you really need all of those stuff (mixture of existentials, generics, higher kinds, type classes, variances, types...).

Creating an instance of the self type in Scala

2 Answers