Синоним функции в программировании

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

В этой статье, не используя теорию категорий с одной стороны и эзотерические языковые механизмы Scala с другой стороны, рассмотрены два важнейших понятия

• ко-вариантный функтор
• контра-вариантный функтор

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

• Exponential (Invariant) Functor, BiFunctor, ProFunctor
• Applicative Functor, Arrow, Monad / Co-Monad
• Monad Transformers, Kleisli, Natural Transformations

Объяснено происхождение категориальной терминологии, указана роль языковых механизмов в реализации категориальных абстракций и рассмотрено несколько ковариантных (Option, Try, Future, List, Parser) и контравариантных (Ordering, Equiv) функторов из стандартной библиотеки Scala.

Первая статья в «категориальной серии»:

1. FP на Scala: что такое функтор?
2. FP на Scala: Invariant Functor

Если Вы желаете сильнее погрузиться в мир Scala, математики и функционального программирования — попробуйте онлайн-курс «Scala for Java Developers» (видео + тесты, всего за 25% цены!).

• Про языковые механизмы абстракции
• Про теорию категорий и Haskell
• Что такое ковариантный функтор
• Примеры ковариантных функторов
• Ковариантный функтор: Identity Law
• Ковариантный функтор: Composition Law
• Ковариантный функтор: используем для оптимизации
• Что такое контравариантный функтор
• Примеры контравариантных функторов
• Контравариантный функтор: Identity Law
• Контравариантный функтор: Composition Law
• Что дальше?

Про языковые механизмы абстракции

Погружение во всякий принципиально новый язык программирования включает изучение:

1. Языковых механизмов для новых типов абстрагирования.
2. Типичных идиом/шаблонов, в которых эти типы абстрагирования используется.

Пример: в ООП изучаются понятия класса, экземпляра, наследования, полиморфизма, инкапсуляции, делегирования,… и шаблоны проектирования GoF, в которых все это разнообразие механизмов абстрагирования используется.

На мой взгляд, основная проблема с переходом Java => Scala заключается в том, что программисты не учат новые механизмы абстракции (generics of higher kind, path dependent types, type classes, macroses, …) так как не понимают к чему их применить.

А не могут начать применять потому, что как только начинает идти речь про «предметы абстрагирования» (функтор, монада, моноид, зависимые типы, …) — появляются теоретики из современной математики (теория категорий, абстрактная алгебра, математическая логика) и одним махом «опрокидывают все фигуры с доски». С точки зрения программистов математики зачастую ведут себя как фанатики секты Свидетелей Пришествия Категорий/ГомотопическойТеорииТипов/ИсчисленияКонструкций: вместо того, что бы говорить «на нашем языке» и привести конкретные примеры из области программирования, они сыпят терминами из абстрактной математики и отсылают к своим же Священным Текстам.

В этой статье разобраны функторы (ковариантный и контравариантный) без обращения к теории категорий и на основе только базовые возможности Scala. Не используются type classes и generics of higher kind (как это делают, например, авторы библиотек Scalaz: scala.scalaz.Functor + scala.scalaz.Contravariant, Cats: scala.cats.Functor + cats.functor.Contravariant, Algebird: com.twitter.algebird.Functor). Обратите внимание, часто в названиях типов, соответствующих идиомам covariant functor и contravariant functor, используют сокращенные названия — Functor и Contravariant.

Вообще говоря, функциональное программирование на Scala (уровня L2-L3) — это смещение относительно Java в нескольких направлениях (я вижу три). При этом смещение характеризуется одновременно четырьмя «компонентами»:

1. Новыми шаблонами/идиомами/перлами программирования.
2. Новыми языковыми механизмами Scala для реализации этих идиом.
3. Новыми библиотеками Scala с реализацией идиом на основе языковых механизмов.
4. Новыми разделами математики, которые послужили источником для ключевых идей идиомы.

Надо отметить, что

• Изучение идиом — обязательно (это и есть «ядро FP»).
• Изучение языковых механизмов абстракции — требуется в production mode для реализации идиом, приспособленных к повторному использованию.
• Изучение типичных функциональных библиотек Scala — желательно в production mode для повторного использования уже написанных и отлаженных идиом.
• Изучение соответствующего раздела математики не является обязательным для понимания или использования идиом.

Как минимум можно выделить «три смещения»: категориальное, алгебраическое, логическое (по названиям разделов математики)

Если кратко, то:

• generics of higher king служат для построения повторно используемой абстракции (например, ковариантного функтора). В ООП, в таком случае, обычно создают тип-предок.
• type classes служат для «применения абстракции» к Вашему коду (класс пользователя «становится» ковариантным функтором). В ООП, в таком случае, обычно наследуются от предка-абстракции.

Наши примеры не будут использовать generics of higher king + type classes и потому не будут приспособлены к повторному использованию (а «старые добрые трюки ООП» тут не особенно подходят). Но даже не будучи готовыми к повторному использованию наши примеры хорошо продемонстрируют суть идиом.

Про теорию категорий и Haskell

В середине 20-го века возник новый раздел математики — теория категорий (отмечу, что сами математики часто называют его «абстрактная чепуха»). Теория категорий произошла из общих идей/конструкций, которые широко используются во многих фундаментальных разделах математики (теория множеств, топология, функциональный анализ, …) и в данный момент претендует на место основания/базы всей математики (вытесняя теорию множеств, на которой строили математику с начала 20-го века).

Но если теория множеств акцентирует внимание на самих множествах (элементы, операции над множествами, мощность множества, множества со структурой (упорядоченные множества, частично упорядоченные множества), …) и отображения множеств (функции из множества в множество) находятся на втором плане, то в теории категорий основой являются категории, а, упрощенно, категория = множество + отображения. Отображение — это синоним функции (точнее, отображение = соответствие элементам области определения элементов области значений без указания непосредственно процедуры «перехода» от аргументов к значениям, отображение = функция заданная таблично, отображение = «внешний интерфейс» функции в смысле f: A => B без указания «внутренней реализации» (тела функции)), и вот тут оказывается, что такой акцент на функциях как таковых очень важен для функционального программирования.

Концентрация на отображениях породила богатые функциональные абстракции (функторы, монады, …) и эти абстракции были перенесены в языки функционального программирования (наиболее известны реализации в Haskell). Рассвет Scala (2005-2010) смещен на 15 лет относительно рассвета Haskell (1990-1995) и многие вещи просто перенесены уже готовыми из Haskell в Scala. Таким образом, для Scala-программиста важнее разбираться с реализациями в Haskell, как основным источником категориальных абстракций, а не в самой теории категорий. Это связано с тем, что при переносе теория категорий => Haskell были видоизменены, утрачены или добавлены множество важных деталей. Важных для программистов, но второстепенных для математиков.

Вот пример переноса:

1. Теория категорий:
   • Covariant functor
   • Applicative functor
   • Arrow
   • Monad
   • Kleisli
2. Haskell:
   • Covariant functor
   • Applicative functor
   • Arrow
   • Monad
   • Kleisli
3. Scala (библиотека Scalaz)
   • Covariant functor
   • Applicative functor
   • Arrow
   • Monad
   • Kleisli

Что такое ковариантный функтор

Одни авторы рекомендуют считать, что Covariant Functor — это контейнер (если быть более точным, то ковариантный функтор — это скорее «половина контейнера»). Предлагаю запомнить эту метафору, но относится к ней именно как к метафоре, а не определению.

Другие, что Covariant Functor — это «computational context». Это продуктивный подход, но он полезен, когда мы уже в полной мере освоили понятие и стараемся «выжать из него максимум». Пока игнорируем.

Третьи предлагают «более синтаксический подход». Covariant Functor — это некий тип с определенным методом. Метод должен соответствовать определенным правилам (двум).

Я предлагаю использовать «синтаксический подход» и использовать метафору контейнера/хранилища.

С точки зрения «синтаксического подхода», ковариантным функтором является всякий тип (назовем его X) имеющий type parameter (назовем его T) с методом, который имеет следующую сигнатуру (назовем его map)

trait X[T] {
  def map(f: T => R): X[R]
}

Важно: мы не будем наследоваться от этого trait-а, мы будем искать похожие типы.

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

trait X[T] {
  // covariant functor (functor)
  def map[R](f: T => R): X[R]

  // contravariant functor (contravariant)
  def contramap[R](f: R => T): X[R]

  // exponential functor (invariant functor)
  def xmap[R](f: (T => R, R => T)): X[R]

