Geekly Articles each Day
📜 ⬆️ ⬇️

FP on Scala: What is a functor?

A specialist embarking on the study of functional programming faces both the ambiguity and confusion of terminology, as well as constant references to “serious mathematics”.

In this article, without using the theory of categories on the one hand and the esoteric language mechanisms of Scala on the other hand, two important concepts are considered
which are the starting point for understanding the whole set of categorical constructions, where you can include

The origin of categorical terminology is explained, the role of language mechanisms in the implementation of categorical abstractions is indicated, 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 immerse yourself in the world of Scala, mathematics and functional programming - try the online course Scala for Java Developers (video + tests, for only 25% of the price!).
')


About language abstraction mechanisms


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 abstraction 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 are used.

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

But they cannot start using them because as soon as they start talking about “objects of abstraction” (functor, monad, monoid, dependent types, ...), theorists from modern mathematics appear (category theory, abstract algebra, mathematical logic) and swoop "knock over all the pieces from the board." From the point of view of programmers, mathematicians often behave like fanatics of the Witness sect of Adventures of Categories / Homotopic Theory of Types / Calculus of Constructions: instead of speaking "in our language" and giving specific examples from the field of programming, they sypyat terms from abstract mathematics and refer to their own Sacred Texts .

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

Generally speaking, functional programming on Scala (L2-L3) is an offset from Java in several directions (I see three). At the same time, the displacement is characterized simultaneously by four “components”:
  1. New patterns / idioms / pearls programming.
  2. New Scala language mechanisms 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 key ideas of idioms.

It should be noted that

At a minimum, “three displacements” can be distinguished: categorical, algebraic, and logical (by the names of the sections of mathematics)
FP IdiomsScala mechanismsScala LibrariesSections of mathematics
Covariant functor, applicative functor, monad, arrowType classes, generics of higher kindScalaz, CatsCategory Theory
Dependent pair, dependent functionPath dependent typesShapelessMathematical logic
Monoid, group, field, ringType classes, generics of higher kindAlgebird, SpireAlgebra

In short, then:

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” are not particularly suitable here). 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 emerged - the theory of categories (I note that mathematics themselves often call it “abstract nonsense” ). The theory of categories originated from general ideas / constructions that are widely used in many fundamental branches of mathematics (set theory, topology, functional analysis, ...) and currently claims the place of the foundation / base of all mathematics (replacing the set theory on which they built mathematics from the beginning of the 20th century).

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

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

Here is a transfer example:
  1. Category Theory:
  2. Haskell:
  3. Scala (Scalaz library)


What is a covariant functor?


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

Others that Covariant Functor is the “computational context” . This is a productive approach, but it is useful when we have fully understood the concept and are trying to “squeeze the maximum out of it”. While ignoring.

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

I propose to use the "syntactic approach" and use the container / storage metaphor.

From the point of view of the “syntactic approach,” any type of covariant functor (let's call it X ) has 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 because it allows us to bring together into the general scheme many categorical constructions
 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 specified here for some abstractions are 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 on Scala (or Java 8) can immediately call a number of “container types”, which 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, according to examples, works. Really


A covariant functor is not just a method with a specific signature, it is also the fulfillment of two rules. Mathematicians here usually refer to category theory, and they say that these rules are a consequence of the fact that the functor is a category homomorphism , that is, a mapping of a category into a category that preserves their structure (the unit element of the category is the arrow element (Identity Law rule) and arrows 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 for the purpose of optimization).


Covariant functor: Identity Law


For any covariant functor, the following IdentityLaw.case0 (fun) rule must identically follow 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 a functor.

So the container that stores the version and increments it with each mapping 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 the 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) must be identically the same as CompositionLaw.case1 (fun).
 object Lawompose 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, which is sequentially displayed by the function 'f' and then by the function 'g' is equivalent to the fact that we build a new function-composition of functions f and g (f andThen g) and display it once.

