Функциональная структура данных

Функциональная структура данных (functional data structures) работает с использованием только чистых функций. Напомним, что чистая функция не должна изменять данные или выполнять другие побочные эффекты. Следовательно, функциональные структуры данных по определению являются неизменяемыми.

Односвязный список

Одной из самых распространённых функциональных структур данных является односвязный список.

Односвязный список можно определить так:

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])

object List:
  def apply[A](as: A*): List[A] =
    if as.isEmpty then Nil
    else Cons(as.head, apply(as.tail*))

Перечисление List содержит два конструктора данных, которые представляют две возможные формы List. List может быть пустым, обозначаемым конструктором данных Nil, или непустым, обозначаемым конструктором данных Cons (сокращение от construction). Непустой список состоит из начального элемента head, за которым следует List (возможно, пустой) оставшихся элементов (tail):

List

Создать список можно следующим образом:

val ex1: List[Double] = Nil
// ex1: List[Double] = Nil
val ex2: List[Int] = Cons(1, Nil)
// ex2: List[Int] = Cons(head = 1, tail = Nil)
val ex3: List[String] = Cons("a", Cons("b", Nil))
// ex3: List[String] = Cons(head = "a", tail = Cons(head = "b", tail = Nil))
val ex4: List[String] = List.apply("a", "b")
// ex4: List[String] = Cons(head = "a", tail = Cons(head = "b", tail = Nil))

Операции над односвязным списком

Над этой функциональной структурой данных можно определить, например, следующие операции суммы и произведения, которые используют сопоставление с образцом:

def sum(ints: List[Int]): Int = ints match
  case Nil => 0
  case Cons(x, xs) => x + sum(xs)

def product(ds: List[Double]): Double = ds match
  case Nil => 1.0
  case Cons(0.0, _) => 0.0
  case Cons(x, xs) => x * product(xs)

Рекурсивные определения довольно часто встречаются при написании функций, работающими с рекурсивными типами данных, такими как List (который ссылается сам на себя в конструкторе данных Cons).

Совместное использование данных в функциональных структурах данных

Когда данные неизменяемы, как писать функции, которые, например, добавляют или удаляют элементы из списка? Когда добавляется элемент e в начало существующего списка, скажем xs, возвращается новый список, в данном случае Cons(e, xs). Поскольку списки неизменяемы, на самом деле не нужно копировать xs; можно просто использовать его повторно. Это называется обменом данными (data sharing). Совместное использование неизменяемых данных часто позволяет более эффективно реализовывать функции; всегда можно вернуть неизменяемые структуры данных, не беспокоясь о том, что последующий код что-то поправит. Нет необходимости делать копии, чтобы избежать модификации или повреждения.

Точно так же, чтобы удалить элемент из начала списка val mylist = Cons(x, xs), можно просто вернуть его "хвост" - xs. Никакого реального удаления не происходит. Первоначальный список mylist все еще доступен в целости и сохранности. Говорится, что функциональные структуры данных являются постоянными, что означает, что операции над ними никогда не меняют существующие ссылки.

Data sharing

Пример операции удаления:

def tail[A](l: List[A]): List[A] =
  l match
    case Nil         => sys.error("tail of empty list")
    case Cons(_, xs) => xs

В результате останутся две неизменяемые структуры данных: l и xs.

Деревья

Ещё одним примером функциональной структуры данных является двоичное дерево:

enum Tree[+A]:
  case Leaf(value: A)
  case Branch(left: Tree[A], right: Tree[A])

Tree

Ссылки: