Yoneda and Coyoneda trick

11 minute read

A simple intuition for a complex topic

image-center — You don’t have to understand this

If you relatively new to functional programming but already at least somewhat familiar with higher order abstractions like Functors, Applicatives and Monads, you may find interesting to learn about Yoneda lemma. This is not something you will use in your day to day work, it’s just a relatively easy exercise that can help you better understand more complex abstractions, like Free structures. If you want to get into deep categorical explanation on this topic I highly recommend Bartosz Milewski’s “Understanding Yoneda”. In this article we will do something different — starting from practical use cases we will try to understand what is (Co)Yoneda, how it can be useful and how it can be implemented in scala.

Yoneda

Let’s start with a simple example. You have a List[Int] and you want to make some transformations on it:

def f(a: Int): String = ???
def g(a: String): Option[Int] = ???
def h(a: Option[Int]): List[String] = ???

(0 to 10000000).map(f).map(g).map(h)

The list will be traversed 10000000 times, one per each map, which is not really efficient. List is a Functor, so it must obey the fmap (g . f) = fmap g . fmap f law, which means that we can rewrite the expression with a single map passing a function composition of all transformations. Also, scala has Streams to lazily apply transformations on a sequence of values. But what if we had arbitrary Functor and not just List? Can we make an abstraction that can do that for us? Let’s call it LazyFunctor and think about an example of how we would use it:

val lazyOption: LazyFunctor[Option, Int] = toLazyFunctor(Some(42))
val transformed: LazyFunctor[Option, Int] = lazyOption.map(_ + 1).map(_ + 2) // silly example
// nothing is executed yet

// apply all transformations at once, yields Some(45)
val option: Option[Int] = fromLazyFunctor(transformed) 

The idea here is instead of actual function application our LazyFunctor will compose everything we pass to map and then execute all at once when we call fromLazyFunctor.

Let’s start with type class definition:

sealed trait LazyFunctor[F[_], A] {
  // takes a function and applies it to original value
  def transformation[B](f: A => B): F[B]

  // interace 'map' to be used as functor
  def map[B](f: A => B): LazyFunctor[F, B] = ???  
}

We have a trait taking two type parameters: F[_] is our type constructor and A is our value type. You can think about transformation as an “original map” of F, this is where we will “store” our composed functions. We also have map that should do the following:

Create an instance of new LazyFunctor
Redefine transformation of a new LazyFunctor to be a composition of provided function f

// lets also make it an abstrac class and add self type annotation
abstract class LazyFunctor[F[_], A] { self =>
  // function to be applied when we call "run"
  def transformation[B](f: A => B): F[B]

  // interace 'map' to be used as functor
  def map[B](f: A => B): LazyFunctor[F, B] = new LazyFunctor[F, B] {
    def transformation[C](g: B => C): F[C] = self.transformation(g compose f)
  } 
}

Here’s the clever trick — at the moment of calling map we know only the first function but we managed to create a composition with the function that will be passed to map in the future. This means that when we finish doing maps and we want to get our value back we need to actually call our transformation. It takes a function as an argument (remember, its almost like an F’s map), which will be the latest composed function in the chain. The obvious thing to do is to pass identity function. Lets add another function to do just that and call it run:

abstract class LazyFunctor[F[_], A] { self =>
  // should be implemented as a composition of transformations
  def transformation[B](f: A => B): F[B]
  
  // apply transformations and get our value back
  def run: F[A] = transformation(identity)
  
  // interace 'map' to be used as functor
  def map[B](f: A => B): LazyFunctor[F, B] = new LazyFunctor[F, B] {
    def transformation[C](g: B => C): F[C] = self.transformation(g compose f)
  } 
}

Now what’s left is to implement isomorphisms between F[A] and LazyFunctor[F, A] to be able to actually construct LazyFunctor and get the value back:

def toLazyFunctor[F[_], A](fa: F[A]): LazyFunctor[F, A] = ???

def fromLazyFunctor[F[_], A](lf: LazyFunctor[F, A]): F[A] = lf.run

Turns out we already have an implementation for fromLazyFunctor and that exactly run function.

Now, as for toLazyFunctor, we know that we need to create new instance of LazyFunctor and define transformation function for it. The thing is, transformation have to return F[B] and we don’t have a way of constructing this type. We can enforce F[_] to be a functor because we know that want to deal with functors. By doing that we could map over provided value fa with transformation function f (that again, will be provided later):

//                                   vvvvvvvvvvvvvvvvvvvvvv
def toLazyFunctor[F[_], A](fa: F[A])(implicit F: Functor[F]): LazyFunctor[F, A] = 
  new LazyFunctor[F, A] {
    override def transformation[B](f: (A) => B): F[B] = F.map(fa)(f)
  }

def fromLazyFunctor[F[_], A](lf: LazyFunctor[F, A]): F[A] = lf.run

