Почему компилятор Scala распознает тип generi c дважды

Question

Scala новичок здесь с запутанной ошибкой компилятора. Мне непонятно, почему компилятор распознает обобщенный c параметр c тип T в msort[T] как тип, отличный от типа аргумента T в (lt: (T, T) => Boolean).

def msort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = {
    val n = xs.length/2
    if (n == 0) xs
    else {
        def merge[T](xs: List[T], ys: List[T]): List[T] = 
            (xs, ys) match {
                case (Nil, _) => ys
                case (_, Nil) => xs
                case (x :: xs1, y :: ys1) => 
                    if (lt(x, y))
                        x :: merge(xs1, ys)
                    else
                        y :: merge(xs, ys1)
            }
        val (fst, snd) = xs splitAt n
        merge(msort(fst)(lt), msort(snd)(lt))
    }
}

Проблема связана со строкой 10 при проверке порядка x и y if (lt(x, y)). Я получаю 2 ошибки несоответствия типов, но не уверен, что пошло не так.

[error] -- [E007] Type Mismatch Error: /..../src/main/scala/Main.scala:10:27 
[error] 10 |                    if (lt(x, y))
[error]    |                           ^
[error]    |                           Found:    (x : T)
[error]    |                           Required: T²
[error]    |
[error]    |                           where:    T  is a type in method merge
[error]    |                                     T² is a type in method msort
[error] -- [E007] Type Mismatch Error: /..../src/main/scala/Main.scala:10:30 
[error] 10 |                    if (lt(x, y))
[error]    |                              ^
[error]    |                              Found:    (y : T)
[error]    |                              Required: T²
[error]    |
[error]    |                              where:    T  is a type in method merge
[error]    |                                        T² is a type in method msort
[error] two errors found

Dev Env

Mac OsX
sbt.version=1.3.2
scalaVersion=2.13.1

Answer 1

Параметр типа T внутреннего метода merge скрывает параметр типа с тем же именем T внешнего метода msort. Вместо этого попробуйте удалить параметр типа из merge следующим образом:

def msort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = {
  val n = xs.length/2
  if (n == 0) xs
  else {
    def merge(xs: List[T], ys: List[T]): List[T] =
      (xs, ys) match {
        case (Nil, _) => ys
        case (_, Nil) => xs
        case (x :: xs1, y :: ys1) =>
          if (lt(x, y))
            x :: merge(xs1, ys)
          else
            y :: merge(xs, ys1)
      }
    val (fst, snd) = xs splitAt n
    merge(msort(fst)(lt), msort(snd)(lt))
  }
}