IndexedStateT has superfluous parts about cats HOT 4 OPEN

Shortly speaking, it's all about trampolining.

A bit more details:
I've done some archaeology, and found the initial PR that introduced StateT as F[S => F[(S, A)]]. After many years of development, it transformed into IndexedStateT having the F[(SA) ⇒ F[(SB, A)]] signature. That PR has some reasoning about this outer effect.

State wraps F[S => F[(S, A)]] instead of the more familiar S => F[(S, A)]. This allows for effective trampolining.

Also, you might want to dig into the original issue where there was quite a detailed discussion on that outer effect.

It's better to have veterans answer this, but I may guess there wasn't an objective to have aligned implementation with the theory. In that sense, in cats could be found many other occurrences.

from cats.

I think it was 100% to improve stack safety.

The outer F[_] is always the same as pure in our constructions I think. We do test the laws, but of course it's possible we've missed something.

For our State monad instance we use this except with F = Eval which is a somewhat optimized implementation of a free monad.

from cats.

The main issue I have is that while it is probably sound to use it for trampolining, any other effects in that outer F will be applied rather out of order, and you don't really have any laws locking you out of doing such at present, no? Would it make sense to introduce a base trampolining monad to use in that place instead rather than force everything through the entire underlying monad stack twice without using any of the other parts? e.g. error handling, etc.

from cats.

I think the first step might be to construct a law or test we think should pass and doesn't. From that concrete example we might have more ideas.

We are under a few constraints:

1. due to the way the scala/jvm ecosystem works, generally we compose classpaths from large sets of transitive dependencies, often which are not on a single version of cats. So, this is why we highly value not breaking binary compatibility: so when you use libraries that already depend on cats together they tend to work. Thus, we can add laws to our testing or laws package somewhat easily, but we can't easily change type signatures since they often invalidate the binary compatibility.
2. we are very interested in actually using the code, so the practical issue of stack safety it very important to us. Long ago, before various stack safety tricks had been found, using functional patterns on the JVM often resulted in stack overflow errors.

If we were unconstrained by 1. we could make the constructor for the class private, so users could never observe the outer F[_].

That said, I'm not sure how it being there harms anything.

As to your point:

Would it make sense to introduce a base trampolining monad to use in that place instead rather than force everything through the entire underlying monad stack twice without using any of the other parts?

We definitely could have done another direct encoding I think, by using a Free structure here and running an interpreter on that in the end, but at this time point 2 from above will be an issue: that will almost certainly break binary compatibility now.

I think withing our constraints (binary compatibility, stack safety and then performance, mostly in that order), we are open to making improvements.

from cats.