That’s about it, just one more detail — our LazyFunctor as actually known as Yoneda, so lets do some renames and see how the whole program looks like:

import cats.Functor

abstract class Yoneda[F[_], A] { self =>
  def transformation[B](f: A => B): F[B]

  def run: F[A] = transformation(identity)

  def map[B](f: A => B): Yoneda[F, B] = new Yoneda[F, B] {
    def transformation[C](g: (B) => C): F[C] = self.transformation(g compose f)
  }
}

def toYoneda[F[_], A](fa: F[A])(implicit F: Functor[F]): Yoneda[F, A] =
  new Yoneda[F, A] {
    override def transformation[B](f: (A) => B): F[B] = F.map(fa)(f)
  }

def fromYoneda[F[_], A](lf: Yoneda[F, A]): F[A] = lf.run

// usage example:
import cats.implicits._
val lazyOption: Yoneda[Option, Int] = toYoneda(Option(42))
val transformedOption: Yoneda[Option, Int] = lazyOption.map(_ + 1).map(_ + 2).map(_ + 3) // silly example
// nothing is executed until next line
val option: Option[Int] = lazyOption.run // apply all transformations at once

This is important: in order to start working with Yoneda[F, A] we have to provide functor instance for F.

Coyoneda

Is it possible to do the same but without restrictions on F to be a Functor? Well, not really — we have original value in the context F[A], we can compose all given functions A => B but we still need to know how to apply all those functions over F[A]. Can we defer restrictions on F to be a Functor? Maybe it might be useful to pretend that F is a Functor, let user do maps and require a functor instance only at the point of getting the value back. Let’s think about usage example:

// our plain data structure
case class Person[A](a: A)

// lift Person value into theoretical 'PretendFunctor'
val personF: PretendFunctor[Person, Int] = toPretendFunctor(Person(42))
// Person is not a functor, but we can do maps
val personF2: PretendFunctor[Person, Int] = personF.map(_ + 1).map(_ + 2) // silly example
// nothing is executed yet

// we're done with transformations, now we need Person to be a Functor
val personFunctor = new Functor[Person] {
  override def map[A, B](fa: Person[A])(f: (A) => B): Person[B] = ???
}

// apply all transformations and get the value back
val person: Person[Int] = personF2.run(personFunctor) 

The use case is similar to LazyFunctor example, so we might think that PretendFunctor’s implementation is very similar. Lets first think about differences in the way we construct the values and getting the result back and then address the interface.

We know that Yoneda (our LazyFunctor) requires a Functor when we construct a value:

def toYoneda[F[_], A](fa: F[A])(implicit F: Functor[F]): Yoneda[F, A] = 
  new Yoneda[F, A] {
                                                     // vvvvvvvvvvvv
    override def transformation[B](f: (A) => B): F[B] = F.map(fa)(f)
  }

We don’t want to do that in our case, we want to defer that for later. In Yoneda we started the chain of function compositions by doing F.map and ended with identity. In PretendFunctor we will do the other way around — start from identity and end with F.map. It means that to construct PretendFunctor we need to provide two arguments — value in the context and a transformation function:

def toPretendFunctor[F[_], A, B](fa: F[A])(f: A => B) : PretendFunctor[F, B] =
  new PretendFunctor[F, B] {
    ???
  }

Now lets think about actual PretendFunctor implementation. There are at least two functions we need to have — map and run:

sealed trait PretendFunctor[F[_], A] {
  def map[B](f: A => B): PretendFunctor[F, B] = ???
  def run(f: Functor[F]) = ???
}

Lets start with run, should be straightforward:

sealed trait PretendFunctor[F[_], A] {
  def map[B](f: A => B): PretendFunctor[F, B] = ???
  //             missing these   vvvvvvvvvvvvvvv  vvvvvvvvvvvvv
  def run(f: Functor[F]) = f.map(underlyingValue)(transformation)
}

Ok, in order to call f.map we need to have both the value and the function which are passed to our toPretendFunctor function, so lets try to just save those arguments into trait’s fields:

sealed trait PretendFunctor[F[_], A] {
  //                   vvv hmm, F[A]? It should be F[something] and then yield A
  val underlyingValue: F[A]
  //                       v hmm, won't compile, don't have B
  val transformation: A => B

  def run(f: Functor[F]) = f.map(underlyingValue)(transformation)

  def map[B](f: A => B): PretendFunctor[F, B] = ???
}

def toPretendFunctor[F[_], A, B](fa: F[A])(f: A => B) : PretendFunctor[F, B] =
  new PretendFunctor[F, B] {
    //                    vv hmm, no, 'fa' is of type F[A] but it has to be F[B]
    val underlyingValue = fa
    val transformation = f
  }

Problem is that toPretendFunctor should return PretendFunctor[F, B] and we can’t just override with fa and f simple because of types mismatch. It looks like we need to store the underlying type of the value in context:

sealed trait PretendFunctor[F[_], A] {
  // should be specified
  type UnderlyingType

  val underlyingValue: F[UnderlyingType]

  // from underlying type to 'A'
  val transformation: UnderlyingType => A

  def run(f: Functor[F]) = f.map(underlyingValue)(transformation)

  def map[B](f: A => B): PretendFunctor[F, B] = ???
}

def toPretendFunctor[F[_], A, B](fa: F[A])(f: A => B) : PretendFunctor[F, B]  =
  new PretendFunctor[F, B] {
    // save original type
    type UnderlyingType = A
    val transformation = f
    val underlyingValue = fa
  }

Great, that should compile, the hard part is over. The only thing left is our map function. It should create new PretendFunctor having underlyingValue and composition of transformation and given function f. We actually have it already implemented by toPretendFunctor:

sealed trait PretendFunctor[F[_], A] {
  type UnderlyingType

  val underlyingValue: F[UnderlyingType]

  val transformation: UnderlyingType => A

  def run(f: Functor[F]) = f.map(underlyingValue)(transformation)

  def map[B](f: A => B): PretendFunctor[F, B] = 
    toPretendFunctor(underlyingValue)(transformation andThen f)
}

Nice! Everything compiles and should do the trick. As you may guessed, PretendFunctor is known as Coyoneda which is a dual counterpart to Yoneda. Lets go back to our original example, do some renames and see how the whole program looks like:

sealed trait Coyoneda[F[_], A] {
  type UnderlyingType

  val underlyingValue: F[UnderlyingType]

  val transformation: UnderlyingType => A

  def run(f: Functor[F]) = f.map(underlyingValue)(transformation)

  def map[B](f: A => B): Coyoneda[F, B] =
    toCoyoneda(underlyingValue)(transformation andThen f)
}

def toCoyoneda[F[_], A, B](fa: F[A])(f: A => B) : Coyoneda[F, B]  =
  new Coyoneda[F, B] {
    type UnderlyingType = A
    val transformation = f
    val underlyingValue = fa
}

// our simple data structure
case class Person[A](a: A)

val personCoyo0: Coyoneda[Person, Int] = toCoyoneda(Person(42))(identity)
val personCoyo1: Coyoneda[Person, Int] = personCoyo0.map(_ + 1).map(_ + 2).map(_ + 3) // silly example
// nothing is executed until next line

// lets define functor for Person
val personFunctor = new Functor[Person] {
  override def map[A, B](fa: Person[A])(f: (A) => B): Person[B] = Person(f(fa.a))
}

// and then pass it to Coyoneda
val person: Person[Int] = personCoyo1.run(personFunctor) // should yield Person(48)

We can go further and put toCoyoneda into Coyoneda companion object and rename it to lift, but you get the idea.

That’s it! We started from LazyFunctor (Yoneda) to fuse multiple maps into one, then we tried to overcome the restrictions on our data type to be a Functor by creating PretendFunctor (Coyoneda). Turns out, pretending to have a functor for any F is a really useful abstraction. You can “make” your plain data structure an Applicative or a Monad even if it’s not even a Functor. This trick is used in Free structures implementation, which is a very useful concept that can change the way we construct and compose and our programs. I hope this post was not too complicated because the ideas are not that complicated, its just the scala syntax that can bring some of the confusion. In contrast I want to end this article with code snippet of everything we have done so far implemented in Haskell — look how its easier to express our intentions and fit under 25 lines:

-- Yoneda --------------------------------------------------------------
newtype Yoneda f a = Yoneda { runYoneda :: forall b. ((a -> b) -> f b) } 

instance Functor (Yoneda f) where
  fmap f y = Yoneda (\ab -> runYoneda y (ab . f))
  
toYoneda :: Functor f => f a -> Yoneda f a
toYoneda fa = Yoneda (\f -> fmap f fa)

fromYoneda :: Yoneda f a -> f a
fromYoneda y = runYoneda y id

-- Coyoneda -----------------------------------------
data CoYoneda f a = forall b . CoYoneda (b -> a) (f b)

instance Functor (CoYoneda f) where
  fmap f (CoYoneda mp fb) = CoYoneda (f . mp) fb
  
toCoYoneda :: f a -> CoYoneda f a
toCoYoneda fa = CoYoneda id fa

fromCoYoneda :: Functor f => CoYoneda f a -> f a
fromCoYoneda (CoYoneda mp fb) = fmap mp fb

Share on

Twitter Facebook LinkedIn

Oleksii Avramenko

Yoneda and Coyoneda trick

A simple intuition for a complex topic

Yoneda

Coyoneda

Share on

You may also enjoy

The Evolution of a Scala Programmer

Switching from OOP to Functional Programming

Catamorphisms and F-Algebras

Free Monads Explained