Пошаговое объяснение синтаксиса Scala, используемого в примере быстрой сортировки в Википедии

Question

Я пытаюсь понять пример быстрой сортировки Scala из Википедии. Как образец может быть разобран шаг за шагом и что означает весь синтаксический сахар?

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 Мартина Одерского. Хотя он основан на массивах, а не на списках, а не на понты в терминах различных функций 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) 
}

Давайте перепишем это. Сначала замените литерал функции на экземпляр 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))

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

давайте выберем несколько кусочков.

Именование

Операторы (такие как * или же +) являются действительными кандидатами на имена методов и классов в 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, Класс дела :: имеет конструктор, принимающий 2 аргумента и собирающий это вместе, мы получаем это:

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

Эквивалентны Это совпадение говорит "если мой список является экземпляром :: извлечь значение head в x а также tail в xs ". сопоставление с образцом также используется в объявлении переменной. Например, если 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 и возвращает истину, если значение int меньше 2. Существует сокращение для написания встроенных функций

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

Эти два выражения означают одно и то же.

Списки

List является запечатанным абстрактным классом только с двумя реализациями, Nil (пустой список) и :: (также называемый cons), который является непустым списком, состоящим из головы и хвоста (который также является списком). Теперь вы можете видеть, что сопоставление с образцом совпадает с тем, является ли список пустым или нет. 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 который возвращает функцию, принимающую 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 оптимизирует его в шаблон итератора. В моем первоначальном ответе была ошибка, потому что qsort выше не является хвостовой рекурсией (хвостовой вызов является оператором cons)

Answer 3

Сводка в этом примере сопоставления с образцом является первым элементом списка:

scala> List(1,2,3) match {
     |     case x :: xs => println(x)
     |     case _ => println("empty")
     | }
1

Сопоставление с образцом основано на экстракторах, а минусы не являются частью языка. Он использует инфиксный синтаксис. Вы также можете написать

scala> List(1,2,3) match {
     |     case ::(x,xs) => println(x)
     |     case _ => println("empty")
     | }
1

также. Таким образом, есть тип::, который выглядит как оператор cons. Этот тип определяет, как он извлекается:

final case class ::[B](private var hd: B, private[scala] var tl: List[B]){ ... }

Это класс case, поэтому экстрактор будет сгенерирован компилятором Scala. Как в этом примере класса А.

case class A(x : Int, y : Int)

A(1,2) match { case x A y => printf("%s %s", x, y)}

-> 1 2

На основании этого поддерживается соответствие шаблонов для Lists, Regexp и XML.