Вопросы Теги

Универсальный quicksort в Scala

Я играл вокруг с Scala недавно, и думал о том, как реализовать универсальную версию quicksort в нем (только для получения лучшего сопереживания языку)

Я придумал что-то вроде этого

object Main {
  def qs[T](a: List[T], f: (T, T) => Boolean): List[T] = { 
    if (a == Nil) return a
    val (l, g) = a drop 1 partition (f(a(0),(_:T)))
    qs(l, f) ::: List(a(0)) ::: qs(g, f)
  }

  def main(args: Array[String]): Unit = { 
    val a = List(5,3,2,1,7,8,9,4,6)
    val qsInt = qs(_: List[Int], (_: Int) > (_: Int))
    println(qsInt(a))
  }

}

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

val (l, g) = a drop 1 partition (a(0) >)

Как я могу сказать компилятору, что T только должен реализовать большее - чем оператор, чтобы быть поддающимся сортировке этой функцией?

С уважением

8
задан Robert Karl 22 February 2010 в 21:58
поделиться

2 ответа

def qsort[T <% Ordered[T]](list: List[T]): List[T] = {
  list match {
  case Nil => Nil     
  case x::xs =>        
    val (before, after) = xs partition (_ < x)
    qsort(before) ++ (x :: qsort(after))
  }
}
14
ответ дан 5 December 2019 в 07:34
поделиться

Поскольку Роджер рассмотрел случай Заказанный ], позвольте мне рассказать о Заказе : 

def qsort[T](list: List[T])(implicit ord: Ordering[T]): List[T] = list match {
  // import ord._ // enables "_ < x" syntax
  case Nil => Nil
  case x :: xs =>
    val (before, after) = xs partition (ord.lt(_, x))
    qsort(before) ::: x :: qsort(after)
}

Использование Порядок имеет два основных Преимущества:

  1. Тип T не обязательно должен быть создан как Упорядоченный .
  2. Можно легко предоставить альтернативный порядок.

Например, в Scala 2.8: 

def sortIgnoreCase(strs: List[String]) = {
  val myOrdering = Ordering.fromLessThan { (x: String, y: String) => 
    x.toLowerCase < y.toLowerCase
  }
  qsort(strs)(myOrdering)
}
8
ответ дан 5 December 2019 в 07:34
поделиться
Другие вопросы по тегам:

Похожие вопросы: