Scala/Coursera/Структури даних

Списки

Приклад діагональної матриці утвореної списками:

val diag: List[List[Int]] = List(List(1, 0), List(0, 1))

:: - оператор побудови списку cons.

Операції що закінчуються на : - правоасоціативні. A :: B :: C = A :: (B :: C)

А ще вони розглядаються як виклик метода правого операнда, в той час як всі інші - лівого.

Списки можна розкладати шаблонами: Nil, p :: ps, List(p1, ..., pn)

Методи списку:

• xs.length - кількість елементів списку
• xs.last - останній елемент
• xs.init - список що містить всі, окрім останнього, елементи даного
• xs take n - повернути перших n елементів списку, або ввесь список якщо його довжина менша за n
• xs drop n - повернути всі елементи крім перших n.
• xs(n) або xs apply n - повернути n-тий елемент списку.
• xs ++ ys - конкатенація (список що містить спершу всі елементи xs, а потім ys)
• xs.reverse - перевернутий список
• xs.updated(n, x) - новий список, в якому n-тий елемент замінено на x
• xs indexOf x - позиція x в списку, або -1, якщо такого елемента не знайдено
• xs contains x - чи містить список елемент x?

Функції вищого порядку над списками:

• xs map f - отримати нову послідовність, застосуванням функції f до елементів даної.
• xs filter p - створити послідовність лише з тих елементів xs що задовольняють умові p
• xs filterNot p == xs filter (x => !p(x))
• xs partition p == (xs filter p, xs filterNot p)
• xs takeWhile p - найдовший префікс з усіх елементів що задовільняють умові p.
• xs dropWhile p - залишок відкидання від початку всіх елементів що задовільняють p.
• xs span p = (xs takeWhile p, xs dropWhile p)
• xs reduceLeft op == x1 op x2 op x3 ...
• (xs foldLeft z)(op) == z op x1 op x2 ...

Аналогічні функції foldRight та reduceRight - правоасоціативні.

Ще операції над Seq:

• xs exists p - true, якщо в xs існує таке x, що p(x)
• xs forall p - true, якщо $p(x)\forall x\in xs$
• xs zip ys - список пар утворених з елементів обох списків, довжина якого дорівнює довжині коротшого списку.
• xs.unzip - повернути пару списків, якщо xs - список пар.
• xss.flatten - перетворити колекцію колекцій на колекцію утвореною конкатенацією всіх колекцій. Тобто список List(List(1, 2), List(3)) на List(1, 2, 3)
• xs.flatMap f - те саме що й (xs map f).flatten. Тобто, якщо f - повертає колекцію, то flatMap - конкатенацію всіх колекцій утворених застосуванням f до елементів xs.
• xs.sum - сума всіх елементів xs.
• xs.product - добуток всіх елементів xs.
• xs.max - мінімальний елемент послідовності.
• xs.min - максимальний елемент.
• xs.mkString s - утворити рядок x1 ++ s ++ x2 ++ s ++ ... ++ s ++ xN
• xs.distinct - послідовність різних елементів.

Пари та кортежі

val pair = (x, y)

Тип кортежу - (p1, ... , pn) == scala.TupleN(e1, ... , eN)

Поля кортежу можна отримати через атрибути ._1, ._2, ...

Можна робити присвоєння val (a, b) = pair

Vector

Vector довжини до 32 елементів - це просто масив. Якщо більше - це масив вказівників на масиви. Загалом виходить дерево, в якому кожен вузол має до 32 піддерев. Глибина дерева - $log_{32}(N)$

Vector має всі операції що й List, окрім cons. Там аналог цієї функції виглядає так:

x +: xs - додати елемент зліва xs :+ x - додати елемент справа

Варто зауважити що двокрапка завжди показує на вектор.

Структури даних в Scala. Операції над Seq працюють з Array і String, але ці два типи отримані з Java, тому насправді не наслідувались від Sequence.

Приклади роботи з послідовностями

Скалярний добуток:

def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
  (xs zip ys).map(xy => xy._1 * xy._2).sum

або

  (xs zip ys).map{case (x, y) => x * y}.sum

Взагалі,

x => x match { case p1 => e1 ... }

еквівалентно

  { case p1 => e1 ... }

def isPrime(n: Int): Boolean =
  (2 until n) forall (d => n % d != 0)

Range

Задає послідовність рівномірно розподілених цілих чисел

val a:Range = 1 to 10 by 3 // 1, 4, 7, 10
val b:Range = 6 to 1 by -2 // 6, 4, 2
val c:Range = 1 until 10   // 1, 2, 3, 4