  // applicative functor
  def apply[R](f: X[T => R]): X[R]

  // monad
  def flatMap[R](f: T => X[R]): X[R]

  // comonad
  def coflatMap[R](f: X[T] => R): X[R]
}

Важно: указанные тут методы для некоторых абстракций являются единственными требуемыми (covariant / contravariant / exponential functors), а для других (applicative functor, monad, comonad) — одним из нескольких требуемых методов.

Примеры ковариантных функторов

Те, кто уже начали программировать на Scala (или на Java 8), тут же могут назвать множество «типов-контейнеров», которые являются ковариантными функторами:

Option

import java.lang.Integer.toHexString

object Demo extends App {
  val k: Option[Int] = Option(100500)
  val s: Option[String] = k map toHexString
}

или чуть ближе к жизни

import java.lang.Integer.toHexString

object Demo extends App  {
  val k: Option[Int] = Map("A" -> 0, "B" -> 1).get("C")
  val s: Option[String] = s map toHexString
 }

Try

import java.lang.Integer.toHexString
import scala.util.Try

object Demo App {
  val k: Try[Int] = Try(100500)
  val s: Try[String] = k map toHexString
}

или чуть ближе к жизни

import java.lang.Integer.toHexString
import scala.util.Try

object Demo extends App {
  def f(x: Int, y: Int): Try[Int] = Try(x / y)
  val s: Try[String] = f(1, 0) map toHexString
}

Future

import java.lang.Integer.toHexString
import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.Future

object Demo extends App {
  val k: Future[Int] = Future(100500)
  val s: Future[String] = k map toHexString
}

или чуть ближе к жизни

import java.lang.Integer.toHexString
import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.Future

object Demo extends App {
  def calc: Int = (0 to 1000000000).sum

  val k: Future[Int] = Future(calc)
  val s: Future[String] = k map toHexString
}

List

import java.lang.Integer.toHexString

object Demo extends App {
  val k: List[Int] = List(0, 42, 100500)
  val s: List[String] = k map toHexString
}

Parser

import java.lang.Integer.toHexString
import scala.util.parsing.combinator._

object Demo extends RegexParsers with App {
  val k: Parser[Int] = """(0|[1-9]d*)""".r ^^ { _.toInt }
  val s: Parser[String] = k map toHexString

  println(parseAll(k, "255"))
  println(parseAll(s, "255"))
}

>> [1.4] parsed: 255
>> [1.4] parsed: FF

В целом метафора ковариантного функтора как контейнера, судя по примерам, работает. Действительно

• Option — «как бы контейнер» на один элемент, где может что-то лежит (Some), а может и нет (None).
• Try — «как бы контейнер» на один элемент, где может что-то лежит (Success), а может и нет (Failure, точнее вместо элемента лежит исключение).
• Future — «как бы контейнер» на один элемент, где может что-то уже лежит, может будет лежать, или уже лежит исключение, или будет лежать исключение или никогда ничего лежать не будет.
• List — контейнер, в котором может быть 0…N элементов
• Parser — тут чуть сложнее, в нем ничего не «хранится», Parser — это способ извлекать данные из строки. Тем не менее, Parser — это источник данных и в этом он похож на контейнер.

Ковариантный функтор — это не просто наличие метода с определенной сигнатурой, это также выполнение двух правил. Математики тут обычно отсылают к теории категорий, и говорят, что эти правила — следствие того, что функтор — это гомоморфизм категорий, то есть отображение категории в категорию, сохраняющее их структуру (а частью структуры категории являются единичный элемент-стрелка (правило Identity Law) и правила композиции стрелок (правило Composition law)).

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

Ковариантный функтор: Identity Law

Для любого ковариантного функтора ‘fun’ должно тождественно выполняться следующее правило IdentityLaw.case0(fun) — то же самое что и IdentityLaw.case1(fun).

object IdentityLaw {
  def case0[T](fun: Functor[T]): Functor[T] = identity(fun)
  def case1[T](fun: Functor[T]): Functor[T] = fun.map(identity)
}

где identity — это полиморфная тождественная функция (единичная функция) из Predef.scala

object Predef ... {
  def identity[A](x: A): A = x
  ...
}

Совсем кратко — fun.map(identity) ничего не должно менять внутри функтора.

