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.