## Thursday, December 7, 2017

### Covariant and Contravariant Functors in Scala

Scala is a first class functional programming and object-oriented language which supports among other concepts, higher-kind types, functors and monads.
This post illustrates the capability of Scala to leverage the concepts of covariant and contravariant functors for tensor analysis with application to vector fields

Note: This post requires a solid knowledge of functional programming as well understanding of differential geometry.

Overview
Most of Scala developers have some experience with the core tenets of functional programming: monads, functors and applicatives. Those concepts are not specific to Scala or even functional programming at large. There are elements of a field in Mathematics known as topology or algebraic topology. Differential geometry or differential topology makes heavy use of tensors that leverage covariant and contravariant functors.

This post introduces the concepts of
• Contravariant functors applied to co-vectors and differential forms
• Projection of higher kind

Vector fields 101
Let's consider a 3 dimension Euclidean space with basis vector {ei} and a vector field V (f1, f2, f3) [Note: we follow Einstein tensor indices convention]

The vector field at the point P(x,y,z) as the tuple (f1(x,y,z), f2(x,y,z), f3(x,y,z)).
The vector over a field of k dimension field can be formally. mathematically defined as
$f: \boldsymbol{x} \,\, \epsilon \,\,\, \mathbb{R}^{k} \mapsto \mathbb{R} \\ f(\mathbf{x})=\sum_{i=1}^{n}{f^{i}}(\mathbf{x}).\mathbf{e}^{i}$ Example: $f(x,y,z) = 2x+z^{3}\boldsymbol{\mathbf{\overrightarrow{i}}} + xy+e^{-y}-z^{2}\boldsymbol{\mathbf{\overrightarrow{j}}} + \frac{x^{3}}{y}\boldsymbol{\mathbf{\overrightarrow{k}}}$
Now, let's consider the same vector V with a second reference (origin O' and basis vector e'i

$f(\mathbf{x})=\sum_{i=1}^{n}{f'_{i}}(\mathbf{x}).\mathbf{e'}_{i}$
The transformation matrix Sij convert the coordinates value functions fi and f'i. The tuple f =(fi) or more accurately defined as (fi) is the co-vector field for the vector field V
$S_{ij}: \begin{Vmatrix} f^{1} \\ f^{2} \\ f^{3} \end{Vmatrix} \mapsto \begin{Vmatrix} f'^{1} \\ f'^{2} \\ f'^{3} \end{Vmatrix}$
The scalar product of the co-vector f' and vector v(f) defined as is defined as
$< f',v> = \sum f'_{i}.f^{i}$
Given the scalar product we can define the co-vector field f' as a linear map
$\alpha (v) = < f',v> (1)$

Covariant functors
I assume the reader has basic understanding of Functor and Monads. Here is short overview:

A category C is composed of object x and morphism f defined as
$C= \{ {x_{i}, f \in C | f: x_{i} \mapsto x_{j}} \}$ A functor F is a map between two categories C and D that preserves the mapping.
$x\in C \Rightarrow F(x)\in D \\ x, y\in C \,\,\, F: x \mapsto y => F(x)\mapsto F(y)$
Let's look at the definition of a functor in Scala with the "preserving" mapping method, map

 1 2 3 trait Functor[M[_]] { def map[U, V](m: M[U])(f: U => V): M[V] } 

Let's define the functor for a vector (or tensor) field. A vector field is defined as a sequence or list of fields (i.e. values or function values).

type VField[U] = List[U]

trait VField_Ftor extends Functor[VField] {
override def map[U, V](vu: VField[U])(f: U => V): VField[V] = vu.map(f)
}


This particular implementation relies on the fact that List is a category with its own functor. The next step is to define the implicit class conversion VField[U] => Functor[VField[U]] so the map method is automatically invoked for each VField instance.

implicit class vField2Functor[U](vu: VField[U])
extends VField_Ftor {

final def map[V](f: U => V): VField[V] =
super.map(vu)(f)
}


By default Covariant Functors (which preserve mapping) are known simply as Functors. Let's look at the case of Covector fields.