Значит контейнер, который хранит версию и увеличивает ее при каждом отображении — не соответствует высокому званию ковариантного функтора

// Это - НЕ ковариантный функтор
class Holder[T](value: T, ver: Int = 0) {
  def map[R](f: T => R): Holder[R] = new Holder[R](f(value), ver + 1)
}

так как он «подсчитывает» количество операций отображения (даже отображения функцией identity).

А вот такой код — соответствует первому правилу функтора (и второму тоже).

// Это - ковариантный функтор
class Holder[T](value: T, ver: Int = 0) {
  def map[R](f: T => R): Holder[R] = new Holder[R](f(value), ver)
}

Тут версия просто прикреплена к данным и неизменно сопровождает их при отображении.

Ковариантный функтор: Composition Law

Для любого ковариантного функтора ‘fun[T]’ и любых функций ‘f: ‘ и ‘g’ должно тождественно выполняться следующее правило CompositionLaw.case0(fun) — то же самое что и CompositionLaw.case1(fun).

object LawСompose extends App {
  def case0[T, R, Q](fun: Functor[T], f: T => R, g: R => Q): Functor[Q] =
    (fun map f) map g
  def case1[T, R, Q](fun: Functor[T], f: T => R, g: R => Q): Functor[Q] =
    fun map (f andThen g)
}

То есть произвольный функтор-контейнер, который последовательно отображают функцией ‘f’ и потом функцией ‘g’ эквивалентен тому, что мы строим новую функцию-композицию функций f и g (f andThen g) и отображаем один раз.

Рассмотрим пример. Поскольку в качестве функтора часто рассматривают контейнеры, то давайте сделаем свой функтор в виде рекурсивного типа данных — контейнера типа бинарное дерево.

sealed trait Tree[T] {
  def map[R](f: T => R): Tree[R]
}
case class Node[T](value: T, fst: Tree[T], snd: Tree[T]) extends Tree[T] {
  def map[R](f: T => R) = Node(f(value), fst map f, snd map f)
}
case class Leaf[T](value: T) extends Tree[T] {
  def map[R](f: T => R) = Leaf(f(value))
}

Здесь метод map(f: T=>R) применяет функцию ‘f’ к элементу типа ‘T’ в каждом листе или узле (Leaf, Node) и рекурсивно распространяет на потомков узла (Node). Значит у нас

• сохраняется структура дерева
• меняются значения данных, «висящих на дереве»

При попытке менять структуру дерева при отображениях нарушаются оба правила (и Identity Law и Composition Law).

НЕ функтор: меняю местами при отображении потомков каждого узла

case class Node[T](value: T, fst: Tree[T], snd: Tree[T]) extends Tree[T] {
  def map[R](f: T => R) = Node(f(value), snd map f, fst map f)
}

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

case class Leaf[T](value: T) extends Tree[T] {
  def map[R](f: T => R) = Node(f(value), Leaf(f(value)), Leaf(f(value)))
}

Если посмотреть на такие (неправильные) реализации бинарного дерева как функтора, то видно, что они вместе с отображением данных, так же подсчитывают количество применений map в виде изменения структуры дерева. Значит И реагируют на identity и пара применений f и g отличается от одного применения f andThen g.

Ковариантный функтор: используем для оптимизации

Давайте рассмотрим пример, демонстрирующий пользу от аксиом ковариантного функтора.

В качестве отображений рассмотрим линейные функции над целыми числами

case class LinFun(a: Int, b: Int) {
  def apply(k: Int): Int = a * k + b
  def andThen[A](that: LinFun): LinFun = LinFun(this.a * that.a, that.a * this.b + that.b)
}

Вместо самых общих функций вида T=>R я буду использовать их подмножество — линейные функции над Int, так как в отличии от общего вида я умею строить композиции линейных функций в явном виде.

В качестве функтора рассмотрю рекурсивный контейнер типа односвязный список целых чисел (Int)

sealed trait IntSeq {
  def map(f: LinFun): IntSeq
}
case class Node(value: Int, tail: IntSeq) extends IntSeq {
  override def map(f: LinFun): IntSeq = Node(f(value), tail.map(f))
}
case object Last extends IntSeq {
  override def map(f: LinFun): IntSeq = Last
}

А теперь — демонстрация

