Cats: Make IndexedStateT contravariant on SA

[dragisak]

Change from IndexedStateT[F[_], SA, SB, A] to IndexedStateT[F[_], -SA, SB, A]

Example of use:

trait Animal { def age: Int }
case class Cat(age: Int) extends Animal

val incrementCatAge: IndexedStateT[Id, Cat, Cat, Unit] = IndexedStateT.modify(cat => cat.copy(age = cat.age + 1))
val incrementAnimalAge: IndexedStateT[Id, Animal, Int, Unit] = IndexedStateT.modify(_.age + 1)

val composite = for {
  _ <- incrementCatAge
  _ <- incrementAnimalAge
  r <- IndexedStateT.get[Id, Int]
} yield r

[ceedubs]

I think that the fact that Cats currently has IndexedStateT wrap an F[SA => F[(SB, A)]] as opposed to just an SA => F[(SB, A)] means that you couldn't make this change without forcing F[_] to be covariant (F[+_]). I think that this forcing covariance on F would be an overly restrictive change.

Sorry I've been largely out of the loop for a while -- has there been research/discussion on whether the tailRecM work has provided an infrastructure that would allow us to change IndexedStateT back into just a SA => F[(SB, A)] while providing stack safety? I realize that this is probably a little late in the game to bring this discussion up... cc @johnynek

[johnynek]

I don't really know what F[SA => F[(SB, A)]] encoding has to do with stack safety except that I I guess we assume F[_] is stack safe (which is why we default to using Eval here?)

Note tailRecM is implemented and it does not depend on this encoding. So, it should be fine.

I am an advocate now of using tailRecM + encoding to Free when you have a monadic recursion that does not look like a simple loop (which is not that common in my experience). With Free, you have stack safety on all flatMaps, and you can lift any monad into free. Getting out is done via tailRecM, so it is safe.

As for this change, I'm not sure it is worth it at this late stage before 1.0. I am nervous about changing the encoding and breaking a lot of folks.

[LukaJCB]

I really don't have any deep insight into the issue, but speaking about breakage, I don't really see the issue. IndexedStateT has only been available since RC1 and the original StateT could stay exactly the same from an API stand point, no? I don't think a lot of people have picked up IndexedState in this short time period, so I can't imagine we'd be breaking a lot of folks :)

[johnynek]

StateT existed before and was a case class wrapper on F[S => F[(S, A)]]. Indexed broadened to F[SA => F[(SB, A)]] but for uses those SA == SB == S, so the code didn't need to change, but maybe some inference or parameters did.

Going from F[S => F[(S, A)]] to S => F[(S, A)] is potentially a larger change and especially since State may not be stack safe in all cases it used to be since it was Eval[S => Eval[(S, A)]] and all function calls were trampolined inside Eval. It is not clear what we break by doing this.

Changing this after RC1 seems pretty dubious to me given how important state is. Note it is pretty easy to roll your own state, so people can experiment and propose for cats 2 that we unwind this encoding, but I'm -1 on changing it now.

[kailuowang]

Removed the help wanted label for now until we reach a consensus on the solution.

[ceedubs]

@johnynek I agree with all of your points.

I think that we could have a discussion about potentially changing the representation of State within Cats for 2.0, but that it's not something that we want to change now and that we can't go through with the proposed change on this issue until/unless the other work happens first.

[ceedubs]

I'm going to go ahead and change this from "triage-needed" to "on-hold". We can't do this with the current formulation of IndexedStateT.

[non]

Just leaving a note here, it seems like IndexedStateT is already not stack-safe due to the use of andThen to compose functions. 😰

I was able to fix it by substituting Composed(f1, f2) for f1 andThen f2 (as per https://gist.github.com/non/0d3a9b05a4892afabe0749a0ab79fbcc).

Not sure if anyone has seen this in action? I noticed it based on the benchmarks here, which also make me think that having a State implementation that is not based on StateT might also be good.

[kailuowang]

I am intrigued by the idea of a Free based State in cats as well. Cc @iravid

[iravid]

👋

Nice! I was pretty annoyed by the getAndSet benchmark crashing here and was going to investigate later this week. Composed looks like a pretty cool solution - type-aligned list all the things ;)

Re a free structure based State - I think this would be really helpful. Unless someone beats me to it, I'm definitely going to work on a free indexed RWS (that can be special cased to RW/WS/RS etc.)