Yoneda and Coyoneda trick

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:

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:

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:

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:

1. Create an instance of new LazyFunctor
2. Redefine transformation of a new LazyFunctor to be a composition of provided function 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:

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:

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):

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:

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:

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:

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:

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

Lets start with run, should be straightforward:

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:

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:

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:

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:

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:

GLHF