object Demo extends App {
  val seq = Node(0, Node(1, Node(2, Node(3, Last))))
  val f = LinFun(2, 3) // k => 2 * k + 3
  val g = LinFun(4, 5) // k => 4 * k + 5

  val res0 = (seq map f) map g        // slow version
  val res1 = seq map (f andThen g)     // fast version

  println(res0)
  println(res1)
}

>> Node(17,Node(25,Node(33,Node(41,Last))))
>> Node(17,Node(25,Node(33,Node(41,Last))))

Мы можем либо

1. ДВА раза перебрать все элементы списка (ДВА раза пройтись по памяти)
2. и ДВА раза выполнить арифметические операции (* и +)

либо построить композицию f andThen g и

1. ОДИН раз перебирать все элементы списка
2. и ОДИН раз выполнить арифметические операции

Что такое контравариантный функтор

Напомню, что ковариантным функтором называется всякий класс X, который имеет метод с определенной сигнатурой (условно называемый map) и подчиняющийся определенным правилам (Identity Law, Composition Law)

trait X[T] {
  def map[R](f: T => R): X[R]
}

В свою очередь контравариантным функтором называется всякий класс X, который имеет метод (условно называемый contramap) с определенной сигнатурой и подчиняющийся определенным правилам (они тоже называются Identity Law, Composition Law)

trait X[T] {
  def contramap[R](f: R => T): X[R]
}

В этом месте недоуменный читатель может остановиться. Постойте, но если у нас есть контейнер, содержащий T и мы получаем функцию f: T => R, то понятно каким образом мы получаем контейнер с R. Передаем функцию контейнеру, тот погружает функцию внутрь себя и не извлекая элемент применяет к нему функцию. Однако совершенно непонятно, как, имея контейнер с T и получив функцию f: R => T, применить ее в «обратном порядке»?!

В математике в общем виде не у всякой функции есть обратная и нет общего способа найти обратную даже когда она существует. В программировании же нам необходимо действовать конструктивно (не просто работать с существованием, единственность,… но строить и исполнять конструкции) — надо каким-то образом по функции f: R => T построить функцию g: T => R что бы применить ее к содержимому контейнера!

И вот тут оказывается, что наша метафора (ковариантный функтор ~ контейнер) не работает. Давайте разберем почему.

Всякий контейнер предполагает две операции

• put — поместить элемент в контейнер
• get — извлечь элемент из контейнера

однако у рассмотренных примеров (Option, Try, Future, List, Parser) в той или иной мере есть метод get, но нет метода put! В Option/Try/Future элемент попадает в конструкторе (или в методе apply от companion object) или же в результате какого-то действия. В Parser вообще нельзя попасть, так как Parser[T] — «перерабатывает» строки в T. Parser[T] — это источник T, а не хранилище!

И вот тут кроется секрет ошибки в метафоре.

Ковариантный функтор — это половина контейнера. Та часть, которая отвечает за извлечение данных.

Давайте изобразим это в виде схемы

     +-------------------------+
     | +------+ T              | R
     | | X[T] -----> f: T=>R ---->
     | +------+                |
     +-------------------------+

То есть «на выходе из» ковариантного функтора элемент данных типа T подстерегает функция f: T=>R и вот эта композиция является, в свою очередь, ковариантным функтором типизированным R.

В таком случае становится понятным, почему не контейнеры-хранилища, но типичные источники данных Iterator и Stream тоже являются ковариантными функторами.
???
???

Схематично ковариантный функтор выглядит следующим образом, мы «прикручиваем» преобразование f: R => T «на входе», а не «на выходе».

     +-------------------------+
   R |              T +------+ |
  -----> f: R=>T -----> X[T] | |
     |                +------+ |
     +-------------------------+

Примеры контравариантных функторов

Для поиска примеров контравариантных функторов в стандартной библиотеке Scala нам надо забыть про метафору контейнера и искать тип с одним type parameter, который только принимает данные в виде аргументов, но не возвращает в виде результата функции.

В качестве примера можно взять Ordering и Equiv

Пример: Ordering

import scala.math.Ordering._

object Demo extends App {
  val strX: Ordering[String] = String
  val f: (Int => String) = _.toString
  val intX: Ordering[Int] = strX on f
}

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

Небольшое замечание относительно строки

  val strX: Ordering[String] = String

