melvic-ybanez/what-i-didnt-know-about-fp-2021.md

## what-i-didnt-know-about-fp-2021.md

      
    Raw
  

              what-i-didnt-know-about-fp-2021.md
            
          
    Previous List: What I Didn't Know about Functional Programming until 2020
What I Didn't Know about Functional Programming until 2021


A hom-functor is usually implemented in Scala as the reader functor. The type itself is essentially a hom-set, but if we fix the domain to a particular type, we get a functor:
// A hom-set Hom(A, X)
type Reader[A, X] = A => X

// A hom-functor X => Hom(String, X) or Hom(String, -)
type HomStringTo[X] = Reader[String, X]
To implement the reader functor instance, we need to fix the domain at the instance-level and let fmap supply the codomain:
implicit def readerFunctor[A]: Functor[Reader[A, *]] = new Functor[Reader[A, *]] {
  def fmap[X, B](fa: Reader[A, X])(f: X => B): Reader[A, B] =
    f compose fa
}
Since we fixed the domain, our functor was covariant because the type parameter it takes was in the positive position.
If we fix the second type parameter of Reader, we can implement it as an instance of the contravariant functor, because the second parameter is in the negative position:
implicit def readerContra[X]: Contravariant[Reader[*, X]] = new Contravariant[Reader[*, X]] {
  def contramap[A, B](fa: Reader[A, X])(f: B => A): Reader[B, X] =
    fa compose f
}


If we vary both type parameters of Reader, we get a profunctor. After all, Reader is contravariant in the first type parameter and covariant in the second. The implementation for the dimap is just a series of function composition:
implicit val readerProF: Profunctor[Reader] = new Profunctor[Reader] {
  def dimap[A, B, C, D](fa: Reader[A, B])(f: C => A)(g: B => D): Reader[C, D] =
    g compose fa compose f
}


For any category C and any object a in C, the set of natural transformations from a hom-functor C(a, -) to any functor F: C -> Set is isomorphic to F(a). This is known as the Yoneda Lemma:
Nat[Hom(a, -), F] <=> F(a)

// alternatively...
[C, Set](C(a, -), F) <=> F(a)

This means given any point in F(a), we can derive a natural transformation; and for any natural transformation alpha: Hom(a, -) -> F, we can apply it to the morphism id(a) and pick any element from F(a).
To show this, we can start by picking two objects x and y in C, with the morphism f: x -> y and the hom-set Hom(a, x). We can get a morphism a -> y via f compose h where h is an element of Hom(a, x). In terms of hom-sets, we write that composition as C(a, f). So, if we have a natural transformation alpha with components x and y, our naturality square will have the following equation and it's point-wise form:
alpha(y) compose C(a, f) = F(f) compose alpha(x)
= alpha(y)(C(a, f)(h)) = F(f)(alpha(x)(h))      // point-wise form
= alpha(y)(f compose h) = F(f)(alpha(x)(h))       

Now, if we set x = a, we can choose id(a) from C(a, a) as h, and reduce the equation:
alpha(y)(f compose id) = F(f)(alpha(a)(id(a)))
= alpha(y)(f) = F(f)(alpha(a)(id(a)))

We managed to make alpha work with any random y and f in the naturality square.


By virtue of the Yoneda Lemma, the functions alpha and fa below are isomorphic:
trait Yoneda[F[_], A] {
  def F: Functor[F]

  def alpha[B](hom: A => B): F[B]

  def fa: F[A]
}
where alpha is the natural transfromation Nat[Hom(a, -), F]. Note how F above is a covariant functor. This is because while a is in negative position in Hom(a, -), it's also in negative position in alpha. That's double negation, making a's position positive.


Because of duality, we also get Coyoneda for free. It simply fixes the codomain of the hom-functor:
Nat[Hom(-, a), F] <=> F(a)

F in this case has to be a contravariant functor, because a is negative position (positive in the hom-functor times negative in the natural transformation itself, making it negative as a result).


The set of natural transformations between hom-functors C(a, -) and C(b, -) for any category C, under the Yoneda Lemma, gives us the Yoneda Embedding:
// Substitute C(b, -) for F in the general statement
[C, Set](C(a, -), C(b, -)) <=> C(b, a)
It's as if b -> a in C is embedded in [C, Set], though the positions of a and b are swapped. This results to contravariant functors for the mappings a -> C(a, -) and b -> C(b, -).


Catamorphisms generalize fold operations on any functor. It maps an F-Algebra and a fixed-point of a functor to the type the functor is acting on. To implement catamorphism, let us first define an algebra that collapses an embellished value, removing the attached context, and a higher-kinded type Term that maps a type constructor to its fixed-point:
type Algebra[F[_], A] = F[A] => A

/**
 * Y-combinator at the type-level
 */
final case class Term[F[_]](out: F[Term[F]])

object Term {
  // Helper function to make function composition more convenient later on
  def out[F[_]]: Term[F] => F[Term[F]] = _.out
}
We can then define catamorphism (usually named cata) in terms of those two:
def cata[F[_], A](f: Algebra[F, A])(implicit F: Functor[F]): Term[F] => A =
  Term.out andThen F.fmap(cata(f)) andThen f
cata performs a leaf-to-root traversal, applying the algebra to the nodes of the recursive data structure. Etymologically, the Greek origin of the prefix "cata" means "collapse" or "destruction" (e.g "catastrophe" or "cataclysm").


An anamorphism is the dual of catamorphism; it acts on the same objects but the arrows are reversed:
type Coalgebra[F[_], A] = A => F[A]

object Term {
  def in[F[_]]: F[Term[F]] => Term[F] = Term.apply[F]
  
  // ... previous code here
}

def ana[F[_], A](f: Coalgebra[F, A])(implicit F: Functor[F]): A => Term[F] =
  Term.in compose F.fmap(ana(f)) compose f
We defined Coalgebra as the dual of Algebra, and Term.in as an alias for Term.apply. The definition of ana differs from that of cata in the order of composition: cata uses left-to-right composition with andThen while ana uses right-to-left composition with compose. The other difference is the use of Term.in instead of Term.out.
The prefix "ana" also comes from the Greek word which means "building".