Scala constructor abstraction

Question

The following is possible in Scala:

scala> val l = List
l: scala.collection.immutable.List.type = scala.collection.immutable.List$@7960c21a

scala> l ( 1, 2, 3 )
res0: List[Int] = List(1, 2, 3)

In other words, Scala has higher-order polymorphism. I would like to use higher-order polymorphism to do the following.

sealed abstract class A { def eval () : A }
case class A0 () extends A { ... }
case class A1 ( a : A ) extends A { ... }
case class A2 ( a : A, b : A ) extends A { ... }
....

So I have a bunch of case classes, subclasses of A, whose constructors don't necessarily take the same numbers of arguments. I also would like to have a 'generic' case class, something like this:

case class ApplyA ( c : ???, l : List [ A ] ) extends A {
   def eval () : A = { ??? } }

The idea is that ApplyA takes as first argument a constructor for something that is a subtype of A, and a list of arguments. The eval method then constructs an appropriate class with the constructor if possible (i.e. the list has the right length) and returns it (this corresponds to l ( 1, 2, 3) in the List example above). What would be the type of the argument of the first constructor for ApplyA?

This should be possible with higher-order polymorphism, but I could not work out how. I know that I can do this even without using higher-order polymorphism by simply wrapping constructors in functions and then passing these functions as first argument to the constructor for ApplyA, but I'd like to understand how to use higher-order polymorphism directly.

Answer 1

@alexey_r is quite right that your List example doesn't involve higher-order polymorphism. But if you're prepared to use some type-level heavy artillery you can abstract over the arity of your A{0,1,2} constructors to get something that looks quite close to what you're asking for.

The first point to note is that, as written, your 'generic' class can't possibly be implemented,

case class ApplyA(c : ???, l : List[A]) ...

because there's no compile time checkable relationship between the arity of the constructor c and the length of the list l. We can fix that problem by replacing the List with an HList and helping ourselves to a conversion from ordinary functions with arbitrary arity to functions with a single HList argument,

import shapeless.HList._
import shapeless.Functions._

sealed abstract class A { def eval() : A }
case class A0 () extends A { def eval() = this }
case class A1 ( a : A ) extends A  { def eval() = this }
case class A2 ( a : A, b : A ) extends A  { def eval() = this }

case class ApplyA[C, L <: HList, HF](c : C, l : L)
  (implicit hl : FnHListerAux[C, HF], ev : HF <:< (L => A)) extends A {
    def eval () : A = hl(c)(l)
  }

val a : A = A0()

val a0 = ApplyA(A0.apply _, HNil)
val a1 = ApplyA(A1.apply _, a :: HNil)
val a2 = ApplyA(A2.apply _, a :: a :: HNil)

The implicit argument hl : FnHListerAux[C, HF] provides a conversion from your constructor, whatever it's arity, to a function from a single HList argument. And the implicit argument ev : HF <:< (L => A) witnesses that the length of the supplied HList of constructor arguments is of the correct length (and types FWIW, but that's barely relevant in this example).

Answer 2

The problem is that the List example doesn't involve any higher-order polymorphism at all. List.apply just takes a variable number of parameters:

def apply(xs: A*)

Higher-order polymorphism involves methods, or types, which take type constructors as type parameters, e.g.

def fmap[F[_], A](x: F[A]): F[B]

So no, you can't do it using higher-order polymorphism.