Scala methods and higher-kinded type parameters

Question

I am trying to define a method in scala that takes a generic type of S[_] <: Seq[Double] and returns a S[FixedLoad] (FixedLoad is a concrete type). But my implementation gives me errors and I can't figure out why. Despite I have tried so many times to understand parametric types and higher-kinded types, my knowledge grows so slow.

What I am trying to achieve is to not lose the concrete type of S (the sequence subtype).

Here is the code:

import scala.collection.generic.CanBuildFrom

class FixedLoad(val id: Int, val positionInT: Int, val amplitude: Double) {
  override def toString: String = s"FixedLoad($id, $positionInT, $amplitude)"
}

object Load {

  implicit def toFixedLoads[S[_] <: Seq[Double]](l: S[Double])(implicit cbf: CanBuildFrom[Nothing, FixedLoad, S[FixedLoad]]): S[FixedLoad] = {
    l.map(_ => new FixedLoad(1, 1, 1)).to[S]
  }

  def main(args: Array[String]): Unit = {
    println(toFixedLoads(List(1.0, 2.0, 3.0)))
  }

}

and the errors:

Error:(16, 13) inferred type arguments [List] do not conform to method toFixedLoads's type parameter bounds [S[_] <: Seq[Double]]
    println(toFixedLoads(List(1.0, 2.0, 3.0)))

Error:(16, 30) type mismatch;
 found   : List[Double]
 required: S[Double]
    println(toFixedLoads(List(1.0, 2.0, 3.0)))

Cutout

Answer 1

Short answer:

Change toFixedLoads[S[_] <: Seq[Double]] to toFixedLoads[S[A] <: Seq[A]]

Long answer:

When you say S[_], that's a higher kinded type. Or, in other words, it's a type constructor. That means it takes a type to produce the final proper type. Here are some examples:

• List - takes a type, e.g. Int, to produce the proper type List[Int]
• Option - takes a type, e.g. Int, to produce the proper type Option[Int]

etc.

Type constructors of this kind are often represented as * -> *. You provide one type and you get a type back. There are other kinds as well; for example, Map and Either need two types to produce the proper type (e.g. Map[Int, String] or Either[Error, Foo]), so their kind is * -> * -> *. Think of it as a curried type constructor; takes a type and returns a function that takes a type and then you get the final, proper type. Or in other words, takes two types to produce the final, proper type. You might also have a type constructor that needs a type constructor to build the proper type (e.g. Monad[F[_]]), in which case the kind is (* -> *) -> * (for example, List -> Monad[List]).

So when you say your method is expecting a parameter of type S[Double] and you pass List(1.0, 2.0, 3.0), compiler infers S to be List, and it complains about List[A] not being a subtype of Seq[Double] for any A. Your first attempt at fixing this might be F[_] <: Seq[_], but that can't compile, because the inner types still don't align. We need to "connect" them with something like F[A] <: Seq[A] for some A, which can be written simply as F[A] <: Seq[A].

A good question might be "can I say S <: Seq[Double]?" Sure, S represents a proper type, so you totally could! Something like this works just fine:

def foo[S <: Seq[Double]](s: S) = println(s)
foo(List(1.0, 2.0)) // prints List(1.0, 2.0)

But of course, your S has a "hole" in it, because your method parameter is of type S[Double], so it's not applicable in your case.

Katalin

I strongly suggest not writing S[Double] <: Seq[Double]. Double doesn't refer to the standard library class when you do that. Rather, Double is a local type variable. The bound S[Double] <: Seq[Double], in this context, means "for all types Double, then S[Double] <: Seq[Double]". Write something clearer, like S[X] <: Seq[X]. You can observe this meaning in class X[+A]; def m[S[Double] <: X[Double]](s: S[Int]): X[Int] = s. To convert S[Int] to X[Int], the quantified bound is instantiated with Double = Int to get S[Int] <: X[Int]. – Nyaya

@Nyaya Agreed, fixed. Thanks. – Katalin

I think this answer needs more extensive rewording. For one, "By fixing your S[_] into S[A], you say that you don't really need a type constructor" is blatantly false. The method still needs a type constructor; it's just that there's a bound on it. – Nyaya

And Map/Either are very much not curried and their kind shouldn't be represented as * -> * -> *. – Flats

@Nyaya "A different bound", since there are bounds in both cases too. – Flats

@Alexey Romanov I disagree. If we allow ourselves to see Map[A, B] as a function on the type level (A, B) => Map[A, B], than we can equally view it as A => B => Map[A, B]. Sure, it's not curried on the syntax level; we can't just provide A and obtain a B => Map[A, B], but the principle stays. The only reason I mentioned currying is to justify * -> * -> *, which is a common way of representing such HKT. @Nyaya Again agreed, my wording was completely off. Please check if the answer makes more sense now. Answering questions like these helps me improve my own knowledge too. – Katalin

@Katalin This is the common way to represent the kind (not the higher-kinded type) in Haskell, where they are curried, in Scala I can see no reason to use it instead of (*, *) -> *. On the other hand, after checking, this notation is the one used in the original adriaanm.github.io/files/higher.pdf paper, and in the output of :kind. So I still don't like it, but it does seem to be the standard one. – Flats

@Alexey Romanov Yeah, I agree it's misleading in Scala, but I assumed it's adopted from general notation. It's good advice to keep this in mind, thanks. – Katalin

@Katalin "compiler infers S[_] to be List, and it complains about List not being a subtype of Seq[Double]" I'd rather say it infers S to be List and complains about List[A] not being a subtype of Seq[Double] for all A, which is what the bound requires. An example of a higher-kinded type satisfying the bound would be type LD[A] = List[Double]. "F[A] <: Seq[A] for some A" should be "for all A". – Flats