Operator <, похоже, не поддерживает "любой" тип, как это исправить?

#scala #generics #operator-overloading

#scala #дженерики #оператор-перегрузка

Вопрос:

Ниже приведена функция быстрой сортировки, написанная на Scala для сортировки списка смешанных типов (int, double, float и т. Д.). В строке 3 появилась ошибка с надписью «Несоответствие типов, ожидаемое: T => Логическое значение, фактическое: T => Любой не может разрешить символ <«. Как мне это исправить?

IDE Intellij, работающая в Windows 10, выдала это сообщение об ошибке.

 
    def qsort[T](list: List[T]): List[T] = list match {
      case Nil => Nil
      case pivot :: tail =>
        val(smaller, rest) = tail.partition(_ < pivot)
        qsort(smaller) ::: pivot :: qsort(rest)
    }

1. Как бы вы сравнили произвольные типы? T должен быть Comparable тип, если вы хотите его сравнить.

2. В C сопоставимые типы не нужно указывать, если у них есть operator < <= и т.д. Но я не знаком с механизмом в Scala.

3. C проверяет наличие < etc. когда вы вызываете универсальную функцию, но Scala выполняет эту проверку при компиляции функции. Scala должен быть уверен, что он будет работать для всех возможных T , поэтому вам нужно как-то ограничить допустимые типы. Вы можете ограничить сам тип или добавить implicit параметр.

Ответ №1:

Ответ Дмитрия будет работать для любого типа, в который можно неявно преобразовать Ordered[T] . Это немного странно, и в идиоматическом Scala люди часто предпочитают Ordering вместо этого использовать неявный. Таким образом, порядок полностью отделен от реализации T .

 def qsort[T : Ordering](list: List[T]): List[T]

Подпись использует привязку к контексту и [T: Ordering] является синтаксическим сахаром для более подробного

 def qsort[T](list: List[T])(implicit ev: Ordering[T]): List[T]

Если вы пришли с Java, Ordering это Ordered то, что Comparator нужно Comparable . Обратите внимание, что Ordering[T] по духу это очень похоже на T => Ordered[T] , но я думаю, что проще обернуть голову, когда вы новичок. Это также дает вам хороший набор методов для создания и управления Ordering s.

Наконец, обратите внимание, что использование List для метода сортировки, такого как быстрая сортировка, приведет к действительно низкой производительности, потому что добавление к a List есть O(n) . Если производительность вызывает беспокойство, используйте Array с встроенной реализацией быстрой сортировки.

Ответ №2:

Добавить неявный параметр

 def qsort[T](list: List[T])(implicit ev: T => Ordered[T]) = ...