в данном случае берется не java.lang.String, а scala.math.Ordering.String

package scala.math

trait Ordering[T] extends ...  {
  trait StringOrdering extends Ordering[String] {
    def compare(x: String, y: String) = x.compareTo(y)
  }
  implicit object String extends StringOrdering
  ...
}

а в качестве метода contramap выступает метод on

package scala.math

trait Ordering[T] extends ... {
  def on[R](f: R => T): Ordering[R] = new Ordering[R] {
    def compare(x: R, y: R) = outer.compare(f(x), f(y))
  }
  ...
}

Пример: Equiv

import java.lang.String.CASE_INSENSITIVE_ORDER
import scala.math.Equiv
import scala.math.Equiv.{fromFunction, fromComparator}

object Demo extends App {
  val strX: Equiv[String] = fromComparator(CASE_INSENSITIVE_ORDER)
  val f: (Int => String) = _.toString
  val intX: Equiv[Int] = fromFunction((x, y) => strX.equiv(f(x), f(y)))
}

Мы строим метод сравнения строк (отношение эквивалентности scala.math.Equiz) на основе метода компаратора java.lang.String.CASE_INSENSITIVE_ORDER

package java.lang;

public final class String implements ... {
    public static final Comparator<String> CASE_INSENSITIVE_ORDER
                                         = new CaseInsensitiveComparator();

    private static class CaseInsensitiveComparator
            implements Comparator<String>, java.io.Serializable {
        public int compare(String s1, String s2) {...}
        ...
    }
    ...
}

используя метод fromComparator

object Equiv extends ... {
  def fromComparator[T](cmp: Comparator[T]): Equiv[T] = new Equiv[T] {
    def equiv(x: T, y: T) = cmp.compare(x, y) == 0
  }
  ...
}

а вместо метода contramap использует громоздкую конструкцию на основе метода fromFunction

object Equiv extends ... {
  def fromFunction[T](cmp: (T, T) => Boolean): Equiv[T] = new Equiv[T] {
    def equiv(x: T, y: T) = cmp(x, y)
  }
  ...
}

Контравариантный функтор: Identity Law

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

Первое правило (Identity Law) гласит: для всякого контравариантного функтора fun должно выполняться IdentityLaw.case0(fun) тождественно равно IdentityLaw.case1(fun)

object IdentityLaw {
  def case0[T](fun: Contravariant[T]): Contravariant[T] = identity(fun)  
  def case1[T](fun: Contravariant[T]): Contravariant[T] = fun.contramap(identity)
}

То есть отображение контравариантного функтора единичной функцией не меняет его.

Контравариантный функтор: Composition Law

Второе правило (Composition Law) гласит: для всякого контравариантного функтора fun[T] и произвольной пары функций f: Q => R и g: R => T пары должно быть IdentityLaw.case0(fun) тождественно равно IdentityLaw.case1(fun)

object CompositionLaw {
  def case0[Q, R, T](fun: Contravariant[T], f: Q => R, g: R => T): Contravariant[Q] =
    (fun contramap g) contramap f
  def case1[Q, R, T](fun: Contravariant[T], f: Q => R, g: R => T): Contravariant[Q] =
    fun contramap (f andThen g)
}

То есть отображение контравариантного функтора последовательно парой функций эквивалентно единичному отображению композицией функций (инвертированной).

Что дальше?

Понятия ко- и контра-вариантного функтора являются только стартовой точкой для серьезного изучения применения абстракций из теории категорий в функциональном программировании (в терминах Scala — переход к использованию библиотек Scalaz, Cats).

Дальнейшие шаги включают:

1. Изучение композиций ко- и контра- вариантных функторов (BiFunctor, ProFunctor, Exponential (Invariant) Functor)
2. Изучение более специализированных конструкций (Applicative Functor, Arrow, Monad), которые уже действительно составляют новую парадигму работы с вычислениями, вводом-выводом, обработкой ошибок, мутирующим состоянием. Укажу хотя бы на то, что всякая монада является ковариантным функтором.

К сожалению, размер статьи не позволяет рассказать это все за один раз.

P.S. Для тех, кто прочитал статью до самого конца предлагаю мой курс «Scala for Java Developers» всего за 25% цены (просто идите по ссылке или воспользуйтесь купоном HABR-COVARIANT-FUNCTOR). Количество скидочных купонов ограничено!

