Cats: Monads for nested

[ShahOdin]

For a certain catagory of monads, we can have a monad for their composition.

implicit def catsDataMonadForNested1[F[_]: Monad: Distributive, G[_]: Monad]: Monad[Nested[F, G, *]] =
    new StackSafeMonad[Nested[F, G, *]] {
      override def flatMap[A, B](fa: Nested[F, G, A])(f: A => Nested[F, G, B]): Nested[F, G, B] = Nested(
        fa.value.flatMap { x =>
          Monad[F].map(Distributive[F].distribute(x)(f.andThen(_.value)))(_.flatten)
        }
      )
      override def pure[A](x: A): Nested[F, G, A] = cats.data.Nested.catsDataApplicativeForNested[F, G].pure(x)
    }

and

implicit def catsDataMonadForNested2[F[_]: Monad, G[_]: Monad: Traverse]: Monad[Nested[F, G, *]] = new StackSafeMonad[Nested[F, G, *]]{
    override def flatMap[A, B](fa: Nested[F, G, A])(f: A => Nested[F, G, B]): Nested[F, G, B] = Nested(
      fa.value.flatMap{
        Traverse[G].flatTraverse(_)(f.andThen(_.value))
      }
    )
    override def pure[A](x: A): Nested[F, G, A] = cats.data.Nested.catsDataApplicativeForNested[F, G].pure(x)
  }

Being able to compose those class of monads "for free" is quite useful. What do people think about providing this composition for Nested? We could of course provide the said requirements on F & G through separate intermediary types and use those instead of Nested.

Fyi, This came up in my attempt at implementing Parallel instances for nested structures. but obviously it allows us to do flatmaps on nested structures so it's quite useful for cases that are not easily addressed for simple EitherT or OptionTs.

[LukaJCB]

Related: https://github.com/typelevel/cats/pull/1478

[LukaJCB]

The problem is that the resulting monads might not actually be lawful and we generally don't want unlawful instances

[djspiewak]

Not guaranteed to be a lawful Monad or even a lawful Applicative, and also not guaranteed to be stack-safe (so shouldn't be using the StackSafeMonad mixin). Basically the only thing you can really guarantee is that such a composition forms a lawful Functor, but this is trivial and thus probably not useful.

[ShahOdin]

Thanks! ah I see. well that's a shame. :) It doesn't look like the other implementation has been looked at in that PR. I'd be curious to know if the other one would violate the exact same set of laws or a different set.

[djspiewak]

Thanks! ah I see. well that's a shame. :) It doesn't look like the other implementation has been looked at in that PR. I'd be curious to know if the other one would violate the exact same set of laws or a different set.

I suspect it would have the same problem.

Ultimately, what this comes down to is the fact that effect sequencing is a fundamentally non-general problem. Some random examples:

• State
• Cont
• List
• Either

Each of these effects has a different strategy for composing over other effects. Monad transformers as a mechanism allow this to be handled because each transformer is fundamentally tied to the specific type layer under composition. More general mechanisms such as this one attempt to compose arbitrary F[_] and G[_] effects in a uniform way, which results in some interesting pathologies.

Some prior art:

• Eff. Note that Eff is really not too much more complex than Data types a la carte. This technique has had a bit of a rebranded resurgence recently in the form of ZIO's "effect rotation", which is really the same thing except hard-coded. All of these techniques are fundamentally doing the same thing: tossing a bunch of effects into a Free Coproduct and the interpreting them away in an interleaved fashion. They all work, but often in unintuitive ways. The canonical example of this is composing State over Either, but Cont and List are also good counter-examples (since they cannot be done in this kind of framework). Formally speaking, it only works for algebraic monads, which are a subset of monads, and even for algebraic monads the composition has properties which are not necessarily uniform with the intuitive nesting (e.g. State changes from Left effects end up being visible, whereas a nested encoding would have short-circuited the state transformations).
• Free + EitherK + InjectK is a primitive ad hoc encoding of Eff, derived directly from Swierstra's paper.
• Emm This was basically a type-level metaprogrammatic encoding of what you're doing here, and as the link in the readme illustrates, it doesn't work lawfully. It also doesn't work at all for effects in the kleisli category (such as State), but even working around that you still end up in trouble.