FP on Scala: What is a functor?

A specialist who begins to study functional programming faces both the ambiguity and complexity of the terminology, and with constant references to “serious mathematics”.

In this article, without using category theory on the one hand and Scala's esoteric language mechanisms on the other hand, we consider two important concepts

• co-variant functor
• contra variant functor

which are the starting point for understanding the whole set of categorical constructions where you can include

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

The origin of categorical terminology is explained, the role of language mechanisms in the implementation of categorical abstractions is pointed out, and several covariant ( Option , Try , Future , List , Parser ) and contravariant ( Ordering , Equiv ) functors from the Scala standard library are considered.

The first article in the "categorical series":

1. FP on Scala: what is a functor?
2. FP on Scala: Invariant Functor

If you want to dive deeper into the world of Scala, mathematics and functional programming, try the Scala for Java Developers online course (video + tests, for only 25% of the price!).

• About linguistic mechanisms of abstraction
• About category theory and Haskell
• What is a covariant functor
• Examples of covariant functors
• Covariant Functor: Identity Law
• Covariant Functor: Composition Law
• Covariant functor: use for optimization
• What is a contravariant functor
• Examples of contravariant functors
• Contravariant Functor: Identity Law
• Contravariant Functor: Composition Law
• What's next?

About linguistic mechanisms of abstraction

Immersion in any fundamentally new programming language includes the study of:

1. Language mechanisms for new types of abstraction.
2. Typical idioms / patterns in which these types of abstractions are used.

Example: OOP studies the concepts of class, instance, inheritance, polymorphism, encapsulation, delegation, ... and GoF design patterns, in which all this variety of abstraction mechanisms is used.

In my opinion, the main problem with the transition Java => Scala is that programmers do not learn new mechanisms of abstraction (generics of higher kind, path dependent types, type classes, macroses, ...) because they do not understand what to apply them to .

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

In this article, functors (covariant and contravariant) are analyzed without resorting to category theory and based on only the basic Scala features. Type classes and generics of higher kind are not used (as, for example, authors of the Scalaz libraries do: scala.scalaz.Functor + scala.scalaz.Contravariant , Cats: scala.cats.Functor + cats.functor.Contravariant , Algebird: com. twitter.algebird.Functor ). Note that often in the names of types corresponding to the idioms covariant functor and contravariant functor, abbreviated names are used - Functor and Contravariant.

Generally speaking, functional programming in Scala (L2-L3 level) is an offset relative to Java in several directions (I see three). Moreover, the offset is characterized simultaneously by four "components":

1. New programming patterns / idioms / pearls.
2. Scala's new language engine for implementing these idioms.
3. New Scala libraries with implementation of idioms based on language mechanisms.
4. New sections of mathematics, which served as a source for the key ideas of the idiom.

It should be noted that

