Yoneda and Coyoneda trick
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 thefmap (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 Stream
s 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:
- Create an instance of new
LazyFunctor
- Redefine
transformation
of a newLazyFunctor
to be a composition of provided functionf
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 map
s 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