NAUMEN Деньгин Роман

Введение в функциональное программирование

Деньгин Роман

Императивное программирование

  • в исходном коде программы записываются инструкции (команды);
  • инструкции должны выполняться последовательно;
  • данные, получаемые при выполнении предыдущих инструкций, могут читаться из памяти последующими инструкциями;
  • данные, полученные при выполнении инструкции, могут записываться в память.
Функция в программировании — фрагмент программного кода (подпрограмма), к которому можно обратиться из другого места программы. 
                        import scala.collection.mutable

                        def foo(items: mutable.ListBuffer[Int]) = for (i <- items.indices) {
                            items(i) = Math.abs(items(i))
                        }

                        val items = mutable.ListBuffer(-1, 2, -3, 5, -10)
                        foo(items)  // (1, 2, 3, 5, 10)


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

Основные концепции:

  • чистота функций;
  • иммутабельность данных;
  • ссылочная прозрачность;
  • код - композиция функций;
  • функция - объект первого класса;
  • функции высших порядков;
  • сопоставление образцом.

Чистые функции

Функция называется чистой, когда она детерминированна и не несёт в себе побочных эффектов.

Чистые функции

Детерминированность

Функция является детерминированной, если для одного и того же набора входных значений она возвращает одинаковый результат.

Чистые функции

Детерминированность

Детерминированная функция 
                        def isEven(n: Int): Boolean = n % 2 == 0
                        
                        isEven(2)   // true
                        isEven(2)   // true
                        isEven(2)   // true
Недетерминированная функция 
                        def getCurrentVideoViewers(url: String): Int = goToUrl(url).getCurrentViewers
                        
                        getCurrentVideoViewers("https://my-cool-video") // 100
                        getCurrentVideoViewers("https://my-cool-video") // 100500
                        getCurrentVideoViewers("https://my-cool-video") // 1000000000

Чистые функции

Побочные эффекты

