维基百科快速排序示例中使用的Scala语法的逐步说明

Question

我试图了解维基百科的Scala quicksort示例.如何将样品逐步拆解,所涉及的所有语法糖是什么意思？

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

尽管我可以在这个阶段收集,但qsort是一个不带参数的函数,它返回一个新的Function1 [List [Int],List [Int]],它通过使用模式匹配,列表操作和递归调用来实现快速排序.但我无法弄清楚枢轴的来源,以及在这种情况下模式匹配语法的确切作用.

更新:

谢谢大家的精彩解释!

我只想分享另一个快速实现的例子,我在Scala by Example中发现了Martin Odersky.虽然基于数组而不是列表,而且在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 <)))
    }
}

Answer 1

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

让我们分开几点.

命名

运算符(例如*or +)是Scala中方法和类名的有效候选者(因此你可以有一个被调用的类::(或者一个被调用的方法::- 实际上都存在).Scala似乎有运算符重载但实际上它不是:它只是你可以声明一个具有相同名称的方法.

模式匹配

target match {
  case p1 => 
  case p2 => 
}

其中p1和p2是模式.有许多有效的模式(您可以匹配字符串,类型,特定实例等).您还可以匹配称为提取器的东西.一个提取基本上提取你的论点在比赛,所以的情况下:

target match {
  case MyExtractor(arg1, arg2, arg3) => //I can now use arg1, arg2 etc
}

在scala中,如果存在一个提取器(其中一个case类是一个例子)X,则该模式X(a, b)等效于a X b.case类::有一个带有2个参数的构造函数,并将它们组合在一起得到:

case x :: xs =>
case ::(x, xs) =>

是等价的.本场比赛说:"如果我的列表是一个实例::提取值head到x和tail成xs".模式匹配也用于变量声明.例如,if p是一个模式,这是有效的:

val p = expression

这就是我们可以声明变量的原因:

val x :: xs = List(1, 2, 3)
val (a, b) = xs.partition(_ % 2 == 0 ) //returns a Tuple2 which is a pattern (t1, t2)

匿名函数

其次,我们有一个"文字"功能.tail是一个实例,List它有一个被调用的方法partition,它接受一个谓词并返回两个列表; 其中一个条目满足谓词,其中一个条目没有.

val pred = (el: Int) => e < 2

声明一个函数谓词,如果 int值小于2 ,则取一个Int和返回true .有一个写内联函数的简写

tail.partition(_ < pivot) // _ is a placeholder for the parameter
tail.partition( (e: Int) => e < pivot )

这两个表达意味着同样的事情.

清单

A List是一个密封的抽象类,只有两个实现Nil(空列表)和::(也称为cons),它是一个由头和尾(也是一个列表)组成的非空列表.您现在可以看到模式匹配与列表是否为空匹配.a List可以通过将其提供给其他列表来创建:

val l = 1 :: 2 :: Nil
val m = List(1, 2, 3) ::: List(4, 5, 6)

上面的行只是方法调用(::是scala中的有效方法名称).这些和普通方法调用之间的唯一区别是,如果方法以冒号结尾:并且使用空格调用,则目标和参数的顺序相反:

a :: b === b.::(a)

功能类型

val f: A => B 

前一行将引用类型f化为一个函数,它接受A并返回一个B,所以我可以这样做:

val a = new A
val b: B = f(a)

因此,您可以看到def qsort: List[Int] => List[Int]声明了一个方法,该方法qsort返回一个带有a 并返回a 的函数.所以我显然可以做到:List[Int]List[Int]

val l = List(2, 4, 1)
val m = qsort.apply(l) //apply is to Function what run is to Runnable
val n = qsort(l) //syntactic sugar - you don't have to define apply explicitly!

递归

当方法调用是尾递归时,Scala会将其优化为迭代器模式.我的原始答案中有一个msitake,因为qsort上面不是尾递归的(尾调用是cons运算符)

Answer 2

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 (smaller, rest)也是模式匹配,所以让我们分解它:

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))