Мы объединили описание функций и объектов в одной лекции по причине того, что они тесно взаимосвязаны. Каждая функция является не только именем для группы операторов, но одновременно и объектом. Объекты же (пользовательские) создаются с помощью функций (конструкторов).

Функции

Язык программирования не может обойтись без механизма многократного использования кода программы. Такой механизм обеспечивается процедурами или функциями. В JavaScript функция выступает в качестве одного из основных типов данных. Одновременно с этим в JavaScript определен класс объектов Function.

В общем случае любой объект JavaScript определяется через функцию. Для создания объекта используется конструктор, который в свою очередь вводится через Function. Таким образом, с функциями в JavaScript связаны следующие ключевые вопросы:

• функция как тип данных;
• функция как объект;
• функция как конструктор объектов.

Именно эти вопросы мы и рассмотрим в данном разделе.

Функция как тип данных

Определяют функцию при помощи ключевого слова function:

function f(arg1,arg2,...)
{
/* тело функции */
}

Здесь следует обратить внимание на следующие моменты. Во-первых, function определяет переменную с именем f. Эта переменная имеет тип function:

document.write('Тип переменной f: '+ typeof(f));
// Будет выведено: Тип переменной f: function

Во-вторых, эта переменная, как и любая другая, имеет значение — свой исходный текст:

var i=5;

function f(a,b,c)
{
 if (a>b) return c;
}

document.write('Значение переменной i: '+ i.valueOf());

// Будет выведено:
// Значение переменной i: 5

document.write('Значение переменной f:<BR>'+ f.valueOf());

// Будет выведено:
// Значение переменной f:
// function f(a,b,c)
// {
//  if (a>b) return c;
// }

Как видим, метод valueOf() применим как к числовой переменной i, так и к переменной f, и возвращает их значение. Более того, значение переменной f можно присвоить другой переменной, тем самым создав «синоним» функции f:

function f(a,b,c)
{
 if (a>b) return c;
 else return c+8;
}

var g = f;
alert('Значение f(2,3,2): '+ f(2,3,2) );
alert('Значение g(2,3,2): '+ g(2,3,2) );

// Будет выведено:
// Значение f(2,3,2): 10
// Значение g(2,3,2): 10

Этим приемом удобно пользоваться для сокращения длины кода. Например, если нужно много раз вызвать метод document.write(), то можно ввести переменную: var W = document.write (обратите внимание — без скобок!), а затем вызывать: W(‘<H1>Лекция</H1>’).

Коль скоро функцию можно присвоить переменной, то ее можно передать и в качестве аргумента другой функции.

function kvadrat(a)
{   return a*a;   }

function polinom(a,kvadrat)
{ return kvadrat(a)+a+5;}

alert(polinom(3,kvadrat));
// Будет выведено: 17

Все это усиливается при использовании функции eval(), которая в качестве аргумента принимает строку, которую рассматривает как последовательность операторов JavaScript (блок) и выполняет этот блок. В качестве иллюстрации приведем скрипт, который позволяет вычислять функцию f(f(…f(N)…)), где число вложений функции f() задается пользователем.

<SCRIPT>
function kvadrat(a)
{   return a*a;   }

function SuperPower()
{ var
 N = parseInt(document.f.n.value),
 K = parseInt(document.f.k.value),
 L = R = '';

 for(i=0; i<K; i++)
 {
  L+='kvadrat(';
  R+=')';
 }
 return eval(L+N+R);
}
</SCRIPT>

<FORM NAME=f>
 Введите аргумент (число):
 <INPUT NAME=n><BR>
 Сколько раз возвести его в квадрат?
 <INPUT NAME=k><BR>
 <INPUT TYPE=button value="Возвести" onClick="alert(SuperPower());">
</FORM>

Обратите внимание на запись L=R=». Она выполняется справа налево. Сначала происходит присваивание R=». Операция присваивания выдает в качестве результата значение вычисленного выражения (в нашем случае — пустая строка). Она-то и присваивается далее переменной L.

