Use one recursive case class constructor in two sealed traits

Question

I am defining few ADTs representing logic formulas. They all use i.e. And constructor, but then differ in what other constructors they use. I'd like to reuse case class definitions with a hope that I could reuse some code later. I'd like to do something like:

sealed trait Formula
sealed trait PositiveFormula

case class Not(sub) extends Formula
case class And(left, right) extends Formula, PositiveFormula

But this doesn't work for any single type for sub, left and right. So I'd like to say:

sealed trait Formula
sealed trait PositiveFormula

case class Not[A](sub : A)
Not[Formula] extends Formula
case class And(left : A, right : A)
And[Formula] extends Formula
And[PositiveFormula] extends PositiveFormula

A few questions:

1. Is anything like above possible and I just dont know syntax?
2. Is there other solution to "reuse case class constructors" problem?
3. What's your opinion on how useful this would be if possible?

Answer 1

In Scala parametric classes can't extend different parents for different type parameters (only parent's type parameter can vary).

It seems you want to have something like "Not[T] extends T", "And[T] extends T" (pseudocode). See Scala : class[T] extends T?

You can try

sealed trait Formula
sealed trait PositiveFormula

trait NotLike[A] {
  def sub: A

  // your generic code here
}

case class Not(sub: Formula) extends NotLike[Formula] with Formula

trait AndLike[A] {
  def left: A
  def right: A

  // your generic code here
}

case class And(left: Formula, right: Formula) extends 
  AndLike[Formula] with Formula

case class PositiveAnd(left: PositiveFormula, right: PositiveFormula) extends 
  AndLike[PositiveFormula] with PositiveFormula

You can also introduce FormulaLike, a common parent for Formula and PositiveFormula

sealed trait FormulaLike
sealed trait Formula extends FormulaLike
sealed trait PositiveFormula extends FormulaLike

trait NotLike[A <: FormulaLike] {
  def sub: A
}

trait AndLike[A <: FormulaLike] {
  def left: A
  def right: A
}

Is PositiveFormula a Formula or not? Just in case, if so then you can make PositiveFormula extend Formula (instead of introducing FormulaLike).

Or maybe you can try to express your relations between types with type classes (inheritance can be too restrictive, composition should be preferred over inheritance)

https://www.baeldung.com/scala/type-classes (intro to type classes)

https://kubuszok.com/2018/implicits-type-classes-and-extension-methods-part-1/ (one more intro to type classes)

https://tpolecat.github.io/2015/04/29/f-bounds.html (type classes and F-bounds)

https://github.com/milessabin/shapeless/blob/main/core/shared/src/main/scala/shapeless/ops/nat.scala (example of type-level calculations with type classes)

You can have hierarchy of classes (nodes) extending Formula and mark some of the nodes as belonging to the type class IsPositive

// hierarchy
sealed trait Formula
  
// type class
trait IsPositive[A <: Formula]

case class Not[A <: Formula](sub: A) extends Formula
  
case class And[A <: Formula](left: A, right: A) extends Formula
implicit def and[A <: Formula](implicit ev: IsPositive[A]): IsPositive[And[A]] = null

or use phantom types with type classes

// phantom types
type Formula
type PositiveFormula /*<: Formula*/

case class Not[A](sub: A)
case class And[A](left: A, right: A)
    
// type class
trait NotTypeclass[A] {
  type Out
  def apply(sub: A): Out
}

object NotTypeclass {
  type Aux[A, Out0] = NotTypeclass[A] {type Out = Out0}
  def instance[A, Out0](f: A => Out0): Aux[A, Out0] = new NotTypeclass[A] {
    override type Out = Out0
    override def apply(sub: A): Out0 = f(sub)
  }

  implicit def not[A <: Formula]: Aux[A, Not[A] with Formula] =
    instance(sub => Not(sub).asInstanceOf[Not[A] with Formula])
}

def makeNot[A](sub: A)(implicit notTc: NotTypeclass[A]): notTc.Out = notTc(sub)

