Higher-kinded types for multisets

Question

I would like to write a Multiset[T, S[_]] class in Scala, which takes 2 type parameters: T is the type of the element, whereas S is the underlying representation of the set. In this multiset, an instance of S[(T, Int)] is constructed (in each pair, T is the element and Int is its number of occurrence). This is possible in C++:

template<typename T, template<typename> S>

Two questions:

How to declare the constraint on S that it must be a set? Does Multiset[T, S[_] <: Set[_]] work?
Is it possible to declare the constraint that an instance of S[(T, Int)] can be instantiated? This can be done in C# using the where S: new() constraint.

Didier Dupont Didier Dupont · Accepted Answer · 2015-03-05T19:44:19

First question: Use S[X] <: Set[X] instead. Using underscore to mark higher order type params is convenient, no need to catch the attention with an useless name, but you can in fact use any identifier. And for this particular case, underscore will not work. You could even do things like S[X] <: Set[List[X]].

Second question: no direct equivalent, however I rarely use that in C# because it implies that object can only be created by the parameterless constructor, which is a big restriction, in force for all possible usage of your code. The user of your class might like for instance to set the capacity at initialization, or use a pool or whatever. Most of the time, I requires a Func<S> delegate in the constructor, and I may add a static factory which accepts new as a convenience as in

class Generic<T> 
{
   public Generic(..., Func<T> factory)
}

static class Generic 
{
  public Generic<T> Create(....) where T : new {
    return new Generic(..., () => new T());
  }
}

In scala, you will need to pass the function. A possible alternative is to use an implicit parameter, e.g.

trait Builder[A] {
   def build(): A
}

object Builder {
  def build[A: Builder] : A = implicitly[Builder[A]].build()
}

class Generic[A: Builder](....) {....
    ...
    // instead of val a = new A()
    val a = Builder.build[A]
    ....
}

Then you can just ensure that a builder is available in implicit scope for your parameter type, and it will be used by default. And you may still pass another one explicitly when the default one is not what you want.

Higher-kinded types for multisets

1 Answers