to - включно, until - не включно.

For-вирази

For-expressions це аналог list comprehension в Python чи Haskell.

Нехай маємо клас що позначає особу:

case class Person(name: String, age: Int)

Отримати імена всіх людей старших за 20 років можна так:

persons filter (p => p.age > 20) map (p => p.name)

а можна так:

for (p <- persons if p.age > 20) yield p.name

Загалом, for-вираз виглядає як for (s) yield e, де s - послідовність генераторів та фільтрів, а e - вираз, значення якого повертається кожної ітерації. Повинна починатись з генератора.

Генератор - це вираз форми p <- e, де e - вираз що повертає послідовність а p - шаблон що приймає по черзі значення елементів цієї послідовності.

Фільтр - це вираз виду if b, де b - булевий вираз.

Замість круглих дужок в for-виразі можна використовувати фігурні, і тоді послідовність генераторів та фільтрів можна розтягти на кілька рядків.

Наприклад:

for {
    i <- 1 until n
    j <- 1 until i
    if isPrime(i + j)
} yield (i, j)

Чи

def scalarProduct(xs, ys) =
  (for ((x, y) <- xs zip ys) yield x * y).sum

Вираз for перетворюється на послідовність викликів map, flatMap та withFilter, тому, щоб такі вирази могли працювати з вашим класом - треба щоб в них були описані ці методи.

Таке працює наприклад з XML чи базами даних і надає до них зручний інтерфейс без SQL чи XSLT. На цій основі побудовані наприклад такі фреймворки з'єднання з базою даних як ScalaQuery та Slick. Подібну ідею використовує Microsoft LINQ.

Set

Set - тип множини, тобто такий що містить невпорядкований набір різних елементів (не містить дублікатів).

val fruits = Set("apple", "banana")
val s = (1 to 5).toSet

Головна операція для множини - contains.

Map

Map поводиться одночасно як функція і як Iterable.

Приклад:

val roman: Map[String, Int] = Map("I" -> 1, "V" -> 5)
roman("I") // = 1

Якщо викликати roman для значення ключа якого нема - отримаємо java.util.NoSuchElementException.

Можна робити виклик roman get "A" отримаємо None для ключа що не існує, або Some(значення). None чи Some(v: Int) - це тип Option[Int]

def showCaptial(country: String) = 
  capitalOfCountry.get(country) match {
    case Some(capital) => capital
    case None => "дані відсутні"
  }

Об'єкт типу Map - це часткова функція (тобто не всюди визначена). Щоб отримати всюди визначену функцію, використовуємо:

capitalOfCountry withDefaultValue "unknown"

Цей вираз дає повну функцію, тобто таку яка на всіх значеннях для яких відсутні ключі в capitalOfCountry, буде повертати значення "unknown".

Щоб додати нову пару в Map, можна написати:

roman + ('X' -> 10)

Сортування

val fruits = List("cherry", "apple", "banana")

fruits.sortWith(_.length < _.length) // сортує за допомогою функції порівняння
fruits.sorted // сортує за допомогою функції (_ < _)

fruit groupBy (_.head) - перетворює колекцію на колекцію списків, в яких ключ - це результат виклику функції, а списки містять елементи виклик функції для яких дає такий результат.

Stream

Stream - це щось схоже на список, але tail в якого обчислюється лише тоді коли про нього спитають. Їх можна створити за допомогою константи Stream.empty та конструктора Stream.cons Або за допомогою фабрики Stream(1, 2, 3).

def streamRange(lo: Int, hi: Int): Stream[Int] =
  if(lo >= hi) Stream.empty
  else Stream.cons(lo, streamRange(lo + 1, hi))

Хоча простіше буде створити прямо з range:

(1 to 1000).toStream

x #:: xs == Stream.cons(x, xs)

Нескінченні потоки

Потік всіх цілих чисел більших за n:

def from(n: Int): Stream[Int] =
  n #:: from(n + 1)

Натуральні:

val nats = from(1)

Парні:

val even = nats map (_ * 2)

Решето Ератосфена:

def sieve(s: Stream[Int]): Stream[Int] = 
  s.head #:: sieve(s.tail filter (_ % s.head != 0))

val primes = sieve(from(2))
primes.take(100).toList

Ліниві обчислення

На відміну від обчислень "за іменем" (by name), ми обчислюємо результат лише раз. Але на відміну від обчислень "за значенням" (by value) обчислюється він лише тоді коли про нього запитають.

lazy val x = expr // ліниве
def x = expr // за іменем
val x = expr // за значенням