Seq [A] расширяет Упорядоченный [Seq [A]]

Question

Я пытаюсь сделать последовательность (например, другие типы коллекций также возможной) сопоставимой с другими последовательностями.

class RichSeq[A](val seq: Seq[A]) extends Ordered[RichSeq[A]]

Конечно, есть неявное преобразование в упомянутом объекте пакета:

implicit def seq2RichSeq[A](s: Seq[A]) = new RichSeq(s)

Сравнение означает, что первый размер имеет значение, чем каждый элемент. Код проясняет:

class RichSeq[A](val seq: Seq[A]) extends Ordered[RichSeq[A]] { 
  def compare(s: RichSeq[A]) = {
    seq.size compare s.seq.size match {
      case 0 => seq.view.zip(s.seq).map { case (x,y) => ord.compare(x,y) }.dropWhile(_ == 0).headOption.getOrElse(0)
      case x => x
    }
  }
}

Но это не компилируется (конечно), потому что для сравнения элементов нужен порядок, поэтому я попробовал это:

class RichSeq[A](val seq: Seq[A]) extends Ordered[RichSeq[A]] { 
  def compare(s: RichSeq[A])(implicit ord: Ordering[A]) = {
    // ...
  }
}

Теперь сигнатура метода сравнения не подходит, поэтому я переместил неявный ord в сигнатуру класса (и адаптировал неявное преобразование):

implicit def seq2RichSeq[A](s: Seq[A])(implicit ord: Ordering[A]) = new RichSeq(s)
class RichSeq[A](val seq: Seq[A])(implicit ord: Ordering[A]) extends Ordered[RichSeq[A]] { 
  def compare(s: RichSeq[A]) = {
      // ...
    }
  }

Но теперь у меня проблема в том, что все другие методы в RichSeq, которые я хочу использовать через implicit на Seq[A], также требуют неявного Ordering[A], и я не всегда могу его доставить. Иногда я использую мои RichSeq методами без упорядочивания, а иногда и методом сравнения.

Например, иногда я звоню

def distinctBy[B](f: A => B): Seq[A] = {
  seq.foldLeft { (Buffer[A](),MutMap[B,A]()) } {
    case ((b,m),x) if m contains f(x) => (b,m)
    case ((b,m),x) => 
      m += f(x) -> x
      b += x
      (b,m)
  }._1
}

Между тем я не могу определить Ordering[A].

Я вижу одно решение иметь два разных класса (с двумя неявными преобразованиями):

class RichSeqOrderable[A](val seq: Seq[A])(implicit ord: Ordering[A]) extends Ordered[RichSeqOrderable[A]]

class RichSeq[A](val seq: Seq[A])

Но я думаю, что это ломает мысль о том, что все вместе?!?

Answer 1

Мое обычное предисловие о том, что я не обязательно буду делать что-то подобное, но чтобы использовать вопрос в качестве предлога для освещения некоторых менее известных функций: здесь, если доступен какой-либо неявный порядок, он будет использовать его, но в противном случае он упорядочит их по хэш-коду.

package object foo {
  implicit def seq2RichSeq[A](s: Seq[A])(implicit ord: Ordering[A] = Ordering[Int].on((_: A).##)) = new RichSeq(s)
}
package foo {
  class RichSeq[A](val seq: Seq[A])(implicit ord: Ordering[A]) extends Ordered[RichSeq[A]] { 
    def compare(s: RichSeq[A]) = {
      seq.size compare s.seq.size match {
        case 0 => seq.view.zip(s.seq).map { case (x,y) => ord.compare(x,y) }.dropWhile(_ == 0).headOption.getOrElse(0)
        case x => x
      }
    }
  }
}

Answer 2

Я пошел за чем-то похожим на предложение paulp :

class RichSeq[A](val seq: Seq[A])(implicit optionalOrd: Option[Ordering[A]] = None) extends Ordered[RichSeq[A]] {
  def compare(s: RichSeq[A]) = {
    seq.size compare s.seq.size match {
      case 0 => seq.view.zip(s.seq).map { case (x,y) => optionalOrd.map(_.compare(x,y)).getOrElse(0) }.dropWhile(_ == 0).headOption.getOrElse(0)
      case x => x
    }
  }
}

object RichSeq {
  implicit def orderingToSome[A](implicit ord: Ordering[A] = null) = Option(ord)
  implicit def seq2RichSeq[A](s: Seq[A])(implicit ord: Option[Ordering[A]]) = new RichSeq(s)
}

Нехорошо иметь слишком много следствий, особенно типов в стандартной библиотеке. Тем не менее, я думаю, что Ordering[A] => Option[Ordering[A]] настолько безопасен, насколько это возможно.

О цепочке имплицитов

В Scala есть ограничение на автоматическое преобразование для добавления метода, заключающееся в том, что при поиске методов он не будет применять более одного преобразования. Например:

class A(val n: Int)
class B(val m: Int, val n: Int)
class C(val m: Int, val n: Int, val o: Int) {
  def total = m + n + o
}

// This demonstrates implicit conversion chaining restrictions
object T1 { // to make it easy to test on REPL
  implicit def toA(n: Int) = new A(n)
  implicit def aToB(a: A) = new B(a.n, a.n)
  implicit def bToC(b: B) = new C(b.m, b.n, b.m + b.n)

  // won't work
  println(5.total)
  println(new A(5).total)

  // works
  println(new B(5, 5).total)
  println(new C(5, 5, 10).total)
}

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

// def m[A <% B](m: A) is the same thing as
// def m[A](m: A)(implicit ev: A => B)

object T2 {
  implicit def toA(n: Int) = new A(n)
  implicit def aToB[A1 <% A](a: A1) = new B(a.n, a.n)
  implicit def bToC[B1 <% B](b: B1) = new C(b.m, b.n, b.m + b.n)

  // works
  println(5.total)
  println(new A(5).total)
  println(new B(5, 5).total)
  println(new C(5, 5, 10).total)
}

«Волшебство!», Скажете вы. Не так. Вот как компилятор будет переводить каждый из них:

object T1Translated {
  implicit def toA(n: Int) = new A(n)
  implicit def aToB(a: A) = new B(a.n, a.n)
  implicit def bToC(b: B) = new C(b.m, b.n, b.m + b.n)

  // Scala won't do this
  println(bToC(aToB(toA(5))).total)
  println(bToC(aToB(new A(5))).total)

  // Just this
  println(bToC(new B(5, 5)).total)

  // No implicits required
  println(new C(5, 5, 10).total)
}

object T2Translated {
  implicit def toA(n: Int) = new A(n)
  implicit def aToB[A1 <% A](a: A1) = new B(a.n, a.n)
  implicit def bToC[B1 <% B](b: B1) = new C(b.m, b.n, b.m + b.n)

  // Scala does this
  println(bToC(5)(x => aToB(x)(y => toA(y))).total)
  println(bToC(new A(5))(x => aTo(B(x)(identity _)).total)
  println(bToC(new B(5, 5))(identity _).total)

  // no implicits required
  println(new C(5, 5, 10).total)
}

Таким образом, в то время как bToC используется как неявное преобразование, aToB и toA передаются как неявные параметры , а не как цепочка неявных преобразований.

Answer 3

Я не закодировал его полностью, но почему бы вам не сделать это:

class RichSeq[A <: Ordered[A]](val seq: Seq[A]) extends Ordered[RichSeq[A]] {
  import Ordering.ordered 

  ...
}

Импортированное неявное преобразование даст вам Ordering[A] при необходимости.