IndexedStateT has superfluous parts

[ekmett]

Digging into the definition of IndexedStateT we find

F[(SA) ⇒ F[(SB, A)]]

but that outer F isn't motivated by anything in the underlying theory.

(SA) ⇒ F[(SB, A)]

is actual indexed state. The extra outer F[_] seems to have slipped in as a sort of Cayley-like construction, but it goes conspicuously unused, and if you attempt to use it to say slip another layer of F effects in during the glue-up of your computation, you'll violate laws left and right for non-commutative choices of F[_]. The inner F is motivated by the fact that you can distribute the (SA) => out of any F[] using strength, and (SB,) in using strength.

Is there any documentation motivating/justifying this extra outer effect layer?

[danicheg]

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.

[johnynek]

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.

[ekmett]

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.

[johnynek]

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.