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?

score 10 · Accepted Answer · answered Apr 14 '21 at 08:18

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.

thanks for this really great explanation! What do you mean with "real for comprehensions"? Can you point out some hints I could look up? — Chris, Apr 14 '21 at 15:59
Hi Chris, real `for comprehensions` as if it were in a lang like Scala or if Kotlin for loops would be expressions instead of statements. As a language construct, they enforce bindings are executed in order. In the Kotlin continuation model and in a model with continuations like Loom monad bind can be implemented as a function instead of requiring a language construct in the form of a "for" style comprehension that frequently the compiler rewrites to flatMap, map or similar. — Raúl Raja Martínez, Apr 28 '21 at 22:53

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

1 Answers1