typelevel
Add `Lift{Value,Kind}`, `Ask#{mapK,liftTo}` and `Local#liftTo`
The motivation for this PR is the desire to add a LocalLogger to log4cats that can store log context in a cats.mtl.Local. log4cats loggers have a mapK method; supporting mapK on a LocalLogger requires being able to transform a Local[F, *] into a Local[G, *], which in turn requires the functionality exposed by ~~KindTransformer~~ LiftKind.
LiftKind (formerly KindTransformer) is originally (and currently) from otel4s, designed by me (so we don't need to worry about attributing it to otel4s as I am simply personally (re)licensing my own code/design to typelevel/cats-mtl here).
~~I don't know how to write laws/tests for either of these commits, and would greatly appreciate assistance doing so~~
@iRevive if/when this lands, we should replace org.typelevel.otel4s.KindTransformer in otel4s with a deprecated type alias that points at cats.mtl.KindTransformer. I cannot imagine any reason to explicitly reference its companion, so we shouldn't have to worry about adding a deprecated val for that.
also I will need to remember to make a PR to cats-effect adding an implicit method to create KindTransformer instances for Resource to Resource's companion
How does this relate to MonadPartialOrder?
https://github.com/typelevel/cats-mtl/blob/ef624597f7c29178e237dcd9f09101c3997e1a90/core/src/main/scala/cats/mtl/MonadPartialOrder.scala#L29
@armanbilge good question. MonadPartialOrder is certainly insufficient in that Monad is not a sufficient context bound in all cases (cats.effect.Resource for example requires MonadCancel†), and is also over-constraining for all but one of the implicits provided in the companion (only StateT requires Monad; most of the rest only require Functor, and Kleisli and identity have no context bounds at all). if Monad was sufficient in general, then simply adding limitedMapK and liftFunctionK to MonadPartialOrder might be an acceptable alternative to adding KindTransformer (even though it's over-constrained in many cases), but that's not the case.
... does that answer your question?
also, I'm happy to have KindTransformer directly extend F ~> G if desired, though I personally think it's clearer as is
† I was lazy in otel4s and used MonadCancelThrow just because it's easier to deal with, but Resource#mapK only requires MonadCancel
cc @rossabaker do you recall us discussing something related to Arman's question? I have a vague recollection of it, though it's been quite a long time
Yes, thanks, that's a very helpful answer!
and is also over-constraining for all but one of the implicits provided in the companion (only
StateTrequiresMonad; most of the rest only requireFunctorandKleisliand identity have no context bounds at all)
Can you explain more about this? Specifically this part:
Kleisliand identity have no context bounds at all
To clarify, do you mean lifting into Kleisli has no context bounds? Because to have a Monad[Kleisli[F, E, *]] you do need a Monad[F].
~~Eventually we can use the KindTransformer from cats-mtl in otel4s, right?~~
Nvm, you already answered my question 😅
~~@iRevive we may need to think about making an otel4s release with all the changes that don't require cats-effect 3.6 in order to adopt this change in a timely manner, and if we don't, we may end up causing users to deal with conflicts if/when this ends up in use (e.g. in log4cats)~~
edit: moot, ce 3.6 is out
This abstraction has certainly proven itself useful in otel4s, and again in this new case. Because cats-mtl is on the classpath everywhere now, it's important we get this right. I'm trying to scavenge for prior art.
- @milessabin shared shapeless-3's
FunctorK, also in cats-tagless. An earlier draft is closer, but still not the same. - Skunk has an
Exchange, which isF ~> F, which is a higher-kindedcats.Endo. But that type is just an argument tolimitedMapK, not the full abstraction. NeitherExchangenor a hypotheticalEndoKturn up much. - I have been unsuccessful in Hoogling for prior art in Haskell.
I wonder, since this is more general than monads, does it belong in mtl? Is it perhaps cats? Without laws, it would be banished to alleycats, which would not work for the places we want to use this.
I wonder, since this is more general than monads, does it belong in mtl? Is it perhaps cats?
I have no objection to it being in cats "proper".
Without laws, it would be banished to alleycats
I have no doubt that laws are writable, I just don't personally know how, and am also not the most versed in category theory to know what mathematical/logical/categorical laws there are.
shapeless-3's
FunctorK
If we were trying to FunctorK for LocalLogger[F[_]] (for example), would we be creating FunctorK[LocalLogger]? how would one derive that? I can't think of how to do it without the functionality provided by KindTransformer
This is allowed in our current lawlessness:
def silly[F[_], G[_]](f: F ~> G): KindTransformer[F, G] =
new KindTransformer[F, G] {
val liftK: F ~> G = f
def limitedMapK[A](ga: G[A])(f: F ~> F): G[A] = ga
}
How about this to relate the operations?
limitedMapK(liftK(fa))(f) <-> liftK(f(fa))
we should also relate limitedMapK and liftFunctionK based on the latter's default implementation (thus asserting that a given implementation is equivalent to the default):
limitedMapK(ga)(f) <-> liftFunctionK(f)(ga)
is there anything concrete we can say about individual methods? for example, we could test that the identity function does nothing, as follows:
limitedMapK(ga)(FunctionK.id) <-> ga
but idk if that's useful or meaningful. I don't think anything can be said of liftK without relating it to the other methods as it's essentially an arbitrary function
I have no objection to it being in cats "proper".
Some historical points why FunctorK didn't make the cut. I don't know how many of those apply here.
I have no doubt that laws are writable, I just don't personally know how, and am also not the most versed in category theory to know what mathematical/logical/categorical laws there are.
I'm just winging it too. This isn't an abstraction handed down on high by the abstract algebrists, this is one that scratches an itch. (Some are like that!)
If we were trying to
FunctorKforLocalLogger[F[_]](for example), would we be creatingFunctorK[LocalLogger]? how would one derive that? I can't think of how to do it without the functionality provided byKindTransformer
Yeah, I think FunctorK abstracts over things with a mapK, but it isn't enough to define one. For that, we need something like this, that unites liftK and mapK.
we should also relate limitedMapK and liftFunctionK based on the latter's default implementation
Agreed.
limitedMapK(ga)(FunctionK.id) <-> ga
I started thinking along these lines, and then I stopped because I thought it was implied by the other one, but I don't think it's quite the same. This seems like a good one.
what about laws for testing mapK on Ask and Local?
That's a fair question. Our existing mapK tests are geared toward data types, not for options that exist on a typeclass that hitherto didn't have mapK. If FunctorK were deemed useful, maybe it should sit beneath Ask!
is MonadPartialOrder a good/correct abstraction? would an abstraction over liftF/liftK that doesn't require both Monad[F] and Monad[G] be more reasonable?
I suppose that depends on the definition of "good".
-
It abstracts over enough to be useful to derive instances of multiple type classes.
-
Applicative[F]is enough for all use cases in this library, andApplicative[G]for all butStateful. Maybe that would be interesting for something likeNested, but I don't think it has ever come up. -
It's lawless, so mischievous implementations only reveal themselves when testing derived instances:
implicit def monadPartialOrderForOptionT[F[_]]( implicit F: Monad[F]): MonadPartialOrder[F, OptionT[F, *]] = new MonadPartialOrder[F, OptionT[F, *]] { val monadF = F val monadG = OptionT.catsDataMonadForOptionT[F] def apply[A](fa: F[A]) = OptionT.none /* yikes */ }Put another way, nothing currently enforces what's in the header comment about "the lifting distributes".
perhaps a different question would be better: why is it important that a single typeclass be able to derive things, and not for example having methods require both a (theoretical) LiftK and Applicative?
An implicit F ~> G doesn't make a lot of sense to me unless it expresses a relationship to other operations (for MonadPartialOrder, the Monad; for KindTransformer, the limitedMapK).
A microlib would lower the stakes of getting it right in cats-mtl, unless cats-mtl depends on that microlib anyway. And otel4s will only continue to get more important, and needs this functionality.
The closest prior art I've found to KindTransformer Haskell is Inject. The hmap is like mapK. The inject is like liftK, except the F remains in the signature. Frustratingly, it doesn't seem to enforce any lawful relationship between the two as we've tried to do here!
unless cats-mtl depends on that microlib anyway
it would not; just otel4s (and log4cats) would, probably
@rossabaker I think we've been thinking about this all wrong, and should consider it from an entirely different angle.
the purpose of KindTransformer is to enable the transformation of an arbitrary type parameterised by F[_] into being parameterised by G[_], without requiring any other value or object that converts between F and G (though it does not aim to be the only context bound—a MonadCancelThrow[G] for example might still be required). for this reason, I'm no longer confident that it necessarily belongs in cats-mtl.
we should consider what transformations KindTransformer currently enables, and what types might need additional capabilities to be transformed from being parameterised by F to G. #liftK enables transforming methods with no inputs in F but an output in F into having their output in G. limitedMapK/liftFunctionK enables transforming methods with a single input in F of an arbitrary type A and an output of F[A] into having a single input and output of G[A] instead (i.e. scoping/context change).
what types cannot be transformed by the current capabilities of KindTransformer? is there an existing type, or can we at least contrive a type?
I think a better description/name for limitedMapK and liftFunctionK is "lift scope"
btw @rossabaker, having laws that assert consistency does not prevent you from writing degenerate instances. for example:
new KindTransformer[F, OptionT[F, *]] {
val liftK: F ~> OptionT[F, *] = new (F ~> OptionT[F, *]) {
def apply[A](fa: F[A]): OptionT[F, A] = OptionT.none
}
def limitedMapK[A](ga: OptionT[F, A])(f: F ~> F): OptionT[F, A] = OptionT.none
}
@djspiewak this design developed (again?) organically in otel4s due to need. could you elaborate on what the issues with this design were that prompted #209?
some more exploration of the design can be found in the PR linked in the immediately previous comment
@NthPortal Sorry for the delay! Essay incoming… (with the caveat that it's been a while since I really thought about this so some details may be erroneous or misleading or just really poorly explained)
Monad transformers are born out of an attempt to solve the "vertical" effect composition problem (flatMap is horizontal). You're trying to take multiple types of effects (such as as maybe optionality and an error channel) and smash them together such that you can have computations which have access to all of those capabilities within a uniform side-channel. This is a very sane thing to want to do, and in fact basically everyone wants to do it.
However, trying to actually do this very quickly runs into some thorny issues. One classical issue that actually causes a vast number of problems is the fact that most effects are not commutative. For example, Option[Either[E, A]] is not the same thing as Either[E, Option[A]]. So you can't just "smash together" the optionality effect and the error side channel effect and call it a day; you need to keep things carefully in the right order and don't get them confused. Btw, Either also has this problem composing with Either, and even Option has this problem composing with Option, so really very few things are truly commutative.
As you scratch further, loads more problems start to appear. A classic "obvious" solution to effect composition materializes from the Traverse typeclass, which seems to give a way of defining a pretty general flavor of flatMap which cuts across multiple monads simultaneously. It even seems to follow our general intuitions about how effects should compose, which is that there are some effects which need to be more base layer (like IO) while others can be layered above that (like Ior). However, as Haskell's famously broken ListT shows, Traverse is actually (and surprisingly) quite unsound with respect to effect composition in general. There are loads of effects on which this seems to work just fine, but you very quickly realize that the results don't actually hold water, and you can even violate very basic things like the functor laws. (as ListT does)
Implicit in all of the above btw is a deceptively alluring notion: the idea that there's some composed effect type FG[A] which is really just the smashing of two other standalone effect types F[A] and G[A]. This is very intuitive, and it passes the sniff test really directly when we think about Option vs OptionT, and then everyone's favorite "not OptionT but actually secretly really the same as OptionT", which is to say EitherT. There's really very little difference between OptionT[F, A] and F[Option[A]], just some syntactic sugar, so it feels so tantalizing to say that this is the true meaning of christmas!
And then we have Kleisli, which is really inconveniently defined by R => F[A]. Except it's not, and it's actually F[R => F[A]], which is even more confusing and subtle. Or the surprisingly similar StateT, which is S => F[(S, A)], and now all sorts of things are starting to fall apart. And let's not forget about StreamT (actually, on second thought, let's absolutely please forget about StreamT), FreeT, and ContT, all of which are really very complex (especially that last one) and not obviously representable in terms of these base effect type deconstructions. Or at the very least, the base effect types are very different than the composed thing.
And this brings us to the real problem: monad transformers are really general. They do more than just mash two effects together, they allow us to do arbitrary datatype ish things provided that the result obeys the monad laws and can implement a higher-order pure (i.e. liftK) and sometimes map (i.e. mapK). That is a wildly unrestricted interface, and the transformers which exist today in the wild take advantage of this in ways which are really implicit and really subtle and very seldom understood. ContT is arguably something that should be entirely unexpressible if our goal is just to smash two effects together vertically, and yet here it is, very much expressed. FreeT is really more like a fixed point data type than a monad transformer, but it obeys the general contract of "eehhhhhhhhh… something something monad laws and FunctorK so it must be a duck", so here we are.
Hopefully you're getting the theme here.
Where the rubber tends to meet the road on all of this in practice is one of two areas: either auto-derivation of mashed thing from constituent thing (for a failed exploration of this, see https://github.com/djspiewak/emm), or auto-deconstruction of mashed thing back to constituent thing. The former is Traverse (and also arguably Eff and a few other attempts), while the latter is MonadControlLayer. But since the FG[A] == F[G[A]] thing is actually far more restrictive than what monad transformers are, both of these are really doomed to failure.
Now, that doesn't mean we can't do anything at all. I've name-dropped FunctorK, and obviously that's in the mix somewhere sort of by definition: we said earlier that a monad transformer is a monad, is defined in terms of some base type constructor, and also should implement a higher-order pure (and usually also map). The last of those criteria is FunctorK (well, really ApplicativeK), the first is Monad, and the middle one is sparkling FunctorK. This line of reasoning is what leads us to Hoist, and then subsequently to MonadPartialOrder.
MPO is really neat because it basically gives us a way to sort of talk about how OptionT[IO, A] contains an IO without having to figure out how to talk about decomposing the latter into the former (since as noted, this isn't possible in general). This gives us a little bit of power (which we use in Cats MTL to reduce boilerplate) and a few laws, but not too much more than that. It is, to the best of my knowledge, the furthest anyone has been able to go, soundly, in this direction.
It's not clear to me whether or not KindTransformer has unsound implications. The (F ~> F) => (G ~> G) thing does make me a little nervous, since it implies you have the contravariant transformation (G ~> F) somewhere in your back pocket, which is where all these things generally start to become unraveled. My fear is that this is secretly why the laws don't work for StateT, but I didn't look at it closely and I don't know whether that's actually true.
I would highly, highly recommend playing around with stacks involving FreeT. It's also advisable to look at ContT, but FreeT alone will get you most of the madness. If you want to have a really ~~good time~~ horribly awful time, you can look at IterateeT and StreamT.
At the end of the day, I think monad transformers themselves are kind of a failed experiment (they solve a much more general problem than anyone really asked for), so I'd like us to move in the direction of hiding them as much as possible, rather than building more machinery which bows to them. But with that said, as you've noted, this was motivated by a practical need in otel4s. Perhaps I should dig into that practical use-case a bit more before I pass judgment.
Also, I do want to be clear that I'm not saying that KindTransformer is definitely unsound! Not in the slightest. This stuff is incredibly subtle and surprising. Saying that "no one has been able to do better than Oleg on finding a strong abstraction" is a direct appeal to authority, and I think that's a pretty terrible reason to dismiss something. However, I do think it's worth keeping in mind that there are very, very, very subtle dragons here that have swallowed many people completely whole (how do you think such a wildly unsound ListT ended up in Haskell in the first place?).
@djspiewak I'm going to organise this reply by addressing shorter and/or simpler points first.
for continuity, what was previously called KindTransformer is now called LiftKind. LiftValue is a subset of LiftKind's capabilities and a generalisation of the functionality of LiftIO.
I did a thorough exploration of possible typeclass hierarchies over at https://codeberg.org/cuddle_puddle/lifts/pulls/1.
Kleisli, which is really inconveniently defined byR => F[A]. Except it's not, and it's actuallyF[R => F[A]]
I think you must be mixing it up with something else, as Kleisli has precisely the first definition you give.
I do want to be clear that I'm not saying that
KindTransformeris definitely unsound!
LiftKind has a number of laws that I think show its soundness, and they are now in this PR as well as my exploration.
The
(F ~> F) => (G ~> G)thing does make me a little nervous, since it implies you have the contravariant transformation (G ~> F) somewhere in your back pocket
neither LiftKind nor LiftValue provide a transformation G ~> F, and I don't personally see the implication. to me, LiftValue only implies G ~> F specifically for the immediate result of lifting a value, in that it must be guaranteed to be unliftable to be lawful. that guarantee is the basis of Unlift and some of the laws.
I've name-dropped
FunctorK
FunctorK doesn't work well as an abstraction as it assumes (incorrectly!) that the mapK operation has no context bounds. Resource from cats-effect is a counterexample in wide use for which a typeclass with mapK functionality would be very helpful.
MapK and LiftScope in my exploration expose the same (or a limited version of that) capability while still supporting context bounds.
You're trying to take multiple types of effects (such as as maybe optionality and an error channel) and smash them together such that you can have computations which have access to all of those capabilities within a uniform side-channel.
A classic "obvious" solution to effect composition materializes from the
Traversetypeclass, which seems to give a way of defining a pretty general flavor offlatMapwhich cuts across multiple monads simultaneously.
LiftKind actually does not attempt to do what you describe, and I don't think comparing it to Traverse is useful or meaningful. if you want access to the capabilities of any particular effect that was composed using LiftKind, you will need to manually decompose it. LiftValue allows you to "wrap" or "box" a type, and LiftKind extends those capabilities to keep track of how to perform certain transformations (specifically scoping operations) on the underlying "wrapped" or "boxed" type.
one of the key use cases of LiftKind is to be able to use telemetry and observability types uniformly across HttpApp[F] and HttpRoutes[F] from http4s, which de-alias to Http[F, F] and Http[OptionT[F, *], F] respectively. we'd like to be able to perform tracing and logging in HttpRoutes even though it doesn't necessarily have behaviour or a response for every possible request—hence the OptionT when it is de-aliased. LiftKind allows us to to lift a tracer into OptionT and still perform scoping operations with it (such as creating spans). if F happens to be an EitherT, it doesn't give us access to that in any way.
MPO is really neat because it basically gives us a way to sort of talk about how
OptionT[IO, A]contains anIOwithout having to figure out how to talk about decomposing the latter into the former (since as noted, this isn't possible in general).
for reference, this is the same as the functionality LiftValue has, except LiftValue doesn't require two Monad instances.
and a few laws
there may be laws that apply to it, but there are no laws/tests for MonadPartialOrder in cats-mtl.
This gives us a little bit of power (which we use in Cats MTL to reduce boilerplate)
while MonadPartialOrder is sufficient to derive instances for (for example) Ask, it is not necessary, which leads me my more general point: I do not like MonadPartialOrder.
I hate MonadPartialOrder's name. 'partial order' is already a term with a meaning—and a typeclass in cats no less—and MonadPartialOrder does not relate to that meaning. to the extent that it might relate to the meaning of 'partial order', it only has two monads, and a set of two elements is either fully ordered or entirely unordered (and it would be vacuous to call it partially ordered). but the relationship between the two monads isn't even one of ordering, but one of derivability—you can derive one from the other.
much more significantly than the name though, I think MonadPartialOrder is a bad abstraction, and I will again use Ask as an example. MonadPartialOrder[F, G] has 3 parts: Monad[F], Monad[G], and F ~> G. for comparison, LiftValue is just F ~> G. in order to derive Ask[G, ?] from Ask[F, ?], you need F ~> G and Applicative[G]. MonadPartialOrder[F, G] requires an extraneous Monad[F] and FlatMap[G](ish) that the Ask[G, ?] doesn't need. even if you argue that Monad[F] is implicit in the existence of Monad[G], there's still unnecessary FlatMap capability. I opine that only the bare necessities for deriving Ask[G, ?] from Ask[F, ?] should be required—LiftValue[F, G] and Applicative[G].
oops, I missed a point I had intended to address.
My fear is that this is secretly why the laws don't work for
StateT
the reason StateT is not lawful is because StateT[F, S, A] is F[S => F[(S, A)]]; in other words, because of the double wrapping in F. this makes StateT#mapK unlawful for use in any abstraction over the operation mapK
one way or another, some version of this code will continue to exist either in otel4s or some dependency of otel4s. I (and probably others) think it belongs here, so I would like to reach a consensus. there are definite downsides to making it a microlib, though that's always an option as well