• Studying idioms is a must (this is the “FP core").
• Learning linguistic mechanisms of abstraction - required in production mode for the implementation of idioms adapted for reuse.
• Studying typical Scala functional libraries - preferably in production mode for reusing already written and debugged idioms.
• Studying the relevant section of mathematics is not necessary for understanding or using idioms.

At a minimum, “three shifts” can be distinguished: categorical, algebraic, logical (according to the names of sections of mathematics)

Idioms FP	Scala gears	Scala Libraries	Sections of mathematics
Covariant functor, applicative functor, monad, arrow	Type classes, generics of higher kind	Scalaz, Cats	Category Theory
Dependent pair, dependent function	Path dependent types	Shapeless	Mathematical logic
Monoid, group, field, ring	Type classes, generics of higher kind	Algebird, Spire	Algebra

In short, then:

• generics of higher king are used to build a reusable abstraction (for example, a covariant functor). In OOP, in this case, an ancestor type is usually created.
• type classes are used to “apply abstraction” to your code (the user class “becomes” a covariant functor). In OOP, in this case, they are usually inherited from an ancestor abstraction.

Our examples will not use generics of higher king + type classes and therefore will not be adapted for reuse (and the "good old OOP tricks" here are not particularly suitable). But even without being ready for reuse, our examples will well demonstrate the essence of idioms.

About category theory and Haskell

In the middle of the 20th century, a new branch of mathematics arose - category theory (I note that mathematicians themselves often call it "abstract nonsense" ). Category theory came from general ideas / constructions that are widely used in many fundamental areas of mathematics (set theory, topology, functional analysis, ...) and currently claim to be the foundation / base of all mathematics (crowding out the set theory on which they built math since the beginning of the 20th century).

But if set theory focuses on the sets themselves (elements, operations on sets, cardinality of sets, sets with structure (ordered sets, partially ordered sets), ...) and mapping of sets (functions from set to set) are in the background, then in category theory the basis is categories, but, simplifiedly, category = set + mappings . A mapping is a synonym for a function (more precisely, a mapping = correspondence to elements of the domain of definition of the elements of the domain of values ​​without specifying the procedure of “moving” from arguments to values ​​directly, mapping = a function specified in a table, mapping = “external interface” of a function in the sense of f: A => Bwithout specifying an “internal implementation” (function body)), and here it turns out that such an emphasis on functions as such is very important for functional programming.

The focus on mappings gave rise to rich functional abstractions (functors, monads, ...) and these abstractions were transferred to functional programming languages ​​(the most famous implementations in Haskell). The dawn of Scala (2005-2010) is offset by 15 years relative to the dawn of Haskell (1990-1995) and many things are simply transferred ready-made from Haskell to Scala. Thus, it is more important for a Scala programmer to deal with implementations in Haskell as the main source of categorical abstractions, and not in category theory itself. This is due to the fact that during the transfer of category theory => Haskell, many important details were modified, lost or added. Important for programmers, but secondary for mathematicians.

Here is a migration example:

1. Category Theory:
   • Coovariant functor
   • Applicative functor
   • Arrow
   • Monad
   • Kleisli
2. Haskell:
   • Coovariant functor
   • Applicative functor
   • Arrow
   • Monad
   • Kleisli
3. Scala (Scalaz library)
   • Coovariant functor
   • Applicative functor
   • Arrow
   • Monad
   • Kleisli

What is a covariant functor

Some authors recommend that the Covariant Functor is a container (to be more precise, the covariant functor is rather “half the container”). I suggest remembering this metaphor, but treats it precisely as a metaphor, not a definition.

Others that the Covariant Functor is a “computational context” . This is a productive approach, but it is useful when we have fully mastered the concept and try to “get the most out of it”. Ignore it for now.

Still others suggest a “more syntactic approach." Covariant Functor is a certain type with a certain method . The method must comply with certain rules (two).

I suggest using a “syntactic approach” and using a container / storage metaphor.

From the point of view of the “syntactic approach”, a covariant functor is any type (let's call it X ) having a type parameter (let's call it T ) with a method that has the following signature (let's call it map )

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

Important: we will not inherit from this trait, we will look for similar types.

The "syntactic approach" is good in that it allows you to bring together many categorical constructions into a general scheme

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

Important: the methods indicated here are for some abstractions the only ones required (covariant / contravariant / exponential functors), and for others (applicative functor, monad, comonad) one of several required methods.

Examples of covariant functors

Those who have already started programming in Scala (or Java 8) can immediately name a lot of “container types” that are covariant functors:

Option

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

or a little closer to life

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
}

or a little closer to life

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
}

or a little closer to life

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

In general, the metaphor of the covariant functor as a container, judging by the examples, works. Really

• Option - “like a container” for one element, where something may lie (Some), or maybe not (None).
• Try - “like a container” on one element, where something may lie (Success), or maybe not (Failure, more precisely, an exception lies instead of the element).
• Future - “like a container” on one element, where something may already lie, it may lie, or the exception already lies, or the exception will lie, or it will never lie.
• List - a container in which there can be 0 ... N elements
• Parser is a little more complicated here, nothing is “stored” in it, Parser is a way to extract data from a string. However, Parser is a data source and in this it resembles a container.

A covariant functor is not just the presence of a method with a certain signature, it is also the fulfillment of two rules. Mathematicians here usually refer to category theory, and say that these rules are a consequence of the fact that the functor is a category homomorphism , that is, the mapping of a category into a category that preserves their structure (and a single arrow element is part of the category structure (Identity Law rule) and arrow composition rules (Composition law)).

Such an approach is generally unproductive in programming. Consider that in functional programming, these two rules are necessary for the ability to transform programs while maintaining functionality (usually with the goal of optimization).

Covariant Functor: Identity Law

For any covariant fun functor, the following rule IdentityLaw.case0 (fun) must be executed identically - the same as 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)
}

where identity is a polymorphic identity function (unit function) from Predef.scala

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

Quite briefly - fun.map (identity) should not change anything inside the functor.

This means that the container that stores the version and increases it with each display does not correspond to the high rank of the covariant functor

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

since it “counts” the number of display operations (even display by the identity function).

But such a code corresponds to the first rule of the functor (and the second too).

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

Here the version is simply attached to the data and invariably accompanies them when displayed.

Covariant Functor: Composition Law

For any covariant functor 'fun [T]' and any functions 'f:' and 'g', the following rule CompositionLaw.case0 (fun) should be executed identically - the same as 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)
}

That is, an arbitrary functor-container that is sequentially displayed with the function 'f' and then with the function 'g' is equivalent to the fact that we are building a new function-composition of the functions f and g (f andThen g) and displaying it once.

Consider an example. Since containers are often considered as a functor, let's make our functor a recursive data type - a binary tree type container.

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

Here, the map method (f: T => R) applies the function 'f' to an element of type 'T' in each leaf or node (Leaf, Node) and recursively propagates to the descendants of the node (Node). So we have

• tree structure is preserved
• the values ​​of the data “hanging on the tree” change

When you try to change the structure of the tree during mappings, both rules are violated (both Identity Law and Composition Law).

NOT a functor: swap when displaying the descendants of each node

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

NOT a functor: with each display, the tree grows, the leaves turn into branches

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