IO-операции, модификация данных и т.д. 
                        def mySqr(x: Int) = {
                            println(s"user data $x)
                            x * x
                        }
                        
                        mySqr(5)    //25 и строка в консоли

Иммутабельность данных

Данные неизменны
Пример изменяемых данных 
                        var sumOfValues = 0

                        def findSum(list: Seq[Int]): Unit = 
                          for(item <- list) {
                            sumOfValues = sumOfValues + item
                          }
Как можно провести вычисления без изменения данных 
                        def findSumImmutable(list: Seq[Int], sumOfValues: Int = 0): Int = 
                          if(list.isEmpty) sumOfValue
                          else findSumImmutable(list.tail, sumOfValues + list.head)

Ссылочная прозрачность (Referential transparency)

Выражение называется ссылочно прозрачным, если его можно заменить соответствующим значением без изменения поведения программы. 
                        def values = Тяжелое вычисление, которое в результате дает Seq(1, 2)

                        findSumImmutable(values)    // 3
                        findSumImmutable(Seq(1, 2)) // 3
                        3

Функции - объекты первого класса

  • функции можно хранить в переменных/константах;
  • функции можно передавать в качестве агрументов;
  • функция может быть результатом вычисления.
                        object Math {
                          def sqr(n: Int): Int = n * n
                        }
                        
                        object ListFunctor {
                          def map[A, B](f: A => B): List[A] => List[B] = _.map(f)
                        }
    
                        val sqr: Int => Int = Math.sqr _
    
                        val sqrList: List[Int] => List[Int] = ListFunctor.map(sqr)
    
                        sqrList(List(2, 3, 4))  // List(4, 9, 16)

Функции - объекты первого класса

Любая функция - экземпляр класса FunctionN[...] 
                        abstract class Function1[A, B] {
                          def apply(a: A): B
                        }
  
                        (A => B) ~ Function1[A, B]

Лямбда-функции

- выражение, которое состоит исключительно из следующих составляющих:
  • переменные - включений имён "переменных" (f, x);
  • аппликации - применения терм друг к другу (f(x));
  • абстракции - реализация лямда-функций (λx.f(x)).
                        val product: (Int, Int) => Int = tuple => tuple._1 * tuple._2
                        val sqr: Int => Int = x => product (x, x)

Композиция функций

∀ f: A → B, g: B → C
∃ c: A → C = g ∘ f
Т.е. для f(a): b и g(b): c есть c(a) = g(f(a)) 
                        def decode: Array[Byte] => String
                        def parseString[T](parser: Parser[T]): String => T
                        
                        def parseBytes[T](parser: Parse[T]): Array[Byte] => T = 
                            decode andThen parseString(parser) // ~ bytes => parseString(parser)(decode(bytes))

Каррирование

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

Каррирование

                        def curriedLog(date: String)
                                      (level: Level)
                                      (msg: String): Unit = println(s"$date [${level}] $msg")

                        def logNow: Level => String => Unit = curriedLog(now)

                        def logErrorNow: String => Unit = logNow(Error)

                        def logInfoNow: String => Unit = logNow(Info)

                        logInfoNow("Hello")

Функции высших порядков

Функция высшего порядка - функция, которая принимает в качестве параметров(-а) или/и возвращает функцию. 
                        def map[A, B](f: A => B, list: List[A]): List[B]
                        
                        def compose[A, B, C](f: A => B, g: B => C): A => C = (x: A) => g(f(x))

Рекурсивные функции

Рекурсивные функции

Функция называется рекурсивной, если она вызывает сама себя. 
                        def factorial(n: Int): Int =
                            if (n == 1)
                                1
                            else
                                factorial(n - 1) * n

Хвостовая рекурсия

Хвостовая рекурсия - рекурсия, в которой рекурсивный вызов является последним.
Т.е. результат рекурсивного вызова - результат вычисления функции. 
                        def factorial(n: Int): Int =
                            if (n == 1)
                                1
                            else
                                factoral(n - 1) * n
                                
                        @tailrec
                        def factorial2(n: Int, res: Int = 1) =
                            if (n < 1)
                                res
                            else
                                factorial2(n - 1, res * n)

Сопоставление с образцом
(Pattern matching)

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

Возможность switch-case match-case
сопоставление с вычисляемым значением (литерал, выражение) + +
сопоставление с типом - +
"Распаковка" объектов - +
Завершения проверок после совпадения break +

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

Bound-pattern

                        def foo[A](a: A): Unit = a match {
                          case x => () // x is A
                        }

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

Type-pattern

                        def foo[A](a: A): Unit = a match {
                          case x: B => () // x is B if a is B
                          case _: C =>    // there are no new names and we know that a is C
                        }

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

Extractor-pattern

                        def foo[A](a: Option[A]): A = a match {
                          case Some(x) => x // x is A
                          case _ => A.default
                        }

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

@-pattern (pattern binder)

                        def foo[A](a: Option[A]): A = a match {
                          case some@Some(x) => x // x is A, some is Some[A]
                          case _ => A.default
                        }

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

Pattern guards

                        def foo[A](a: Option[A]): Int = a match {
                          case Some(x: Int) if x > 0 => x // x is positive Int
                          case _ => 1
                        }
                    
                        def tailMap[A, B](f: A => B)(list: List[A]): List[B] = {
                          @tailrec
                          def loop(l: List[A], buffer: List[B]): List[B] = if(l.isEmpty) {
                            buffer
                          } else {
                            val head = l.head
                            val tail = l.tail
                            loop(tail, buffer :+ f(head))
                          }
                          loop(list, List.empty)
                        }

                        def newTailMap[A, B](f: A => B)(list: List[A]): List[B] = {
                          @tailrec
                          def loop(l: List[A], buffer: List[B]): List[B] = l match {
                            case head :: tail => loop(tail, buffer :+ f(head)) // ::(head, tail)
                            case _            => buffer
                          }
                          loop(list, List.empty)
                        }

Algebraic data type

Algebraic data type

Комбинации типов:

  • сумма (A | B);
  • произведение (A & B).

Algebraic data type

Сумма:

type Option[T] = None | Some[T]
type List[T] = Nil | ::[T]
type Boolean = True | False
... 
                        sealed trait List[+T]
                        
                        final case class ::[+T](head: T, tail: List[T]) extends List[T]

                        case object Nil extends List[Nothing]
                    
                        sealed trait Boolean
                        
                        case object True extends Boolean

                        case object False extends Boolean

Algebraic data type

Произведение:

type StandAloneApp = Host & Port
type BasicAppEnvironment = Database & StandAloneApp
BasicAppEnvironment ≈ Database & (Host & Port)
BasicAppEnvironment ≈ Database & Host & Port
... 
                        case class Database(url: String, username: String, password: String)
                        case class StandAloneApp(socketConf: (Host, Port))

                        case class BasicAppEnvironment(appConf: StandAloneApp, db: Database)

Algebraic data type

И Pattern Matching

Сопоставление с образцом - один из способов извлечения данных из алгебраического типа.

Algebraic data type

И Pattern Matching

Для произведения типов Extractor-pattern 
                        def startApp(
                          hostAllowed: Host, 
                          listenPort: Port,
                          db: Database): Unit

                        def run(env: BasicAppEnvironment) = env match {
                          case BasicAppEnvironment(StandAloneApp((host, port)), db: Database) =>
                            startApp(host, port, db)
                        }

Algebraic data type

И Pattern Matching

Для суммы типов Type-pattern и/или Extractor-pattern 
                        def describeValue(opt: Option[_]): String = opt match {
                          case Some(value) => s"There is a \"${value.toString}\""
                          case None => "There is nothing"
                        }

                        def describe(opt: Option[_]): String = opt match {
                          case _: Some[_] => "There is something"
                          case _ => "There is nothing"
                        }

Что мы получаем:

  • можно (и нужно) отказаться от переменных;
  • можно тестировать по принципу черного ящика;
  • огромное число гарантий;
  • отказоустойчивость;
  • оптимизация на этапе компиляции/разработки;
  • продолжать можно долго...

Спасибо за внимание

Вопросы?..