Обобщение скала-кода в функцию

Question

Поэтому я случайно написал ответ на Haskell на вопрос Scala.Будучи довольно знакомым с Haskell, решение пришло ко мне довольно легко:

myMaxBy :: (a -> a -> Ordering) -> [a] -> [a]
myMaxBy _ [] = undefined
myMaxBy f (x:xs) = foldr step [x] xs
  where step y acc@(z:_) = case f y z of
          GT -> [y]
          EQ -> y:acc
          LT -> acc

Тогда кто-то напомнил мне, что это был вопрос Scala.Я решил перевести свой код в Scala, и после большой боли я согласился:

(List(xs.head) /: xs.tail) { (acc, y) =>
  y compare acc.head match {
    1  => List(y)
    0  => y :: acc
    -1 => acc
  }
}

Но я не мог за всю свою жизнь заставить систему типов Scala подчиниться моей воле и обобщить это вфункция, в которой xs и compare - это входы (в идеале, входы с карри, сначала с компаратором).Хотя это, безусловно, связано с моим общим незнакомством со Scala, я также немного виню в сложной (хотя и очень мощной) системе типов Scala.Можете ли вы сделать что-то за руку и объяснить, как я могу превратить это в обобщенную функцию с сигнатурой типа, аналогичной эквиваленту Haskell?(Читайте: в целом как .) Пожалуйста, также продемонстрируйте использование, если оно сложнее, чем myMaxBy(myCompare)(someList).

Answer 1

Вы пропустили ключевые слова case в своем сопоставлении с шаблоном, которые очень важны!

Все, что вам нужно, это чтобы тип параметра коллекции мог использовать метод compare. В Scala есть две системы сравнения: расширение Ordered или использование Ordering. Между ними есть неявные преобразования, поэтому не имеет большого значения, какой вы выберете; первое, возможно, легче понять.

Во-первых, используя Ordered:

  def myMaxBy[A <% Ordered[A]](xs: List[A]) = {
    (List(xs.head) /: xs.tail) { (acc, y) =>
      y compare acc.head match {
        case 1  => List(y)
        case 0  => y :: acc
        case -1 => acc
      }
    }  
  }

Здесь мы даем наш универсальный тип A a , связанный с представлением , используя <%, что означает «можно видеть как». Это является более общим, чем использование верхней границы <:, и полезно для классов, которые сами не являются Ordered, но имеют неявные преобразования в классы Ordered, например, Int до RichInt.

В качестве альтернативы, если вы хотите, чтобы гибкость позволяла изменять критерии заказа, вы можете написать это так:

  def myMaxBy[A](xs: List[A])(implicit ord: Ordering[A]) = {
    (List(xs.head) /: xs.tail) { (acc, y) =>
      ord.compare(y, acc.head) match {
        case 1  => List(y)
        case 0  => y :: acc
        case -1 => acc
      }
    }
  }

При вызове, если в области видимости есть неявное значение Ordering[A], вы можете не указывать второй аргумент. Этот второй способ также имеет то преимущество, что вы можете определить Ordering для произвольных классов, независимо от того, поддерживают ли они его или нет.

Вы можете вызывать оба, используя, например, myMaxBy(List(1,2,3,4,3,4)). Во втором, если вы хотите, скажем, обратный порядок: myMaxBy(List(1,2,3,4,3,4))(Ordering.Int.reverse).

Еще одна вещь, которую вы можете увидеть в этом контексте, это границы контекста . Например. [A: Ordering]. Это означает то же самое, что и [A](implicit ord: Ordering[A]), что более кратко, за исключением того, что вы не получаете дескриптор на Ordering, поэтому вам нужно вызвать его, используя implicitly. Так что здесь, вероятно, лучше заявить об этом, как указано выше.

Answer 2

Вам нужно либо иметь расширенный порядок типа А, либо лучше, ограничить его, чтобы был доступен класс типа заказа. Первый выглядит так:

def sort[A <: Ordered[A]](xs: List[A]) =
  (List(xs.head) /: xs.tail) { (acc, y) => y compare acc.head match { … } }

Поскольку точки Луиджи еще лучше, лучше использовать границу вида

def sort[A <% Ordered[A]](xs: List[A]) =
  (List(xs.head) /: xs.tail) { (acc, y) => y compare acc.head match { … } }

Лучше использовать класс типа Ordering:

def sort[A](xs: List[A])(implicit ord: Ordering[A]) =
  (List(xs.head) /: xs.tail) { (acc, y) => ord compare (y, acc.head) match { … } }

Вы также можете использовать контекстную границу:

def sort[A: Ordering](xs: List[A]) = {
  val ord = implicitly[Ordering[A]]
  (List(xs.head) /: xs.tail) { (acc, y) => ord compare (y, acc.head) match { … } }
}

хотя синтаксически это немного чище, оно не позволяет вам передавать явное альтернативное упорядочение (например, упорядочение строк без учета регистра).