Scala в прикладах

Тут ведеться переклад книги Martin’а Odersky Scala by examples, яка описує основні прийоми програмування мовою Scala^↑. Приєднуйтеся!

Вступ

Scala витончено поєднує об'єктно-орієнтоване і функційне програмування. Ця мова спроектована для вираження звичних патернів програмування коротко, красиво і безпечно за типами. Scala вводить кілька інноваційних мовних конструктів. наприклад:

• Абстрактні типи і домішки об'єднують концепти об'єктних і модульних систем;
• Зіставлення зі зразком на ієрархії класів об'єднує функційний і об'єктно-орієнтований доступ до даних (це дуже спрощує обробку XML-дерев);
• Гнучкі синтаксис і система типів дозволяють конструювати просунуті бібліотеки і нові доменно-специфічні мови.

У той же час, мова Scala сумісна з Java. Можна використовувати Java-бібліотеки і фреймворки без пов'язуючого коду і додаткових декларацій.

Ця книга представляє Scala неформально, на прикладах.

Розділи 2 і 3 звертають увагу на деякі можливості, через які Scala особливо цікава. Наступні розділи представляють конструкти мови більш детально, починаючи з простих виразів і функцій, через об'єкти і класи, списки і потоки, мінливим станам, зіставлення зі зразком, до більш складних прикладів, які ілюструють цікаві прийоми програмування. Цей неформальний виклад має бути доповнений документом Scala Language Reference Manual, який специфікує Scala точніше і детальніше.

Зауваження. Ми у величезному боргу перед чудовою книгою Абельсона і Сассмана, «Структура та інтерпретація комп'ютерних програм». Багато прикладів і вправи звідти також наведені тут. Звичайно, робоча мова в кожному випадку була змінений зі Scheme на Scala. Крім того, в прикладах використані об'єктно-орієнтовані конструкти Scala, де це доречно.

Перший приклад

Як перший приклад розглянемо швидке сортування.

def sort(xs: Array[Int]) {
  def swap(i: Int, j: Int) {
    val t = xs(i);
    xs(i) = xs(j);
    xs(j) = t
  }
  def sort1(l: Int, r: Int) {
    val pivot = xs((l + r) / 2)
    var i = l;
    var j = r
    while (i <= j) {
      while (xs(i) < pivot) i += 1
      while (xs(j) > pivot) j -= 1
      if (i <= j) {
        swap(i, j)
        i += 1
        j -= 1
      }
    }
    if (l < j) sort1(l, j)
    if (j < r) sort1(i, r)
  }
  sort1(0, xs.length - 1)
}

Код дуже схожий на програму на Java або Cі. Ми використовуємо ті ж оператори і схожі керівні конструкції. Є також трохи синтаксичних відмінностей. Зокрема,

• Визначення завжди починаються з зарезервованого слова. Визначення функцій починається з def, визначення змінних починається з var, а визначення значень (тобто змінних тільки для читання) - з val.
• Тип ідентифікатора оголошується через двокрапку після ідентифікатора. Задання типу часто можна пропускати, оскільки компілятор здатний виводити його з контексту.
• Типи масивів записуються як Array[T] замість T [], а вибірка з масиву як a(i) замість a[i].
• Функції можуть бути вкладені в інші функції. Вкладені функції мають доступ до параметрів і локальних змінних зовнішніх функцій. Наприклад, масив xs є видимим для функцій swap і sort1, а значить, його не потрібно передавати як параметр.

Поки що Scala виглядає досить простою мовою з деякими синтаксичними дивацтвами. Насправді, на Scala можна писати програми в звичайному імперативному або об'єктно-орієнтованому стилі. Це важливо, тому що полегшує об'єднання Scala-компонент із кодом, написаним на таких популярних мовах, як Java, C# або Visual Basic.

Але можна писати програми, які будуть виглядати зовсім інакше. Ось знову швидке сортування, на цей раз написане в функційному стилі.

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

Функційна програма коротко і точно передає сутність алгоритму швидкого сортування:

• Якщо масив порожній або складається з одного елемента, то він вже відсортований.
• Якщо масив не пустий, вибираємо середній елемент як роздільник.
• Розбиваємо масив на три підмасива, що містять, відповідно, елементи, менші за роздільник, елементи, рівні роздільнику, і елементи, більші за нього.
• Сортуємо підмасиви за допомогою рекурсивного виклику функції sort. (Це не зовсім те, що робить імперативна версія. Там масив розбивається на масив елементів, менших за роздільник, і масив елементів, більший або рівний йому.)
• Після склеювання всіх підмасивів повертаємо результат.

Обидві реалізації, і імперативна, і функційна, мають однакову асимптотичну складність - O(N log(N)) у середньому і O(N²) у гіршому випадку. Але якщо імперативна версія безпосередньо оперує елементами масиву, використовуючи пряму адресацію, то функційна при кожному рекурсивному виклику повертає новий відсортований масив, залишаючи без зміни масив, переданий як аргумент. Отже, функційна реалізація вимагає більше пам'яті для виконання.

Функційна реалізація створює враження, що Scala це спеціалізована мова для функційних операцій на масивах. Насправді всі операції, що використовувалися в прикладі, це просто бібліотечні методи класу послідовності Seq[T] зі стандартної бібліотеки Scala, яка сама реалізована на Scala. Оскільки масиви - це екземпляри класу Seq, вс його методи доступні їм.

Зокрема, метод filter, який приймає як аргумент предикатну функція. Предикатна функція має переводити елементи масиву в бульові значення. Результат виконання filter - масив, що складається з тих елементів вихідного масиву, які задовольняють предикату, тобто на яких предикатна функція повертає істину (true). Отже метод filter класу Array[T] має сигнатуру

def filter(p: T => Boolean): Array[T]

Тут T => Boolean — запис типу функції, яка приймає аргумент типу T і повертає бульове значення. Функції, подібні filter, тобто які приймають іншу функцію як аргумент або повертають функцію как результат, називаються функціями вищого порядку.

Див. також

• Scala