// type class
trait AndTypeclass[A] {
  type Out
  def apply(left: A, right: A): Out
}

trait LowPriorityAnd {
  type Aux[A, Out0] = AndTypeclass[A] {type Out = Out0}
  def instance[A, Out0](f: (A, A) => Out0): Aux[A, Out0] = new AndTypeclass[A] {
    override type Out = Out0
    override def apply(left: A, right: A): Out0 = f(left, right)
  }

  implicit def and[A <: Formula]: Aux[A, And[A] with Formula] =
    instance((l, r) => And(l, r).asInstanceOf[And[A] with Formula])
}
object AndTypeclass extends LowPriorityAnd {
  implicit def positiveAnd[A <: PositiveFormula]: Aux[A, And[A] with PositiveFormula] =
    instance((l, r) => And(l, r).asInstanceOf[And[A] with PositiveFormula])
}

def makeAnd[A](left: A, right: A)(implicit andTc: AndTypeclass[A]): andTc.Out =
  andTc(left, right)

makeAnd(??? : PositiveFormula, ???): PositiveFormula
makeAnd(??? : Formula, ???): Formula
makeNot(??? : Formula): Formula
// makeNot(??? : PositiveFormula) // doesn't compile

makeNot(makeAnd(??? : Formula, ???)): Formula
makeAnd(makeNot(??? : Formula), makeAnd(??? : Formula, ???)): Formula
makeAnd(makeAnd(??? : Formula, ???), makeAnd(??? : Formula, ???)): Formula
makeAnd(makeAnd(??? : PositiveFormula, ???), makeAnd(??? : PositiveFormula, ???)): PositiveFormula

or use phantom types keeping type classes only for type-level calculations

type Formula
type PositiveFormula /*<: Formula*/

case class Not[A](sub: A)
case class And[A](left: A, right: A)

trait NotTypeclass[A] {
  type Out
}
object NotTypeclass {
  type Aux[A, Out0] = NotTypeclass[A] { type Out = Out0 }

  implicit def not[A <: Formula]: Aux[A, Formula] = null
}

def makeNot[A](sub: A)(implicit
  notTc: NotTypeclass[A]
): Not[A] with notTc.Out = Not(sub).asInstanceOf[Not[A] with notTc.Out]

trait AndTypeclass[A] {
  type Out
}
trait LowPriorityAnd {
  type Aux[A, Out0] = AndTypeclass[A] {type Out = Out0}

  implicit def and[A <: Formula]: Aux[A, Formula] = null
}
object AndTypeclass extends LowPriorityAnd {
  implicit def positiveAnd[A <: PositiveFormula]: Aux[A, PositiveFormula] = null
}

def makeAnd[A](left: A, right: A)(implicit
  andTc: AndTypeclass[A]
): And[A] with andTc.Out = And(left, right).asInstanceOf[And[A] with andTc.Out]

or use phantom types without type classes

type Formula
type PositiveFormula /*<: Formula*/

case class Not[A](sub: A)
case class And[A](left: A, right: A)

def makeNot[A <: Formula](sub: A): Not[A] with Formula = 
  Not(sub).asInstanceOf[Not[A] with Formula]

def makeAnd[A <: Formula](left: A, right: A): And[A] with Formula =
  And(left, right).asInstanceOf[And[A] with Formula]
def makePositiveAnd[A <: PositiveFormula](left: A, right: A): And[A] with PositiveFormula =
  And(left, right).asInstanceOf[And[A] with PositiveFormula]

Formula and PositiveFormula are abstract types rather than traits to avoid ClassCastException.

Answer 2

You need types for case class fields. You can probably make PositiveFormula extend Formula too. For example, this would work for Boolean operands.

sealed trait Formula
sealed trait PositiveFormula extends Formula
case class Not(sub:Boolean) extends Formula
case class And(left:Boolean, right:Boolean) extends PositiveFormula