Just caught up with the thread of `traverseEither`...

# arrow

[Daniel Berg]

Just caught up with the thread of traverseEither on Nel. The behavior of traverseEither on Iterable was also different than what I expected. It walks the sequence from back to front and also f is evaluated on all elements even if a Left value is found.

[Daniel Berg]

We have an alternative implementation. Something like:

fun <E, A, B> traverse(xs: List<A>, f: (A) -> Either<E, B>): Either<List<B>> {
    val z: Either<E, <List<B>> = listOf<B>().right()
    return xs.fold(z) { acc, a ->
        acc.flatMap { ys -> f(a).map { ys + it } }
    }
}

[Daniel Berg]

I don't know if that goes against the theory behind it but in our case we have an expensive f that we don't executed if a Left value is found.

[Jannis]

Yeah, I was looking into this afterwards as well:
https://github.com/arrow-kt/arrow/pull/2365
Should fix all traverse related issues

[Daniel Berg]

Oh nice, you also added a mutable list. We have only a few elements in our use case but just browsing the current impl it looks O(N^2) to me.

[Jannis]

Iteration isn't actually a huge problem (tho less is obv better), but the junk created when using List.plus is insane, it throws away a lot of object arrays and just hurts the gc times. I first noticed this when benchmarking queues in arrow STM...
The current impl should be O(2*N) as in reverse followed by fold which are both N (I hope). Some people also ignore the constant factor but I think that depends on what you are analyzing and here they do matter.

[Daniel Berg]

Also good to see the stack safe checks!