Contravariant functors
A Contravariant functor is a map between two categories that reverses the mapping of morphisms.
$x, y\in C \,\,\, F: x \mapsto y => F(y)\mapsto F(x)$

trait CoFunctor[M[_]] {
def map[U, V](m: M[U])(f: V => U): M[V]
}


The map method of the Cofunctor implements the relation M[V->U] => M[U]->M[V]
Let's implement a co-vector field using a contravariant functor. The definition (1) describes a linear map between a vector V over a field X to the scalar product V*: V => T.
A morphism on the category V* consists of a morphism of V => T or V => _ where V is a vector field and T or _ is a scalar function value.

type CoField[V, T] = Function1[V, T]


The co-vector field type, CoField is parameterized on the vector field type V which is a input or function parameter. Therefore the functor has to be contravariant.

The higher kind type M[_] takes a single type as parameter (i.e. M[V]) but a co-vector field requires two types:
• V: Vector field
• T: The scalar function is that the result of the inner product <.>

Fortunately the contravariant functor CoField_Ftor associated with the co-vector needs to be parameterized only with the vector field V. The solution is to pre-defined (or 'fix') the scalar type T using a higher kind projector for the type L[V] => CoField[V, T]
T => ({type L[X] = CoField[X,T]})#L

trait CoField_Ftor[T]
extends CoFunctor[({type L[X] = CoField[X,T]})#L ] {

override def map[U,V](
vu: CoField[U,T]
)(f: V => U): CoField[V,T] =
(v: V) => vu(f(v))
}


As you can see the morphism over the type V on the category CoField is defined as f: V => U instead of f: U => V. A kind parameterized on the return type (Function1) would require the 'default' (covariant) functor. Once again, we define an implicit class to convert a co-vector field, of type CoField to its functor, CoField2Ftor

implicit class CoField2Ftor[U,T](vu: CoField[U,T])
extends CoField_Ftor[T] {

final def map[V](f: V => U): CoField[V,T] =
super.map(vu)(f)
}


Evaluation
Let's consider a field of function values FuncD of two dimension: v(x,y) = f1(x,y).i + f2(x,y.j. The Vector field VField is defined as a list of two function values.

type DVector = Array[Double]
type FuncD = Function1[DVector, Double]
type VFieldD = VField[FuncD]


The vector is computed by assigning a vector field to a specific point (P(1.5, 2.0). The functor is applied to the vector field, vField to generate a new vector field vField2

val f1: FuncD = new FuncD((x: DVector) => x(0)*x(1))
val f2: FuncD = new FuncD((x: DVector) => -2.0*x(1)*x(1))

val vfield: VFieldD = List[FuncD](f1, f2)
val value: DVector = Array[Double](1.5, 2.0)
val vField2: VFieldD = vfield.map( _*(4.0))


A co-vector field, coField is computed as the sum of the fields (function values) (lines 1, 2). Next, we compute the product of co-vector field and vector field (scalar field product) (line 6). We simply apply the co-vector Cofield (linear map) to the vector field. Once defined, the morphism _morphism is used to generate a new co-vector field coField2 through the contravariant function CoField2Functor.map(line 10).
Finally a newProduction is generated by composing the original covariant field Cofield and the linear map coField2 (line 12).

  1 2 3 4 5 6 7 8 9 10 11 12 val coField: CoField[VFieldD, FuncD] = (vf: VFieldD) => vf(0) + vf(1) val contraFtor: CoField2Functor[VFieldD, FuncD] = coField val product = coField(vField) val _morphism: VFieldD => VFieldD = (vf: VFieldD) => vf.map( _*(3.0)) val coField2 = contraFtor.map( _morphism ) val newProduct: FuncD = coField2(coField) 

Environment
Scala 2.11.8
JDK 1.8

References
• Tensor Analysis on Manifolds - R. Bishop, S. Goldberg - Dover publication 1980
• Differential Geometric Structures - W. Poor - Dover publications 2007
• Functors and Natural Transformationsv- A. Tarlecki - Category Theory 2014