I was reading source for `State` and saw this: ``...

# arrow

[julian]

I was reading source for State and saw this:

fun <S, T, P1, R> State<S, T>.map(sx: State<S, P1>, f: (T, P1) -> R): State<S, R> =
  flatMap(IdBimonad) { t -> sx.map { x -> f(t, x) } }.fix()

What is IdBimonad doing?
(I read the docs available for BiMonad, but I'm still mystified.)

[julian]

Oh, I think it's providing the monad to

fun <B> flatMap(MF: Monad<F>, fas: (A) -> StateTOf<S, F, B>): StateT<S, F, B>

[julian]

And I think a Bimonad is a combination comonad and monad typeclass for data types that can have both, like Id.
Is that about right?

[Imran/Malic]

Bi-something usually indicates that there are two type parameters with a given container F , regardless of F's nature. Here is an example from Cats with Tuples and Either - the concept is the same https://typelevel.org/cats/typeclasses/bifunctor.html

[Imran/Malic]

Referring to the BIO hype it would mean that the IO data type has in addition to it’s inhibited/ return type A also an (Domain-)Error E .

[Imran/Malic]

When I was wondering what IdBimonad is doing this helped me a lot.

arrow.typeclasses.internal.IdBimonad

/**
 * Alias that represents a computation that has a dependency on [D].
 */
typealias ReaderFun<D, A> = (D) -> A

/**
 * Alias ReaderHK for [ReaderTHK]
 *
 * @see ReaderTHK
 */
typealias ForReader = ForReaderT

/**
 * Alias ReaderKind for [ReaderTKind]
 *
 * @see ReaderTKind
 */
typealias ReaderOf<D, A> = ReaderTOf<ForId, D, A>

/**
 * Alias to partially apply type parameter [D] to [Reader].
 *
 * @see ReaderTKindPartial
 */
typealias ReaderPartialOf<D> = ReaderTPartialOf<ForId, D>

/**
 * [Reader] represents a computation that has a dependency on [D].
 * `Reader<D, A>` is an alias for `ReaderT<ForId, D, A>` and `Kleisli<ForId, D, A>`.
 *
 * @param D the dependency or environment we depend on.
 * @param A resulting type of the computation.
 * @see ReaderT
 */
typealias Reader<D, A> = ReaderT<ForId, D, A>

/**
 * Constructor for [Reader].
 *
 * @param run the dependency dependent computation.
 */
fun <D, A> Reader(run: ReaderFun<D, A>): Reader<D, A> = ReaderT(run.andThen { Id(it) })

/**
 * Syntax for constructing a [Reader]
 *
 * @receiver [ReaderFun] a function that represents computation dependent on type [D].
 */
fun <D, A> (ReaderFun<D, A>).reader(): Reader<D, A> = Reader().lift(this)

/**
 * Alias for [Kleisli.run]
 *
 * @param d dependency to runId the computation.
 */
fun <D, A> Reader<D, A>.runId(d: D): A = this.run(d).value()

/**
 * Map the result of the computation [A] to [B] given a function [f].
 *
 * @param f the function to apply.
 */
fun <D, A, B> Reader<D, A>.map(f: (A) -> B): Reader<D, B> = map(IdBimonad, f)

/**
 * FlatMap the result of the computation [A] to another [Reader] for the same dependency [D] and flatten the structure.
 *
 * @param f the function to apply.
 */
fun <D, A, B> Reader<D, A>.flatMap(f: (A) -> Reader<D, B>): Reader<D, B> = flatMap(IdBimonad, f)

/**
 * Apply a function `(A) -> B` that operates within the context of [Reader].
 *
 * @param ff function that maps [A] to [B] within the [Reader] context.
 */
fun <D, A, B> Reader<D, A>.ap(ff: ReaderOf<D, (A) -> B>): Reader<D, B> = ap(IdBimonad, ff)

/**
 * Zip with another [Reader].
 *
 * @param o other [Reader] to zip with.
 */
fun <D, A, B> Reader<D, A>.zip(o: Reader<D, B>): Reader<D, Tuple2<A, B>> = zip(IdBimonad, o)

/**
 * Compose with another [Reader] that has a dependency on the output of the computation.
 *
 * @param o other [Reader] to compose with.
 */
fun <D, A, C> Reader<D, A>.andThen(o: Reader<A, C>): Reader<D, C> = andThen(IdBimonad, o)

/**
 * Map the result of the computation [A] to [B] given a function [f].
 * Alias for [map]
 *
 * @param f the function to apply.
 * @see map
 */
fun <D, A, B> Reader<D, A>.andThen(f: (A) -> B): Reader<D, B> = map(f)

/**
 * Set the result to [B] after running the computation.
 */
fun <D, A, B> Reader<D, A>.andThen(b: B): Reader<D, B> = map { _ -> b }

fun Reader(): ReaderApi = ReaderApi

object ReaderApi {

  fun <D, A> just(x: A): Reader<D, A> = ReaderT.just(IdBimonad, x)

  fun <D> ask(): Reader<D, D> = ReaderT.ask(IdBimonad)

  fun <D, A> lift(run: ReaderFun<D, A>): Reader<D, A> = ReaderT(run.andThen { Id(it) })
}

Now this is old arrow code, and with the new implementations with the Suspension API’s and extension Functions, there is no need to use Reader, Kleisli or State for idiomatic Kotlin. Especially, because State is insufficient for effectful programs.

[Imran/Malic]

Sorry for that rant, hope that helped 😅

[Jannis]

The intuition that a Bimonad is Comonad + Monad is correct. And yes State<S, A> = StateT<S, ForId, A> which is to say that State is the StateT monad transformer without any further effects (because Id has no effects). Since StateT = (S) -> Kind<F, (S, A)> that means State = (S) -> Id<(S, A)> and equally State = (S) -> (S, A) because Id does nothing

[Jannis]

I don't actually know why we use a bimonad there since we only really need a monad but it works either way

[Imran/Malic]

We had to use it somewhere I guess😂

[Imran/Malic]

@Jannis are we using Bimonad in MTL more or is that something we could potentially drop to the incubator, because it is still in core

[Jannis]

The IdBimonad specifically is only used internally for its monad instance so it may drop the unnecessary methods from comonad but that does not matter imo. Bimonad itself is a typeclass right? And as such it is user api and should be kept.

[Imran/Malic]

I am not for removing it, I only thought it would make sense to move it to MTL. But it also has other use-cases 🙂

[julian]

Thanks @Imran/Malic, @Jannis!

@Imran/Malic The Reader code you quoted was promising. But being unable to go into the implementations being called was limiting. For example, here I want to see what the map being called is doing:
fun <D, A, B> Reader<D, A>.map(f: (A) -> B): Reader<D, B> = map(IdBimonad, f)

[Jannis]

Reader<D, A> is defined as ReaderT<D, ForId, A>. ReaderT<D, F, A> = (D) -> Kind<F, A> so Reader<D, A> = (D) -> Id<A> ~ (D) -> A.
map in this case works like so:
fun <D, F, A, B> ReaderT<D, F, A>.map(f: (A) -> B): ReaderT<D, F, B> = ReaderT { d -> this.runReaderT(d).flatMap { a -> f(a).runReaderT(d) } }
fun <D, F, A> ReaderT<D, F, A>.runReaderT(d: D): Kind<F, A>
The actual implementation does a bit more to get the monad instance involved etc. I skipped that because that doesn't change any semantics.

[Jannis]

In short: ReaderT is all about implicitly passing a parameter through by wrapping a partially applied function

[Jannis]

That is also why so many people use it for DI in the haskell world.
However in kotlin this is not as useful because we have receiver functions and receiver scopes which can do DI a lot cleaner (and without the stacksafety hassle that the ReaderT implementation has to go through... ReaderT is only stacksafe if F is stacksafe. So it is fine for IO or Eval but not for Id)

[Jannis]

Oh btw @Imran/Malic the issue linked may not apply to our State because it is actually implemented a little different from the cats version, we also verify flatMap/ap consistency with laws.

[Jannis]

regardless I would still not advice the use of those transformers because they are terribly inefficient and not intuitive outside of haskell imo

[Imran/Malic]

@julian there is an mtl module here if you want to check it out, but the aforementioned reasons among many others are why we have removed it from core and actively disincentivizing folks to use it in Kotlin.

[julian]

@Jannis What do you mean about Id not being stacksafe?

[Jannis]

Id(1).flatMap { x -> Id(x).flatMap { ... } }
Each flatMap here is one level of stack depth and there is no trampolining like IO does to avoid stackoverflows. This means sometime after around 128 min nested flatMap calls it may crash.
To avoid this we offer tailrecM on all monads which is supposed to flatMap in a tailrecursive manner and thus does not allocate stack frames recursively.
Some monads like IO/Eval are also stacksafe because their runners themselves "trampoline" to avoid overflows, this is usually done by reifying the remaining computation on the heap, ending the runloop and resuming the loop with the computation on the heap which no starts at 0 stackframes again.
Our new suspend based IO is also stacksafe for similar reasons iirc

[julian]

Btw, what sent me down this track was doing the exercises in the chapter on State in the book "FP in Kotlin" by Marco Vermeulen aka @ marc0der. So not a real-life usage. But good to know for the future that I should avoid using State and Reader .

[Jannis]

Imo understanding how those work may be beneficial to understanding how monads work in general. The reason they aren't great is entirely kotlin and the jvm's fault:
• In kotlin we have to take care of stacksafety through trampolining and excessive use of AndThen which will slow down programs, now that usually is no issue because when are our programs ever cpu bound but it still aint great
• Also type inference isn't great and without access to typeclasses we won't ever have a nice way of actually writing code with State/Reader
There are other non-lang specific reasons against State (Reader is perfectly fine except the two things mentioned).
Either way reader is better modeled with DI over function receivers and state for local state should just go mutable for now. For state that is accessed concurrently stm or other concurrency primitives should be used and we might add some state related stuff over suspend later if that idea I have works out 🙈

[Jannis]

btw state and reader with id are "mostly" stacksafe, nested flatMaps may fail but almost everything else should be stacksafe 🙈

[julian]

Thanks @Jannis. This is very illuminating. Interesting you mentioned AndThen because I was looking at the source for that yesterday, and it came to mind when you mentioned trampolining.

[julian]

It looked like it took some measure to merge instances to help with stack safety.

[Jannis]

AndThen is the prime example of how reifying to the heap and running in a loop can get you stacksafety 😄

[Jannis]

It even uses some dirty tricks to achieve stacksafe flatMap for functions which was really important when making Reader and State as stacksafe as possible

[julian]

Either way reader is better modeled with DI over function receivers...

I adopted the recommended approach of typeclassless DI using receivers and I love it. I'm soooo done with Dagger!