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

Яценко Иван

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

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

Функция в программировании — фрагмент программного кода (подпрограмма), к которому можно обратиться из другого места программы.

                        import scala.collection.mutable
                            
                        object Sort {
                          def bubble(input: mutable.ListBuffer[Int]): Unit = {
                            if(input.isEmpty) ()
                            else {
                              for(i <- input.indices) {
                                for(j <- input.indices.drop(i).reverse) {
                                  val a = input(i)
                                  val b = input(j)
                                  if(a > b) {
                                    val buffer = a
                                    input(i) = input(j)
                                    input(j) = buffer
                                  }
                                }
                              }
                            }
                          }
                        }
    
                        val arr = mutable.ListBuffer(3, 2, 6, 4, 6, 1)  // ListBuffer(3, 2, 6, 4, 6, 1)
    
                        Sort.bubble(arr)
      
                        arr  // ListBuffer(1, 2, 3, 4, 6, 6)

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

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

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

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

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

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

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

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

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

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

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

Недетерминированная функция

                        object Math {
                          var pi = 3.14d

                          def circleArea(radius: Double) = 
                            radius * radius * pi
                        }

                        Math.circleArea(10)  // 314.0
                        Math.pi = 3.1415926d
                        Math.circleArea(10)  // 314.15926

Детерминированная функция

                            object Math {
    
                              def circleArea(radius: Double, pi: Double) = 
                                radius * radius * pi
                            }
    
                            Math.circleArea(10, 3.14)  // 314.00

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

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

IO-операции, передача управления, модификация данных и т.д.

                        object Math {
                          private var pi = 3.14d

                          def setPI(newPi: Double) = 
                            pi = newPi

                          def getPI() = pi

                          def circleArea(radius: Double) = 
                            radius * radius * getPi()
                        }

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

Данные неизменны.

                        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)

Ссылочная прозрачность

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

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

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

Преобразование функции нескольких аргументов в функцию одного аргумента, которая возвращает функцию от следующего аргумента, которая возвращает функцию от...
curr: ((A × B) → (C)) → (A → (B → C))

                        //curr - операция каррирования

                        foo: (A, B, C) => D
                        curr(foo): A => ((B, C) => D)
                        curr(curr(foo)): A => (B => (C => D))

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

                        def log(time: DateTime, level: Level, msg: String): String

                        def curriedLog: DateTime => Level => String => String = 
                          time: DateTime => 
                            level: Level =>
                              msg: String => log(time, level, msg)

                        val fixedTimeLogger: Level => String => String = curriedLog(DateTime.now())

                        val fixedTimeErrorLogger: String => String = 
                        fixedTimeLogger(Level.error)

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

                        def log(time: DateTime, level: Level, msg: String): String

                        def curriedLog(time: DateTime)
                                      (level: Level)
                                      (msg: String): String = log(time, level, msg)

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

Функция высшего порядка - функция, которая принимает в качестве параметров(-а) или/и возвращает функцию.

                        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 map[A, B](f: A => B)(list: List[A]): List[B] = 
                          if(list.nonEmpty) f(list.head) +: map(f)(list.tail)
                          else Nil

Стек вызовов для списка из двух элементов

at map.appy at map.appy at map.appy at map.appy at map.appy

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

Хвостовая рекурсия - рекурсия, в которой рекурсивный вызов является последним.
Т.е. результат рекурсивного вызова - результат вычисления функции.

                        def iterativeMap[A, B](f: A => B)(list: List[A]): List[B] = {
                          import scala.collection.mutable
                          val buffer = muttable.ListBuffer[B] = muttable.ListBuffer.empty
                          for(item <- list) {
                            buffer += f(item)
                          }
                          buffer
                        }

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

Стек вызовов для списка из двух элементов

at map.loop at map.appy

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

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

Возможность	switch-case	match-case
сопоставление с вычисляемым значением (литерал, выражение)	+	+
сопоставление с типом	-	+
"Распаковка" объектов	-	+
Сопоставление с xml	-	+
Завершения проверок после совпадения	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

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

сумма (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"
                        }

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылочная прозрачность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Bound-pattern

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

Type-pattern

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

Extractor-pattern

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

@-pattern (pattern binder)

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

Pattern guards

Algebraic data type

Algebraic data type

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

Algebraic data type

Сумма:

Algebraic data type

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

Algebraic data type

И Pattern Matching

Algebraic data type

И Pattern Matching

Algebraic data type

И Pattern Matching

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

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