Relation between Arrow suspend functions and monad comprehension

Question

I am new to Arrow and try to establish my mental model of how its effects system works; in particular, how it leverages Kotlin's suspend system. My very vague understanding is as follows; if would be great if someone could confirm, clarify, or correct it:

Because Kotlin does not support higher-kinded types, implementing applicatives and monads as type classes is cumbersome. Instead, arrow derives its monad functionality (bind and return) for all of Arrow's monadic types from the continuation primitive offered by Kotlin's suspend mechanism. Ist this correct? In particular, short-circuiting behavior (e.g., for nullable or either) is somehow implemented as a delimited continuation. I did not quite get which particular feature of Kotlin's suspend machinery comes into play here.

If the above is broadly correct, I have two follow-up questions: How should I contain the scope of non-IO monadic operations? Take a simple object construction and validation example:

suspend fun mkMessage(msgType: String, appRef: String, pId: String): Message? = nullable {
    val type = MessageType.mkMessageType(msgType).bind()
    val ref = ApplRefe.mkAppRef((appRef)).bind()
    val id = Id.mkId(pId).bind()
    Message(type, ref, id)
}

In Haskell's do-notation, this would be

mkMessage :: String -> String -> String -> Maybe Message
mkMessage msgType appRef pId = do
    type <- mkMessageType msgType
    ref <- mkAppRef appRef
    id <- mkId pId
    return (Message type ref id)

In both cases, the function returns the monad type (a nullable value, resp. Maybe). However, while I can use the pure function in Haskell anywhere I see fit, the suspend function in Kotlin can only be called from within a suspend function. In this way, a simple, non-IO monad comprehension in Arrow behaves like an IO monad that must be threaded throughout my code base; I suppose this results because the suspend mechanism was designed for actual IO operations. What is the recommended way to implement non-IO monad comprehensions in Arrow without making all functions into suspend functions? Or is this actually the way to go?

Second: If in addition to non-IO monads (nullable, reader, etc.), I want to have IO - say, reading in a file and parsing it - how would i combine these two effects? Is it correct to say that there would be multiple suspend scopes corresponding to the different monads involved, and I would need to somehow nest these scopes, like I would stack monad transformers in Haskell?

The two questions above probably mean that I am still lacking a mental model that bridges between the continuation-based implementation atop the Kotlin's suspend mechanism with the generic monad-as-typeclass implementation in Haskell.

Jannjanna

Answer 1

schuster,

You're correct that Arrow uses the suspension feature from Kotlin to encode something like monad comphrensions.

To answer your first question:

Kotlin has suspend in the language (and Kotlin Std), by default suspend can only be called from other suspend code. However, the compiler also has a feature called RestrictsSuspension, this disallows for mixing suspend scopes and thus disallows the ablity to combine IO and Either for example. We expose a secondary DSL, either.eager which is encoded using RestrictsSuspension and it disallows calling foreign suspend functions.

This allows you to encode mkMessage :: String -> String -> String -> Maybe Message.

fun mkMessage(msgType: String, appRef: String, pId: String): Message? = nullable.eager {
    val type = MessageType.mkMessageType(msgType).bind()
    val ref = ApplRefe.mkAppRef((appRef)).bind()
    val id = Id.mkId(pId).bind()
    Message(type, ref, id)
}

To answer your second question: IO as a data type is not needed in Kotlin, since suspend can implement all IO operations in a referential transparent way like it works in Haskell. The compiler also makes a lot optimisations in the runtime, just like Haskell does for IO.

So the signature suspend fun example(): Either<Error, Value> is the equivalent of EitherT IO Error Value in Haskell. The IO operations are however not implemented in the Kotlin Std, but in a library KotlinX Coroutines, and Arrow Fx Coroutines also offers some data types and higher-level operations such as parTraverse defined on top of KotlinX Coroutines.

It's slightly different than in Haskell, since we can mix effects instead of stacking them with monad transformers. This means that we can call IO operations from within Either operations. This is due to special functionality, and optimisations the compiler can make in the suspension system. This blog explains how that optimisation works, and why it's so powerful. https://nomisrev.github.io/inline-and-suspend/

Here is also some more background on Continuations, and tagless encodings in Kotlin. https://nomisrev.github.io/continuation-monad-in-kotlin/

I hope that fully answers your question.

Daysidayspring

It seems that the path outlined above is now deprecated with the update to arrow-kt 1.1.2. When writing the above type of restricted bind, I now get the warning "'bind(): A' is deprecated. Deprecated in favor of Eager Effect DSL: EagerEffectScope". How should the above code be transformed to be compatible with future versions of arrow-kt? – Jannjanna

Hey @UlrichSchuster, The same principles as above still apply, but we changed some internals and the package. You should be able to simply find+replace the arrow.core.computations package to arrow.core.continuations and everything should still work and compile without any issues. – Daysidayspring

Answer 2

I don't think I can answer everything you asked, but I'll do my best for the parts that I do know how to answer.

What is the recommended way to implement non-IO monad comprehensions in Arrow without making all functions into suspend functions? Or is this actually the way to go?

you can use nullable.eager and either.eager respectively for pure code. Using nullable/either (without .eager) allows you to call suspend functions inside. Using eager means you can only call non-suspend functions. (not all effectual functions in kotlin are marked suspend)

Second: If in addition to non-IO monads (nullable, reader, etc.), I want to have IO - say, reading in a file and parsing it - how would i combine these two effects? Is it correct to say that there would be multiple suspend scopes corresponding to the different monads involved, and I would need to somehow nest these scopes, like I would stack monad transformers in Haskell?

You can use extension functions to emulate Reader. For example:

suspend fun <R> R.doSomething(i: Int): Either<Error, String> = TODO()

combines Reader + IO + Either. You can find a bigger example here from Simon, an Arrow maintainer.

Survive