Функциональные структуры данных и сопоставление с образцом в Scala

Парадигма функционального программирования — это способ, которым мы пишем наш код без какого-либо изменяемого состояния. Таким образом, возникает вопрос, как мы определяем структуры данных и как их использовать. Здесь мы рассмотрим, что такое функциональная структура данных, и как мы будем их определять и использовать, а также рассмотрим в связанные понятия сопоставление с образцом и функции высшего порядка.

Определение функциональных структур данных

Функциональная структура данных — это то, что работает с чистыми функциями, что означает, что 1 + 2 дает 3, оставляя 1 и 2 без изменений, два списка a и b при их конкатенации даст (a++b) даст совершенно другой список, оставив a и b неизмененными, не связано ли это с копированием большого количества данных, давайте проверим, взяв связанный список как пример.

//List type parameterised with type A
sealed trait List[+A]
//A list constructor representing an empty list
case object Nil extends List[Nothing]
//A list type representing an non empty list
case class Cons[+A](head:A,tail:List[A]) extends List[A]

Теперь давайте посмотрим на реализацию связанного списка в Scala, мы создали трейт, трейт в Scala похож на интерфейс, который может дополнительно содержать реализацию метода. Запечатанное ключевое слово указывает, что реализация трейта должна быть в самом файле. После этого мы создали два конструктора для списка, объект Nil которого указывает на пустой список, а Cons показывает конструктор для непустого списка.

Обратите внимание, что мы использовали общий параметр типа A для типа списка. Это указывает на то, что наш список может иметь тип Int, Double, String и т. д.

[+A], используемый в списке, называется ковариацией в Scala, то есть List[dog] является подтипом List[Animal], предполагая, что собака является подтипом животного. Здесь мы расширяем Nil до List[Nothing], который подходит для всех наших случаев, следовательно, Nothing является подтипом всех типов, поэтому он будет соответствовать нашим потребностям, поэтому Nil может быть пустым списком String, Double, Int и т. д.

Теперь такие операции, как сумма и произведение, определенные в списке, будут выглядеть следующим образом.

/*
  * Function to calculate sum of elements in a list*/
  def sum(lis:List[Int]):Int=lis match {
    case Nil => 0
    case Cons(x,xs)=>x+sum(xs)
  }
  /*
  * Function to calculate product of elements in a list*/
  def prod(lis: List[Int]):Int=lis match {
    case Nil=>1
    case Cons(0,_)=>0
    case Cons(x,xs)=>x*prod(xs)
  }

Чтобы найти сумму элементов связанного списка, проверяются два случая, мы можем посмотреть больше на эту операцию сопоставления позже, здесь мы сравниваем список, если список является пустым списком, то сумма будет равна нулю, иначе мы вычисляем сумма главы списка и оставшейся части.

Точно так же для вычисления продукта, если список пуст, верните продукт как 1, если достигнут конец списка, если какой-либо элемент равен 0, тогда будет возвращен 0, другой случай дается для рекурсивного вычисления продукта.

object List {
 def main(args: Array[String]): Unit = {
   val x:List[Int]=Cons(1,Cons(2,Nil))
   println(sum(x))
   //sum is 3 
   println(prod(x))
   //product is 2
}

Сопоставление с образцом в Scala

Теперь давайте подробнее рассмотрим часть сопоставления шаблонов, которая немного похожа на выражение switch case. Что мы здесь делаем, так это то, что мы сопоставляем список типа int с ключевым словом match.

соответствует

Различные случаи для этого совпадения указаны в фигурных скобках.

{case ex1=> do_something
 case ex2=> do_something
}

Теперь давайте возьмем в качестве примера добавление нашего списка и проверим, как работает сопоставление с образцом. Мы проверяем наши списки по определенным случаям, если наш список является пустым списком, сумма будет равна нулю, что будет соответствовать первому случаю. Следующее условие будет следующим.

case Cons(x,xs)=>x+sum(xs)

Это условие представляет собой непустой список, для непустого списка сумма вычисляется рекурсивно, то есть сумма будет суммой его заголовка, который в данном случае представляет собой целое число, рекурсивно добавляемое к функции суммы, пока не будет достигнуто условие остановки, что является концом списка. При достижении условия остановки будет возвращен ноль, и все рекурсивные функции будут разрешены, и будет возвращена сумма.

Теперь давайте рассмотрим несколько примеров сопоставления с образцом.

val k=Array(1,2,3)
  Array(1,Nil) match {
    case _ => println(23)
  }
  //prints 23    
  Cons(1,Cons(2,Nil)) match {
    case Cons(h,_)=>println(h)
  }
  //1
  Cons(1,Cons(2,Nil)) match {
    case Cons(_,h)=>println(h)
  }
  //Cons(2,Nil)    
}

первый случай напечатает 23, потому что мы использовали _, а _ используется для игнорирования результата, что означает, что он ничего не будет проверять, он просто выполнит случай.
Второй случай будет соответствовать непустому списку и будет печатать заголовок списка. В этом случае будет 1.
Третье условие напечатает часть списка, исключая его заголовок.

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

Когда структура данных станет неизменяемой, встанет вопрос, как добавить в нее элемент или как из нее удалить. если мы добавляем новый элемент в списокxs , это приведет к созданию нового списка Но на самом деле нам не нужно копировать все элементы в список, мы можем просто повторно использовать список xs . Этот процесс называется обмен данными.

Функции высшего порядка и передача анонимных функций

В функциональном программировании мы можем рассматривать функции как значения, поэтому эти функции можно хранить в структурах данных, передавать в функции и т. д.

def findFirst[T](as: List[T], f: T => Boolean): Int = {
    @annotation.tailrec
    def loop(n: Int): Int =
      if (n >= as.length) -1
      else if (f(as(n))) n
      else loop(n + 1)

    loop(0)
  }

Это функция, используемая для поиска первого вхождения элемента в массиве, эта функция принимает другую функцию f в качестве параметра, которая используется для проверки того, что элемент массива является элементом, который мы ищем, если это правда, функция вернет свою позицию. иначе он вернет -1.

val arr2 = List("apple", "orange", "grapes")
findFirst(arr2, (x: String) => x == "grapes"))

Это пример передачи анонимной функции в другую функцию, эта функция будет принимать значение типа string и проверять, является ли строка «виноградом», если она истинна. И функция вернет позицию элемента.

Функциональные структуры данных и сопоставление с образцом в Scala

Вопросы по теме