Поясним работу скрипта в целом. В функции SuperPower() мы сначала считываем значения, введенные в поля формы, и преобразуем их из строк в целые числа функцией parseInt(). Далее с помощью цикла for мы собираем строку L, состоящую из K копий строки » kvadrat( «, и строку R, состоящую из K правых скобок » ) «. Теперь мы составляем выражение L+N+R, представляющее собой K раз вложенную в себя функцию kvadrat(), примененную к аргументу N. Наконец, с помощью функции eval() вычисляем полученное выражение. Таким образом, вычисляется функция (…((N)²)²…)².

Функция как объект

У любого типа данных JavaScript существует объектовая «обертка» (wrapper), которая позволяет применять методы типов данных к переменным и литералам, а также получать значения их свойств. Например, длина строки символов определяется свойством length. Аналогичная «обертка» есть и у функций — это класс объектов Function.

Например, увидеть значение функции можно не только при помощи метода valueOf(), но и используя метод toString():

function f(x,y)
{
  return x-y;
}
document.write(f.toString());

Результат распечатки:

function f(x,y) { return x-y; }

Свойства же функции как объекта доступны программисту только тогда, когда они вызываются внутри этой функции. Наиболее часто используемыми свойствами являются: массив (коллекция) аргументов функции ( arguments[] ), его длина ( length ), имя функции, вызвавшей данную функцию ( caller ), и прототип ( prototype ).

Рассмотрим пример использования списка аргументов функции и его длины:

function my_sort()
{
  a = new Array(my_sort.arguments.length);
  for(i=0;i<my_sort.arguments.length;i++)
     a[i] = my_sort.arguments[i];
  return a.sort();
}

b = my_sort(9,5,7,3,2);
document.write(b);
// Будет выдано: 2,3,5,7,9

Чтобы узнать, какая функция вызвала данную функцию, используется свойство caller. Возвращаемое ею значение имеет тип function. Пример:

function s()
{ document.write(s.caller+"<BR>"); }

function M()
{ s(); return 5; }

function N()
{ s(); return 7; }

M();   N();

Результат исполнения:

function M() { s(); return 5; }
function N() { s(); return 7; }

Еще одним свойством объекта класса Function является prototype. Но это — общее свойство всех объектов, не только функций, поэтому и обсуждать его мы будем в следующем разделе в контексте типа данных Object. Упомянем только о конструкторе объекта класса Function:

f = new Function(arg_1,...,arg_n, body)

Здесь f — это объект класса Function (его можно использовать как обычную функцию), arg_1, …, arg_n — аргументы функции f, а body — строка, задающая тело функции f.

Данный конструктор можно использовать, например, для описания функций, которые назначают или переопределяют методы объектов. Здесь мы вплотную подошли к вопросу конструирования объектов. Дело в том, что переменные внутри функции можно рассматривать в качестве ее свойств, а функции — в качестве методов:

function Rectangle(a,b,c,d)
{
this.x0 = a;
this.y0 = b;
this.x1 = c;
this.y1 = d;

this.area = new Function(
 "return Math.abs((this.x1-this.x0)*(this.y1-this.y0))");
}

r = new Rectangle(0,0,30,50);

document.write("Площадь: "+r.area());

// Будет выведено:
// Площадь: 1500

Обратите внимание еще на одну особенность — ключевое слово this. Оно позволяет сослаться на текущий объект, в рамках которого происходит исполнение JavaScript-кода. В данном случае это объект класса Rectangle.

Порой обучение продвигается с трудом. Сложная теория, непонятные задания… Хочется бросить. Не сдавайтесь, все сложности можно преодолеть. Рассказываем, как

Не понятна формулировка, нашли опечатку?

Выделите текст, нажмите ctrl + enter и опишите проблему, затем отправьте нам. В течение нескольких дней мы улучшим формулировку или исправим опечатку

Что-то не получается в уроке?

Загляните в раздел «Обсуждение»:

1. Изучите вопросы, которые задавали по уроку другие студенты — возможно, ответ на ваш уже есть
2. Если вопросы остались, задайте свой. Расскажите, что непонятно или сложно, дайте ссылку на ваше решение. Обратите внимание — команда поддержки не отвечает на вопросы по коду, но поможет разобраться с заданием или выводом тестов
3. Мы отвечаем на сообщения в течение 2-3 дней. К «Обсуждениям» могут подключаться и другие студенты. Возможно, получится решить вопрос быстрее!

Подробнее о том, как задавать вопросы по уроку

2 ответа