If you look at such (incorrect) implementations of a binary tree as a functor, you can see that they, together with the display of data, also count the number of uses of map in the form of changing the structure of the tree. So And react to identity and a couple of uses f and g is different from one use f andThen g.

Covariant functor: use for optimization

Let's look at an example that demonstrates the benefits of the axioms of a covariant functor.

As mappings, we consider linear functions over integers

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

Instead of the most general functions of the form T => R, I will use a subset of them - linear functions over Int, since, in contrast to the general form, I can build compositions of linear functions in explicit form.

As a functor, I will consider a recursive container of the type a simply connected list of integers (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
}

And now a demo

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

We can either

1. TWO times iterate over all elements of the list (TWO times go through memory)
2. and TWO times to perform arithmetic operations (* and +)

either build composition f andThen g and

1. Iterate through all the elements of the list ONCE
2. and ONE time to perform arithmetic operations

What is a contravariant functor

Let me remind you that every class X that has a method with a certain signature (conditionally called map ) and obeying certain rules ( Identity Law , Composition Law ) is called a covariant functor

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

In turn, every class X that has a method (conditionally called contramap ) with a certain signature and obeying certain rules (they are also called Identity Law , Composition Law ) is called a contravariant functor.

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

At this point, a puzzled reader may stop. Wait, but if we have a container containing a T and we obtain a function f: T => the R , it is clear how we get the container with the R . We pass the function to the container, it immerses the function inside itself and, without removing the element, applies the function to it. However, it is completely incomprehensible how, having a container with T and receiving the function f: R => T , apply it in the “reverse order” ?!

In mathematics in general terms, not every function has an inverse and there is no general way to find the inverse even when it exists. In programming, we need to act constructively (not just work with existence, uniqueness, ... but build and execute constructions) - we need to somehow construct a function g: T => R using the function f: R => T to apply it to the contents of the container! And here it turns out that our metaphor (covariant functor ~ container) does not work. Let's see why. Every container involves two operations

• put - put an item in a container
• get - extract an item from the container

however, the considered examples (Option, Try, Future, List, Parser) have a get method to one degree or another, but no put method! In Option / Try / Future, the element gets in the constructor (or in the apply method of the companion object) or as a result of some action. You can’t get into Parser at all, since Parser [T] - "recycles" lines in T. Parser [T] is the source of T, not the storage!

And here lies the secret of the error in the metaphor.

The covariant functor is half the container. The part that is responsible for retrieving data.

Let's draw it in a diagram

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

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

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

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

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

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

To search for examples of contravariant functors in the Scala standard library, we need to forget about the metaphor of the container and look for a type with one type parameter that only accepts data as arguments, but does not return as the result of the function.

An example is Ordering and Equiv

Example: 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
}

Having a way to compare strings with each other and having the function of converting an integer to a string, I can build a way to compare numbers as strings.

A little remark on the line

  val strX: Ordering[String] = String

in this case, not java.lang.String, but 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
  ...
}

and as a method contramap protrudes method 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))
  }
  ...
}

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

We are building a string comparison method (scala.math.Equiz equivalence relation) based on the java.lang.String.CASE_INSENSITIVE_ORDER comparator method

package java.lang;
public final class String implements ... {
    public static final Comparator CASE_INSENSITIVE_ORDER
                                         = new CaseInsensitiveComparator();
    private static class CaseInsensitiveComparator
            implements Comparator, java.io.Serializable {
        public int compare(String s1, String s2) {...}
        ...
    }
    ...
}

using fromComparator method

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

instead of the contramap method, it uses a cumbersome construct based on the fromFunction method

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

Contravariant Functor: Identity Law

As in the case of the covariant functor, the contravariant functor, in addition to the method with the signature, must follow two rules.

The first rule (Identity Law) states: for any contravariant fun functor, IdentityLaw.case0 (fun) must be identical, 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)
}

That is, the mapping of a contravariant functor with a unit function does not change it.

Contravariant Functor: Composition Law

The second rule (Composition Law) states: for any contravariant functor [T] and an arbitrary pair of functions f: Q => R and g: R => T, the pair must be IdentityLaw.case0 (fun) identically equal to 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)
}

That is, the mapping of a contravariant functor sequentially by a pair of functions is equivalent to a unit mapping by a composition of functions (inverted).

What's next?

The concepts of co- and contra-variant functor are only the starting point for a serious study of the use of abstractions from category theory in functional programming (in Scala terms - the transition to the use of Scalaz, Cats libraries).

Further steps include:

1. Studying compositions of co- and contra-variant functors (BiFunctor, ProFunctor, Exponential (Invariant) Functor)
2. The study of more specialized constructions (Applicative Functor, Arrow, Monad), which already really make up a new paradigm of working with calculations, input-output, error handling, mutating state. I point out at least that every monad is a covariant functor.

Unfortunately, the size of the article does not allow you to tell it all at once.

PS For those who read the article to the very end, I offer my Scala for Java Developers course for only 25% of the price (just follow the link or use the HABR-COVARIANT-FUNCTOR coupon ). The number of discount coupons is limited!