维基百科quicksort示例中使用的Scala语法的分步说明

发布时间：2020-12-16 09:41:35 所属栏目：安全来源：网络整理

导读：我正在努力了解维基百科的 Scala quicksort example。样品如何逐步拆解，所涉及的所有句法糖是什么意思？ def qsort: List[Int] = List[Int] = { case Nil = Nil case pivot :: tail = val (smaller,rest) = tail.partition(_ pivot) qsort(smaller) ::: piv

我正在努力了解维基百科的 Scala quicksort example。样品如何逐步拆解，所涉及的所有句法糖是什么意思？

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

在这个阶段我可以收集qsort是一个不需要参数的函数，通过使用模式匹配，列表操作和递归调用返回实现quicksort的新Function1 [List [Int]，List [Int]]。但是我不能弄清楚枢轴来自哪里，在这种情况下，模式匹配语法究竟如何工作。

更新：

感谢大家的伟大的解释！

我只想分享另一个在Scala by Example Scala by Example发现的quicksort实现的例子。尽管基于数组，而不是列表，而不是一个炫耀在varios Scala功能方面，我个人觉得它比它的维基百科更加复杂对等方面，而且更加清晰，并且基础算法的点表达：

def sort(xs: Array[Int]): Array[Int] = {
    if (xs.length <= 1) xs
    else {
        val pivot = xs(xs.length / 2)
        Array.concat(
            sort(xs filter (pivot >)),xs filter (pivot ==),sort(xs filter (pivot <)))
    }
}

解决方法

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

让我们重写一下。首先，使用Function1的实例替换函数文字：

def qsort: List[Int] => List[Int] = new Function1[List[Int],List[Int]] {
  def apply(input: List[Int]): List[Int] = input match {
    case Nil => Nil 
    case pivot :: tail => 
      val (smaller,rest) = tail.partition(_ < pivot) 
      qsort(smaller) ::: pivot :: qsort(rest) 
  }
}

接下来，我将使用等效的if / else语句替换模式匹配。请注意，它们是等同的，不一样。模式匹配的字节码更优化。例如，下面的第二个if和异常抛出不存在，因为编译知道如果第一个失败，总是会发生第二个匹配。

def qsort: List[Int] => List[Int] = new Function1[List[Int],List[Int]] {
  def apply(input: List[Int]): List[Int] = if (input == Nil) {
    Nil
  } else if (input.isInstanceOf[::[_]] && 
             scala.collection.immutable.::.unapply(input.asInstanceOf[::[Int]]) != None) {
    val unapplyResult = scala.collection.immutable.::.unapply(input.asInstanceOf[::[Int]]).get
    val pivot = unapplyResult._1
    val tail = unapplyResult._2
    val (smaller,rest) = tail.partition(_ < pivot) 
    qsort(smaller) ::: pivot :: qsort(rest) 
  } else {
    throw new scala.MatchError(input)
  }
}

实际上，val(更小，休息)也是模式匹配，所以我们来分解它：

def qsort: List[Int] => List[Int] = new Function1[List[Int],List[Int]] {
  def apply(input: List[Int]): List[Int] = if (input == Nil) {
    Nil
  } else if (input.isInstanceOf[::[_]] && 
             scala.collection.immutable.::.unapply(input.asInstanceOf[::[Int]]) != None) {
    val unapplyResult0 = scala.collection.immutable.::.unapply(input.asInstanceOf[::[Int]]).get
    val pivot = unapplyResult0._1
    val tail = unapplyResult0._2
    val tmp0 = tail.partition(_ < pivot)
    if (Tuple2.unapply(tmp0) == None)
      throw new scala.MatchError(tmp0)
    val unapplyResult1 = Tuple2.unapply(tmp0).get
    val smaller = unapplyResult1._1
    val rest = unapplyResult1._2
    qsort(smaller) ::: pivot :: qsort(rest) 
  } else {
    throw new scala.MatchError(input)
  }
}

显然，这是非常未被优化的。更糟糕的是，有一些函数调用被多次完成，这在原来没有发生。不幸的是，要解决这个问题，需要对代码进行一些结构性更改。

这里还有一些句法糖。有一个匿名函数被传递给分区，并且有用于调用函数的语法糖。重写这些产生以下内容：

def qsort: List[Int] => List[Int] = new Function1[List[Int],List[Int]] {
  def apply(input: List[Int]): List[Int] = if (input == Nil) {
    Nil
  } else if (input.isInstanceOf[::[_]] &&
             scala.collection.immutable.::.unapply(input.asInstanceOf[::[Int]]) != None) {
    val unapplyResult0 = scala.collection.immutable.::.unapply(input.asInstanceOf[::[Int]]).get
    val pivot = unapplyResult0._1
    val tail = unapplyResult0._2
    val func0 = new Function1[Int,Boolean] {
      def apply(input: Int): Boolean = input < pivot
    }
    val tmp0 = tail.partition(func0)
    if (Tuple2.unapply(tmp0) == None)
      throw new scala.MatchError(tmp0)
    val unapplyResult1 = Tuple2.unapply(tmp0).get
    val smaller = unapplyResult1._1
    val rest = unapplyResult1._2
    qsort.apply(smaller) ::: pivot :: qsort.apply(rest) 
  } else {
    throw new scala.MatchError(input)
  }
}

一次，关于每个句法糖的广泛解释及其工作原理是由别人做的。 :-)我希望这补充了他们的答案。正如最后一个注释，以下两行是等效的：

qsort(smaller) ::: pivot :: qsort(rest) 
    qsort(rest).::(pivot).:::(qsort(smaller))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!