implement a monad comprehension on a list in kotlin using a coroutine

Question

I wonder if it is possible to implement something similar to the do-notation of Haskell in Kotlin on Lists or List-Like structures with monadic properties.

Take following example:

fun <A, B> cartesianProduct(xs: List<A>, ys: List<B>): List<Pair<A, B>> =
  xs.flatMap { x -> ys.flatMap { y -> listOf(x to y) } }

It would be nice if I could write something like

suspend fun <A, B> cartesianProduct(xs: List<A>, ys: List<B>): List<Pair<A, B>> =
  list { 
    val x = xs.bind()
    val y = xs.bind()
    yield(x to y)
  }

Arrow-Kt defines similar comprehensions using coroutines for either, nullable, option and eval. I looked at the implementation and also its Effect documentation, but I have trouble to translate the concept to Lists. Is this even possible in kotlin?

Answer 1

It's not possible at the moment to implement monad comprehension for List, Flow, and other non-deterministic data structures that emit more than one value. The current implementation of continuations in Kotlin is single shot only. This means a continuation can resume a program with a single emitted value. Resuming the program more than once requires hijacking the continuation stack labels with reflection in order to replay their state in the second resumption. Additionally replaying a block in which a multishot data type is binding would replay all effects previous to the bind since the block has to emit again.

list {
  println("printed 3 times and not cool")
  val a = listOf(1, 2, 3).bind()
  a
}

The arrow-continuations library already includes a MultiShot delimited scope for reset/shift but it's currently internal since is not safe until Kotlin suspension or continuations provide the ability to multishot without replaying the current block. Alternatively we would need real for comprehensions or a similar structure to enforce binds happen before other code which would also solve the block replaying issue.

The Effect interface ultimately delegates to one of these scopes for its implementation. The current versions of Reset.suspended and Reset.restricted are single shot.