Scala в примерах: различия между версиями
Содержимое удалено Содержимое добавлено
Annayudi (обсуждение | вклад) →Неявные(имплицитные) параметры и преобразования: — исправление ошибки в коде, которая есть и в оригинальном тексте |
→Списки: — начат перевод главы |
||
Строка 2129:
= Списки =
Списки — важные структуры данных во многих программах на Scala. Список, состоящий из элементов ''x<sub>1</sub>, …, x<sub>n</sub>'', записывается так: <tt>List(x<sub>1</sub>, …, x<sub>n</sub>)</tt>. Вот примеры:
<font size=3><syntaxhighlight lang=Scala>
val fruit = List("apples", "oranges", "pears")
val nums = List(1, 2, 3, 4)
val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty = List()
</syntaxhighlight></font>
Списки похожи на массивы в таких языках, как C или Java, но есть три важных отличия. Во-первых, списки неизменяемы. То есть, элементы списка нельзя менять при помощи присваиваний. Во-вторых, у списков рекурсивная структура, тогда как массивы плоские. В третьих, списки поддерживают гораздо больше операций, чем обычные массивы.
== Использование списков ==
=== Тип List ===
Как и массивы, списки ''гомогенны''. Это значит, все элементы списка — одного типа. Тип списка с элементами типа <tt>T</tt> записывается как <tt>List[T]</tt> (похоже на <tt>T[]</tt> в Java).
<font size=3><syntaxhighlight lang=Scala>
val fruit: List[String] = List("apples", "oranges", "pears")
val nums : List[Int] = List(1, 2, 3, 4)
val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty: List[Int] = List()
</syntaxhighlight></font>
=== Конструкторы списков ===
Все списки строятся при помощи двух более фундаментальных конструкторов, <tt>Nil</tt> и <tt>::</tt> (произвносится "cons"). <tt>Nil</tt> выражает пустой список. Инфиксный оператор <tt>::</tt> выражает продление списка. То есть, <tt>x :: xs</tt> выражает список с первым элементом <tt>x</tt>, за которым идут элементы списка <tt>xs</tt>. Значения списков, приведенные выже, могут быть определены так (на самом деле, их предыдущие определения это синтаксический сахар для определений ниже):
<font size=3><syntaxhighlight lang=Scala>
val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums = 1 :: (2 :: (3 :: (4 :: Nil)))
val diag3 = (1 :: (0 :: (0 :: Nil))) ::
(0 :: (1 :: (0 :: Nil))) ::
(0 :: (0 :: (1 :: Nil))) :: Nil
val empty = Nil
</syntaxhighlight></font>
Оператор ‘<tt>::</tt>’ правоассоциативен: <tt>A :: B :: C</tt> интерпретируется как <tt>A :: (B :: C)</tt>. То есть, мы можем опустить скобки в определениях. Например, мы можем записать более коротко
<font size=3><syntaxhighlight lang=Scala>
val nums = 1 :: 2 :: 3 :: 4 :: Nil
</syntaxhighlight></font>
=== Базовые операции со списками ===
Все операции со списками можно выразить при помощи следующих трех конструкций:
* <tt>head</tt> — возвращает первый элемент списка;
* <tt>tail</tt> — возвращает список, состоящий из всех элементов за исключением первого;
* <tt>isEmpty</tt> — возвращает <tt>'''true'''</tt> тогда и только тогда, когда список пуст.
Эти операции определены как методы объектов-списков. Их можно вызвать, выбрав из списка, с которым мы работаем. Примеры:
<font size=3><syntaxhighlight lang=Scala>
empty.isEmpty = true
fruit.isEmpty = false
fruit.head = "apples"
fruit.tail.head = "oranges"
diag3.head = List(1, 0, 0)
</syntaxhighlight></font>
Методы <tt>head</tt> и <tt>tail</tt> определены только для непустых списокв. Когда они выбраны из пустого списка, они выбрасывают исключение.
В качестве примера работы со списками рассмотрим сортировку элементов списка числе в возрастающем порядке. Простой способ сделать это — ''сортировка вставками'', которая работает так: чтобы отсортировать непустой список с первым элементом <tt>x</tt> и остальными элементами <tt>xs</tt>, отсортируем оставшийся список <tt>xs</tt> и вставим элемент <tt>x</tt> на правильную позицию в результат. Сортировка пустого списка дает пустой список. Запишем это на Scala:
<font size=3><syntaxhighlight lang=Scala>
def isort(xs: List[Int]): List[Int] =
if (xs.isEmpty) Nil
else insert(xs.head, isort(xs.tail))
</syntaxhighlight></font>
'''Упражнение 9.1.1''' Реализуйте недостающую функцию <tt>insert</tt>.
=== Образцы списков ===
На самом деле, оператор <tt>::</tt> определен как case-класс в стандартной библиотеке Scala. Возможно раскладывать списки при помощи сопоставления с образцом, используя образцы, составленные из конструкторов <tt>Nil</tt> и <tt>::</tt>. Например, <tt>isort</tt> можно написать так:
<font size=3><syntaxhighlight lang=Scala>
def isort(xs: List[Int]): List[Int] = xs match {
case List() => List()
case x :: xs1 => insert(x, isort(xs1))
}
</syntaxhighlight></font>
где
<font size=3><syntaxhighlight lang=Scala>
def insert(x: Int, xs: List[Int]): List[Int] = xs match {
case List() => List(x)
case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
}
</syntaxhighlight></font>
== Определение класса List I: методы первого порядка ==
== Пример: сортировка слиянием ==
| |||