enable EitherEffect or other computation blocks within traverse

[i-walker]

The following approach can be extended to any other algebra, datatype or parTraverse.
In 0.13.2 we define traverseEither:

inline fun <E, A, B> Iterable<A>.traverseEither(f: (A) -> Either<E, B>): Either<E, List<B>> {
  val acc = mutableListOf<B>()
  forEach { a ->
    when (val res = f(a)) {
      is Right -> acc.add(res.value)
      is Left -> return@traverseEither res
    }
  }
  return acc.right()
}

consider this example:

// imagine this model, where users have a limited amount of keywords associated with their profile
data class User(val id: Int, val savedKeywords: List<String>)

// and an Error hierarchy
sealed class Error
data class UserNotFound(val user: User): Error()
data class KeyWordNotSaved(keyword: String): Error()

//  and API calls to 3rd party micro services

suspend fun getUserFromId(id: Int): Either<UserNotFound,User> = TODO()
    
suspend fun saveKeywords(keywords: List<String>): Either<KeyWordNotSaved, Unit> = TODO()

// now we would like to extend the functionality to multiple User Id's
```kotlin
suspend fun saveAllKeywords(ids: List<Int>): Either<Error, Unit> =
    either {
        ids.map { id: Int ->
            saveKeywords(
                getUserFromId(id).bind().savedKeywords
            ).bind()
        }
    }

but either.invoke + map is traverseEither - with the difference that we want to have more than just one computational binding.
This is an alternative, which allows users to use EitherEffect as they traverse

suspend inline fun <E, A, B> Iterable<A>.traverseEither(crossinline f: suspend EitherEffect<E, *>.(A) -> B): Either<E, List<B>> =
    either {
        val acc = mutableListOf<B>()
        forEach { a -> acc.add(f(this, a)) }
        acc
    }

and our example above is achieved with:

suspend fun List<Int>.saveAllKeywordsWithTraverse(): Either<Error, List<Unit>> =
    traverseEither { id: Int ->
        saveKeywords(
            getUserFromId(id).bind().savedKeywords
        ).bind()
    }

One may note that the definition of traverseEither is using the shift and reset functionality only for the end result. Making it a special case of what delimited continuations provides.

The question to the community is wether we should adopt this in Validated, Either and other places where bind is used e.g.: nullable.
Please leave any Feedback :)

[nomisRev]

Hey @i-walker,

Great suggestion, this is something that was considered when working on these new signatures but there are some trade-offs.

inline fun <E, A, B> Iterable<A>.traverseEither(crossinline f: EitherEffect<E, *>.(A) -> B): Either<E, List<B>> =
VS
inline fun <E, A, B> Iterable<A>.traverseEither(crossinline f: (A) -> Either<E, B>): Either<E, List<B>> =

In the first signature, the one you proposed, it's no longer possible to pass fun process(id: Int): Either<Error, User> but you're now forced to manually call it and bind to it.

listOf(1, 2).traverseEither { id -> process(id).bind() } compared to currently listOf(1, 2).traverseEither(::process).

Given that either scopes can be installed at any level the current signatuers was chosen, it causes another level of identation though unless you split it off to a seperate function.

suspend fun saveAllKeywordsForId(id: Int): Either<Error, Unit> =
    either {
          val keys = getUserFromId(id).bind().savedKeywords
          saveKeywords(keys).bind()
    }

suspend fun List<Int>.saveAllKeywordsWithTraverse(): Either<Error, List<Unit>> =
  traverseEither(::saveAllKeywords)

So the same syntax can easily be achieved by splitting off in a seperate context aware function.
So by promoting this pattern we still allow all patterns whilst not having to bloat the Arrow library with multiple variants of each function.

With multiple receivers this could potentially improve even further since a user might be able to do:

context(EitherEffect<Error, *>)
suspend fun List<Int>.saveAllKeywordsWithTraverse(): List<Unit> =
  map {
     val keys = getUserFromId(id).bind().savedKeywords
      saveKeywords(keys).bind()
  }

[i-walker]

Thanks for pointing out the trade-offs @nomisRev :D
From what I understand in the current context-receiver proposal with multiple receivers the following function

context(EitherEffect<Error, *>)
suspend fun List<Int>.saveAllKeywordsWithTraverse(): List<Unit> =
  map {
     val keys = getUserFromId(id).bind().savedKeywords
      saveKeywords(keys).bind()
  }

type checks to

(context(EitherEffect<Error, *>) -> List<Int>) -> List<Unit> // or something similar IIRC

so we would have to deal with similar issues.
Unless there is a compiler integration, which can do automatic conversions, if that context is never used.

[nomisRev]

This is solved by mapOrAccumulate in 2.x.x branch, will get back-ported to 1.2.x

[kyay10]

mapOrAccumulate now exists! Also, a general Accumulate API is being worked on.