Consider an example. Since containers are often viewed as a functor, let's make our functor in the form of 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 'f' function to an element of type 'T' in each sheet or node (Leaf, Node) and recursively distributes to the descendants of the node (Node). So we have


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

NOT a functor: swapping when displaying 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 map 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, along with the data display, also count the number of map applications in the form of a change in the tree structure. It means And react to identity and a couple of applications f and g differs from one application of f andThen g.


Covariant functor: use for optimization



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

As mappings, 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 common functions of the form T => R, I will use their subset — linear functions over Int, since, unlike the general form, I can build compositions of linear functions in an explicit form.

As a functor, consider a recursive container of the type of 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 demonstration
 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 to sort through all the elements of the list (TWO times to go through memory)
  2. and TWO times perform arithmetic operations (* and +)

either build a composition f andThen g and
  1. One time to sort through all the elements of the list
  2. and ONCE perform arithmetic operations



What is a contravariant functor?


Recall that a covariant functor is any class X that has a method with a specific signature (conditionally called map ) and obeying certain rules ( Identity Law , Composition Law )
 trait X[T] { def map[R](f: T => R): X[R] }


In turn, a contravariant functor is any 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 )
 trait X[T] { def contramap[R](f: R => T): X[R] }


At this point, the puzzled reader may stop. Wait, but if we have a container containing T and we get the function f: T => R , then it’s clear how we get the container with R. We transfer 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 getting the function f: R => T , apply it in “reverse order” ?!

In mathematics in general, 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 working with existence, uniqueness, ... but building and executing constructions) —somehow, using the function f: R => T , we must build the function g: T => R 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.

however, the considered examples (Option, Try, Future, List, Parser) to some extent have a get method, but no put method! In Option / Try / Future, an element gets into the constructor (or in the apply method from the companion object) or as a result of some action. In general, Parser cannot be accessed, since Parser [T] - “recycles” strings in T. Parser [T] is the source of T, not the repository!

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

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

Let's draw it as a diagram

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

That is, at the output of the covariant functor, the data element of type T lies in wait for the function f: T => R, and now this composition is, in turn, a covariant functor typed R.

In this case, it becomes clear why not storage containers, but typical data sources Iterator and Stream are also covariant functors.
???
???

Schematically, the covariant functor looks like this, we “fasten” the transformation f: R => T “at the input”, and not “at the output”.
      + ------------------------- +
    R |  T + ------ + |
   -----> f: R => T -----> X [T] |  |
      |  + ------ + |
      + ------------------------- +



Examples of contravariant functors


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

As an example, you can take 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 among themselves and having a function to convert an integer to a string, I can build a way to compare numbers as strings.

A quick note about the string
  val strX: Ordering[String] = String

in this case, not java.lang.String, but scala.math.Ordering.String is taken
 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 the contramap method is the on method.
 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 build a string comparison method (the 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<String> CASE_INSENSITIVE_ORDER = new CaseInsensitiveComparator(); private static class CaseInsensitiveComparator implements Comparator<String>, java.io.Serializable { public int compare(String s1, String s2) {...} ... } ... }

using the 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 bulky construction 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 a covariant functor, the contravariant functor, in addition to the method with signature, must follow two rules.

The first rule (Identity Law) says: for every contravariant functor fun , IdentityLaw.case0 (fun) must be identically equal to 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 by a single function does not change it.


Contravariant functor: Composition Law


The second rule (Composition Law) says: for any contravariant functor fun [T] and an arbitrary pair of functions f: Q => R and g: R => T the pair must be IdentityLaw.case0 (fun) is 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 single mapping by the composition of functions (inverted).


What's next?


The notions of a 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 and Cats libraries).

Further steps include:
  1. Studying compositions of co- and contravariant 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 work with calculations, input-output, error handling, a mutating state. Let me 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 have read the article until the very end, I offer my course “Scala for Java Developers” for only 25% of the price (just follow the link or use the coupon HABR-COVARIANT-FUNCTOR ). The number of coupon codes is limited!

Source: https://habr.com/ru/post/266905/

More articles:


All Articles