FP on Scala: Invariant Functor

The article discusses

• As such an abstraction of category theory as an invariant functor (Invariant Functor), which is sometimes called an Exponential Functor, is expressed in Scala.
• Two rules ( Identity Law , Composition Law ), which each invariant functor is supposed to follow.
• An example of an invariant state functor (Value Holder) is given.
• An example of an invariant functor-relation between elements of a set (semigroup) is given.

The publication is a continuation of FP on Scala: What is a functor? which addressed the following issues

• What is the relationship between category theory , Haskell and Scala .
• What is a covariant functor .
• What is a contravariant functor .

Content

• Introduction
• What is Invariant Functor?
• Invariant Functor - Identity Law
• Invariant Functor - Composition Law
• Example # 1: Value Holder
• Example # 2: Semigroup
• Invariant functor in libraries

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! The number of reference coupons is limited!).

Introduction

Let me remind you of the main points of the previous article :

• There is no need to know category theory to understand categorical abstractions within the framework of functional programming. Moreover, category theory does not give good examples.
• Implementations of categorical abstractions in Scala came from Haskell. It is useful to be able to read the source code of a more mature Haskell, in order to recruit examples for a younger Scala.
• The main categorical libraries ( Scalaz , Cats ) use generics of higher kind to express categorical abstractions. However, this language mechanism (which is not present in either Java or C #) is used to construct reusable abstractions. "Piece" idioms can be implemented with minimal means.
• A covariant functor is a data source.
• A contravariant functor is a data receiver.

.
But still, the author strongly recommends reading the previous article .

What is Invariant Functor?

An invariant functor is a covariant and contravariant “in one bottle” functor.
')
In the form of a signature, this can be expressed as follows.

trait Invariant[T] { def xmap[R](f: T => R, g: R => T): Invariant[R] } 

That is, to obtain a new invariant functor, we need to provide the mappings required by both the covariant functor ( f: T => R ) and contravariant ( g: R => T ).

Or graphically

      + --------------------------------------- +
    R |  T + ------ + T |  R 
   -----> f: R => T -----> C [T] -----> g: T => R ----->
      |  + ------ + |
      + --------------------------------------- +

That is, “translated” Invariant [R] is “reduced” to the original Invariant [T] using a pair of mutually inverse transformations f and g that “wait” for the data “at the input” and “at the output”.

Invariant Functor - Identity Law

Invariant Functor (along with Covariant Functor and Contravariant Functor) is also obliged to follow a couple of similar rules. And the first rule (Identity Law) says: for any invariant functor fun [T] , IdentityLaw.case0 (fun) must be identically equal to IdentityLaw.case1 (fun).

 object IdentityLaw { def case0[T](fun: Invariant[T]): Invariant[T] = fun def case1[T](fun: Invariant[T]): Invariant[T] = fun.xmap(x => x, x => x) } 

The meaning of the rule becomes clear if you turn to the meaning of the Identity Law for the Covariant Functor and the Identity Law for the Contravariant Functor .

Invariant Functor - Composition Law

The second rule (Composition Law) says: for any invariant functor fun [T] and any functions f1: T => R , g1: R => T , f2: R => Q , g2: Q => R , CompositionLaw should be executed. case0 (fun, f1, g1, f2, g2) is identically equal to CompositionLaw.case1 (fun, f1, g1, f2, g2).

 object CompositionLaw { def case0[T, R, Q](fun: Invariant[T], f1: T => R, g1: R => T, f2: R => Q, g2: Q => R): Invariant[Q] = fun.xmap(f1, g1).xmap(f2, g2) def case1[T, R, Q](fun: Invariant[T], f1: T => R, g1: R => T, f2: R => Q, g2: Q => R): Invariant[Q] = fun.xmap(f2 compose f1, g1 compose g2) } 

The meaning of the rule becomes clear if you turn to the meaning of the Composition Law for the Covariant Functor and the Composition Law for the Contravariant Functor .

Example # 1: Value Holder

From the previous article, it follows that the covariant and contravariant functors are two “container half” (this is a metaphor, it is more accurate to consider the signature + rules). So, if an invariant (exponential) functor is both, then for example you can take the simplest of the containers - value holder.

 trait Holder[T] { self => def put(arg: T): Unit def get: T def xmap[R](f: T => R, g: R => T): Holder[R] = new Holder[R] { override def put(arg: R): Unit = self.put(g(arg)) override def get: R = f(self.get) } } 

For example, value holder for strings.

 class StrHolder(var value: String = null) extends Holder[String] { override def put(arg: String): Unit = {value = arg} override def get: String = value } 

Demonstration

 object Demo extends App { val f: String => Int = Integer.parseInt(_, 16) val g: Int => String = Integer.toHexString val s: Holder[String] = new StrHolder val k: Holder[Int] = s xmap (f, g) k put 100500 println(k get) } >> 100500 

We have an Int container, which stores them in a string hex format.

Well, why do we need the simplest value holder? We can increase its functionality in several directions.

• You can attach data (version, put / get log, ...).
• You can intercept calls (for synchronization, logging of put / get calls, proxying to remote sources, ...).

Note: note that the rules of the invariant functor prevent the xmap operations from being counted, but not others (put, get)! You can log in the internal state calls put / get / ..., but not xmap.
Task: Implement this logic.

Example # 2: Semigroup

It is important to note that the covariant and contravariant functors are precisely the sources and receivers of data that work according to certain rules (Identity Law, Composition Law), and not the “half container”. We are not required to store data (make it part of our state), we just have to have their arguments and return values ​​of the methods. But if we do not store them, then the put and get operations should “be performed simultaneously,” that is we are looking for structures whose type parameter T is present in both the arguments and the return value.

Our examples can be not states, but processes ! Note that what is a process (method) can express the relationship between elements).

