Relationship between Yoneda and Codensity?

Hi, all.

Due to a lack of mathematical background, I am often confused and overwhelmed by a constant stream of terminology while learning Haskell .
So there may be various low-level errors in the description of the question .

I happened to come across the terminology “yoneda style”, while learning the
“GHC.Data.Stream” module.

So I Collected some information on it.
And then I found out that it seemed very similar to Codensity for monad .

``````Yoneda for functor:
newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b }
newtype Codensity m a = Codensity { runCodensity :: forall b. (a -> m b) -> m b }
``````

They both seem to be doing the same thing:

Storing the action, and Composing ,then doing operation Lazily

.
But various information indicates that there is not much connection between them.
So why ?

2 Likes

You should probably have a read of Ed Kmett’s three-part series Free Monads for Less (Part 2, Part 3).

5 Likes

Thanks a lot . I’ll go to read right now .
But before that, Could you please briefly explain their differences ?

Is there anything wrong or correct in my understanding:

``````They both seem to be doing the same thing:

> Storing the action, and Composing ,then doing operation **Lazily**
``````

They both store a function that can accept a callback and wrap the result of that callback in an effect. The difference is that `Yoneda` can only accept effect-free callbacks, and `Codensity` can accept effectful callbacks. That’s a meaningful difference; it means that you can always make a `Monad` out of a `Codensity`, for example, by using the `Codensity`'s function to join effects, but the same is not true of `Yoneda`.

3 Likes

Can they be seen as realizing the same idea.
Can I consider yoneda as codensity-like on Functor ,while codensity as yoneda-like on Monad .

If you find that helpful. It’s a bit like considering multiplication and exponentiation as the same idea, because you can define them both by iterating another arithmetic operation. And sometimes that intuition will be helpful, and sometimes it will obscure important differences. If you try to collapse your understanding to simply the way in which they are similar, you will miss out on what makes them significant individually.

2 Likes

OK, I see.
I will try to find more examples to understand each of them.
Thanks.

You might find these talk slides helpful — the presenter draws parallels between `DList`, `Yoneda`, and `Codensity` in a way that might make sense to you.

Unfortunately, I’m not aware of a recording.

1 Like

OK, I’ll learn that.

Just for context, this sort of thing is at the advanced end of Haskell, so it definitely isn’t a topic you need to understand to be a competent programmer in the language. (Although of course it’s very interesting)

2 Likes

Not just the advanced end, but one of many advanced ends that are not relevant even for deep experts of other subdomains of Haskell.

But by all means, pursue your interests! Some of us just feel we need to point this out because there’s this idea you need to know advanced category theory to do Haskell programming, when it’s often something that just gets in the way

3 Likes

That actually is Confusing things:
What content can a person know well to be considered a competent Haskeller ?
(Excluding Free monad, Freer, Extensible effect ?
Just until Monad transformer, mtl ? )

Thankyou. I know what you mean.
But When learning Haskell, I always feel like I’m floating on the surface and not down-to-earth. So much so that I don’t have the confidence to start a slightly formal project.

1 Like

If your goal is to write software that serves a purpose, the best thing you can do is start the project and get feedback from users. If you can write an interactive console application using product and sum types, you probably already know enough! Everything else is best learned through concrete experience.

If your goal is to learn advanced topics, well, that’s a different story.

For what it’s worth, I consider myself a competent Haskeller, and here are some areas of knowledge I have that I think contribute to that feeling. Note that knowledge in almost all of these domains is best gained through the school of hard knocks.

• build tools (one of: stack, cabal)
• language extensions: which ones are safe and easy, which ones are more scary (starting point: GHC2021)
• how haskell libraries can depend on system libraries (generally C libraries like libz), and how to handle that.
• how to look things up (all of: Hoogle, Cabal user guide, GHC user guide)
• how to manage Haskell dependencies (one of: stack, cabal lock files, Nix)
• use of hlint and a code formatter (one of: ormolu, fourmolu, stylish-haskell)
• functional programming style: use of functions for abstraction, encapsulation, generalization
• use of product and sum types: modeling the domain, choosing the right level of explicitness, using newtypes
• test libraries and test strategies
• choosing Haskell dependencies: bog-standard choices or the ones I have a personal preference towards
• use of standard library abstractions: Functor, Applicative, Monad, Foldable, Traversable, IO, ReaderT, (not) StateT
• exception handling, particularly so-called asynchronous exceptions (though I am shaky here)
• profiling (see Haskell Optimization Handbook)

Deep areas that I may never learn about:

• Yoneda-level category theory
• Type-checking theory
• GC optimization

Special mention of things I have managed to avoid learning so far, but some people enjoy or need, and i’ll probably learn when my personal thunk gets forced:

• use of streaming libraries (streamly, conduit, pipes)
• use of lens or other optics libraries
• use of effects libraries
10 Likes

Thank you for providing so many details.
These guidelines are very important and meaningful for newcomers like me.

2 Likes

I recently read Grokking Simplicity, and if its becoming with functional programming that you’re interested in I would definitely recommend it. Haskell has a lot of different bells and whistles that aren’t commonly seen in other languages, and it can be very tempting to focus on them, but at the end of the day they are ultimately implementation details. If you’re just getting started and want to actually make “things”, I’d encourage focussing on the bigger things FP can bring to the table. You might find yourself thinking “eh, these are easy” - they often seem that way but when you really work with some of the basics you’ll find they can take years to truly master!

3 Likes

The book seems to be more focused on practicality,which does make it easier for newcomers to start.

@chreekat’s answer was great, so I won’t add too much, but the main things I think you should know to feel comfortable with Haskell include:

• comfort with type based debugging: e.g. resolving type errors quickly
• having a sense of how to write anything you could write in an imperative language in a functional way. (For example, I remember struggling to understand how one would write interactive apps when I was learning.)
• being familiar with standard libraries: (if useful, I put together a few resources here How to use libraries - The Haskell Guide, including (see the links in the left column), Gabriella Gonzalez’ invaluable overview of the ecosystem). Getting comfortable learning how to use a library quickly, by just reading the types and documentation on Hackage is a really useful skill.
• working with functors, monads and applicatives: do-notation, mtl, combinators like `sequence`
5 Likes

The importance of the libraries, the ecosystem cannot be overstated.

Thank you for your hard work in getting the wonderful collection .

My advice as mathematician and category theorist: Stare at the types of Yoneda and Codensity for a while. Maybe in two years when you are solving some concrete programming problem in Haskell, you will go: “Ah, I’ve developed this solution, but its type signature tells me it is really a Codensity monad that I’m using”. This information may not be directly helpful in that moment, but could make you smile.

What you should keep in mind about types that are isomorphic to another type, like `Yoneda`: They may have different performance characteristics. In a nutshell, function composition is very cheap in functional languages. I heard that is one reason why the language Elm was successful in the telecommunications industry. Ideally, performance advantages is something some smart library author has thought about for you, and you notice only when your project pulls in the kan-extensions package as a transitive dependency.

3 Likes