Scala в примерах: различия между версиями

10 834 байта добавлено ,  8 лет назад
 
== Определение класса List I: методы первого порядка ==
 
Списки не встроены в Scala, они определены при помощи абстрактного класса <tt>List</tt>, у которого есть два подкласса для <tt>::</tt> и <tt>Nil</tt>. Далее мы подробно рассмотрим класс <tt>List</tt>.
 
<font size=3><syntaxhighlight lang=Scala>
package scala
abstract class List[+A] {
</syntaxhighlight></font>
 
<tt>List</tt> — абстрактный класс, так что нельзя определять элементы, вызывая пустой конструктор <tt>List</tt> (например, при помощи new <tt>List</tt>). У класса есть типовой параметр <tt>A</tt>. Класс ковариантен по этому параметру, то есть, <tt>List[S] <: List[T]</tt> для всех типов <tt>S</tt> и <tt>T</tt>, таких что <tt>S <: T</tt>. Класс расположен в пакете scala. Этот пакет содержит наиболее важные стандартные классы Scala. <tt>List</tt> определяет несколько методов, объясненных ниже.
 
 
<font size=3>'''Разложение списка'''</font>
 
Во-первых, есть три базовых метода: <tt>isEmpty</tt>, <tt>head</tt>, <tt>tail</tt>. Их реализации в терминах сопоставления с образцом довольно просты:
 
<font size=3><syntaxhighlight lang=Scala>
def isEmpty: Boolean = this match {
case Nil => true
case x :: xs => false
}
def head: A = this match {
case Nil => error("Nil.head")
case x :: xs => x
}
def tail: List[A] = this match {
case Nil => error("Nil.tail")
case x :: xs => xs
}
</syntaxhighlight></font>
 
Следующая функция считает длину списка:
 
<font size=3><syntaxhighlight lang=Scala>
def length: Int = this match {
case Nil => 0
case x :: xs => 1 + xs.length
}
</syntaxhighlight></font>
 
'''Упражнение 9.2.1''' Напишите хвостово-рекурсивную версию <tt>length</tt>.
 
Следующие две функции дуальны <tt>head</tt> и <tt>tail</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
def last: A
def init: List[A]
</syntaxhighlight></font>
 
<tt>xs.last</tt> возвращает последний элемент списка <tt>xs</tt>, а <tt>xs.init</tt> — все элементы <tt>xs</tt>, кроме последнего. Обе эти функции проходят весь список, и поэтому менее эффективны, чем их аналоги <tt>head</tt> и <tt>tail</tt>. Вот реализация <tt>last</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
def last: A = this match {
case Nil => error("Nil.last")
case x :: Nil => x
case x :: xs => xs.last
}
</syntaxhighlight></font>
 
Реализация <tt>init</tt> аналогична.
 
Следующие три функции возвращают префикс списка, его суффикс или и то, и другое.
 
<font size=3><syntaxhighlight lang=Scala>
def take(n: Int): List[A] =
if (n == 0 || isEmpty) Nil else head :: tail.take(n-1)
 
def drop(n: Int): List[A] =
if (n == 0 || isEmpty) this else tail.drop(n-1)
 
def split(n: Int): (List[A], List[A]) = (take(n), drop(n))
</syntaxhighlight></font>
 
<tt>(xs take n)</tt> возвращает первые <tt>n</tt> элементов списка <tt>xs</tt> или весь список, если его длина меньше <tt>n</tt>. <tt>(xs drop n)</tt> возвращает все элементы <tt>xs</tt>, кроме первых <tt>n</tt>. Наконец, <tt>(xs split n)</tt> возвращает пару, состоящую из списков результатов <tt>xs take n</tt> и <tt>xs drop n</tt>.
 
Следующая функция возвращает элемент на данной позиции в списке (аналогично взятию элемента из массива). Индексы начинаются с <tt>0</tt>.
 
<font size=3><syntaxhighlight lang=Scala>
def apply(n: Int): A = drop(n).head
</syntaxhighlight></font>
 
У метода <tt>apply</tt> в Scala специальное значение. Объект с этим методом может быть применен к аргументам, как если бы он был функцией. Например, чтобы выбрать третий элемент списка <tt>xs</tt>, можно написать или <tt>xs.apply(3)</tt>, или <tt>xs(3)</tt> — второй вариант раскрывается в первый.
 
С <tt>take</tt> и <tt>drop</tt> мы можем создавать списки, состоящие их последовательных элементов данного списка. Чтобы создать список из элементов ''xs<sub>m</sub>, …, xs<sub>n-1</sub>'' списка <tt>xs</tt>, используйте
 
<font size=3><syntaxhighlight lang=Scala>
xs.drop(m).take(n - m)
</syntaxhighlight></font>
 
 
<font size=3>'''Сшивание списков'''</font>
 
Следующая функция делает из двух списков список пар. Если даны два списка, <tt>xs = List(x<sub>1</sub>, …, x<sub>n</sub>)</tt> и <tt>ys = List(y<sub>1</sub>, …, y<sub>n</sub>)</tt>, <tt>xs zip ys</tt> создает список <tt>List((x<sub>1</sub>, y<sub>1</sub>), …, (x<sub>n</sub>, y<sub>n</sub>))</tt>. Если у двух списков были разные длины, длинный список обрежется. Вот определение <tt>zip</tt>, обратите внимание, что это полиморфный метод:
 
<font size=3><syntaxhighlight lang=Scala>
def zip[B](that: List[B]): List[(a,b)] =
if (this.isEmpty || that.isEmpty) Nil
else (this.head, that.head) :: (this.tail zip that.tail)
</syntaxhighlight></font>
 
 
<font size=3>'''Продолжение списка'''</font>
 
Как и любой инфиксный оператор, <tt>::</tt> также реализован как метод объекта. В этом случае объект — это удлиняемый список. Это возможно, потому что операторы, заканчивающиеся на символ ‘<tt>:</tt>’, обрабатываются в Scala специальным образом. Все такие операторы рассматриваются как методы своих правых операндов. Например, <tt>x :: y = y.::(x)</tt>, тогда как <tt>x + y = x.+(y)</tt>.
 
Заметьте, однако, что операнды бинарной операции в каждом случае вычисляются слева направо. Так что, если <tt>D</tt> и <tt>E</tt> — выражение с возможными побочными эффектами, <tt>D :: E</tt> транслируется в <tt>{'''val''' x = D; E.::(x)}</tt>, чтобы сохранить порядок вычисления операндов слева направо.
 
Другое отличие между операторами, заканчивающимися на ‘<tt>:</tt>’, и другими операторами относится к их ассоциативности. Операторы, заканчивающиеся на ‘<tt>:</tt>’, правоассоциативны, тогда как остальные — левоассоциативны. То есть, <tt>x :: y :: z = x :: (y :: z)</tt>, тогда как <tt>x + y + z = (x + y) + z</tt>.
 
Определение <tt>::</tt> как метода класса <tt>List</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
def ::[B >: A](x: B): List[B] = new scala.::(x, this)
</syntaxhighlight></font>
 
Заметьте, что <tt>::</tt> определен для всех элементов x типа B и списков типа <tt>List[A]</tt>, таких что тип <tt>B</tt> — супертип типа <tt>A</tt>. Результатом в этом случае будет список элементов типа <tt>B</tt>. Это выражается типовым параметром <tt>B</tt> с нижней границей <tt>A</tt> в сигнатуре <tt>::</tt>.
 
 
<font size=3>'''Конкатенация списков'''</font>
 
Операция конкатенации похожа на <tt>::</tt> и записывается <tt>:::</tt>. Результат выполнения <tt>(xs ::: ys)</tt> — список, состоящий их всех элементов <tt>xs</tt>, за которыми следуют все элементы <tt>ys</tt>. Поскольку оператор заканчивается на двоеточие, <tt>:::</tt> правоассоциативен и рассматривается как метод своего правого операнда. Следовательно,
 
<font size=3><syntaxhighlight lang=Scala>
xs ::: ys ::: zs = xs ::: (ys ::: zs)
= zs.:::(ys).:::(xs)
</syntaxhighlight></font>
 
Ниже приведена реализация метода <tt>:::</tt>.
 
<font size=3><syntaxhighlight lang=Scala>
def :::[B >: A](prefix: List[B]): List[B] = prefix match {
case Nil => this
case p :: ps => this.:::(ps).::(p)
}
</syntaxhighlight></font>
 
 
<font size=3>'''Обращение списка'''</font>
 
Еще одна полезная операция это обращение списка. В <tt>List</tt> для этого есть метод <tt>reverse</tt>. Попробуем его реализовать:
 
<font size=3><syntaxhighlight lang=Scala>
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case x :: xs => reverse(xs) ::: List(x)
}
</syntaxhighlight></font>
 
Эта реализация хороша тем, что она проста, но она не очень эффективна. Действительно, конкатенация выполняется для каждого элемента списка. Конкатенация списка занимает время, пропорциональное длине первого операнда. Следовательно, сложность <tt>reverse(xs)</tt>: ''n + (n - 1) + … + 1 = n (n + 1) / 2'', где ''n'' — длина <tt>xs</tt>. Может ли реализовать reverse более эффективно? Позже мы увидим, что есть другая реализация, которая имеет линейную сложность.
 
== Пример: сортировка слиянием ==
== Определение класса List II: методы высшего порядка ==
83

правки