Let me remind you of the basic algebraic terminology (we need the simplest relations between the elements of a set that give an invariant functor. Quite simply, the simplest is, of course, an equivalence relation and order, but according to the previous article , they are contravariant functors).

A groupoid (groupoid) is a set provided with a single binary operation (T # T => T, T is a type of elements of a groupoid, # is an operation symbol), which does not take it beyond the limits of the set.

A semigroup (semigroup) is a groupoid whose operation is associative ((a # b) # c == a # (b # c) for all a, b, and c).

A monoid is a semigroup with a neutral element (there exists an element 'e' such that a # e == e # a == a, for any a).

Set with operation	Groupoid	Semigroup	Monoid
Int and '+'	+	+	+
Int and '-'	+	-	-
Int and '*'	+	+	+
Int and '/'	-	-	-
String and '+'	+	+	+
String (without "") and '+'	+	+	-

Remarks

1. Int cannot be divided by 0, ArithmeticException - the result is not Int.
2. Addition and multiplication are associative, subtraction and division are not.
3. For the Int semigroup, the neutral element is '0'.
4. For the Int semigroup, by multiplication, the neutral element is '1'.
5. In the concatenated strings, the neutral element is the empty string ("").

Imagine a semigroup (or groupoid, in Scala, checking the associativity cannot be carried to the compilation stage anyway) in the form of a trait, which is parameterized by the type of the element and contains its operation as a method

 trait Semi[T] { def |+|(x: T, y: T): T } 

A semigroup is an invariant (exponential) functor.

 trait Semi[T] { self => def |+|(x: T, y: T): T def xmap[R](f: T => R, g: R => T): Semi[R] = new Semi[R] { override def |+|(x: R, y: R): R = f(self |+| (g(x), g(y))) } } 

Express the semigroup of strings by concatenation

 class SemiStr extends Semi[String]{ override def |+|(x: String, y: String): String = x + y } 

Consider the transition from a semigroup of strings by concatenation to a “semigroup of integers by concatenation

 object SemiDemo10 extends App { val f: String => Int = _.toInt val g: Int => String = _.toString val x: Semi[String] = new SemiStr val y: Semi[Int] = x xmap (f, g) println(y.|+|(100, 500)) } >> 100500 

We constructed a semigroup in integers (Semi [Int]) in which the binary operation is reduced to the concatenation of string representations of the number in the decimal number system (100 | + | 500 => "100" | + | "500" => "100500" => 100,500).

If the previous example is too banal, then look at the following

 object SemiDemo16 extends App { val f: String => Int = Integer.parseInt(_, 16) val g: Int => String = Integer.toHexString val x: Semi[String] = new SemiStr val y: Semi[Int] = x xmap (f, g) println(y.|+|(10, 10)) } >> 170 

We constructed a semigroup in integers (Semi [Int]) in which the binary operation reduces to the concatenation of string representations of a number in hexadecimal numbering system (10 | + | 10 => "A" | + | "A" => "AA" => 10 * 16 + 10 = 170). It can be verified that such an operation on Int is still associative (we ignore the case of int overflow and negative numbers, sorry).

In the Scalaz library, they also believe that a semigroup and a monoid are invariant functors .

 package scalaz object InvariantFunctor { /** Semigroup is an invariant functor. */ implicit val semigroupInvariantFunctor: InvariantFunctor[Semigroup] = new InvariantFunctor[Semigroup] {...} /** Monoid is an invariant functor. */ implicit val monoidInvariantFunctor: InvariantFunctor[Monoid] = new InvariantFunctor[Monoid] {...} ... } 

Invariant functor in libraries

The best way to learn Scala and FP is to read the source code of professionals on Scala and FP.

Scalaz is the most popular and mature of libraries that implement abstractions from category theory. In many ways, the design is taken from Haskell = scalaz . InvariantFunctor libraries

Cats is an attempt to re-implement categorical abstractions (which I did not like Scalaz - I do not know) = cats.functor.Invariant

Play JSON library includes an invariant functor , it is discussed here and here .