Hello. I have a sequence of Option<T>. How do I get the first non-None item or None if there i...

# arrow

[melatonina]

Hello. I have a sequence of Option<T>. How do I get the first non-None item or None if there is none? I can do that by mapping the Option<T> to T?, working with the nullable and remapping it to Option<T> at the end, of course. What is the Λrrow idiom for this operation?

[simon.vergauwen]

There is an interface called Traverse, which you can use to flip containers. G<F<A>> to F<G<A>> in your case Sequence<Option<A>> to Option<Sequence<A>> this is a quite common pattern which we can abstract over with Traverse.

https://arrow-kt.io/docs/arrow/typeclasses/traverse/

It’s also defined directly on SequenceK.
https://arrow-kt.io/docs/apidocs/arrow-core-data/arrow.core/-sequence-k/

Which you can use with Option.applicative() and ::identity or traverse(Option.applicative()) { it }

[simon.vergauwen]

This will however traverse the whole sequence instead of stopping at the first non-null or None.

It sounds like you just want firstOrNull but for Option? What is the reason for using Option here?

[melatonina]

I was actually reading this post about traverse https://www.47deg.com/blog/traverse-typeclass-in-arrow/ and I thought "This is related to my problem but not quite what I'm looking for" 😄.

[simon.vergauwen]

It’s a very powerful operator since it allows you to work with List or simple collections and turn it into powerful programs.

val getAllUsers: IO<List<User>> = listOf(1, 2, 3).k().map { getUserById(id) }.sequence(IO.applicative())

[melatonina]

Exacly, I'm looking for something like firstOrNull for Option. The reason for using Option is that I may replace it in future with Either to provide a reason for the failure. It's not something I need now. I can work with a nullable or I can implement my own firstOrNull for Option by passing via nullable, and continue my work. I just wanted to exploit this occasion to learn more Λrrow,

[simon.vergauwen]

That makes sense, traverse for Sequence will return all results or the failure.

[melatonina]

Ok. I'll implement a firstOrNone for Sequence<Option<T>> then. Thanks!

[simon.vergauwen]

Perhaps we can implement a firstOrDefault in traverse, I don’t think null would make sense there if you were using Either instead of Option for the nested type.

[melatonina]

You are right: when switching to Either<L, T>, a behavior that makes sense, in this case, would be reporting why all attempts have failed. So firstOrNone is good for Sequence<Option<T>> but not for Sequence<Either<L, T>> . I'll think about it in future.

[simon.vergauwen]

Well if you want to accumulate the errors you should use Validated instead which can have NonEmptyList<E> in the left side to accumulate all the errors.

[simon.vergauwen]

It uses Semigroup for NonEmptyList to concatenate all the errors together.

[melatonina]

Thanks, Simon! I'll use a firstOrNone for today and I'll refer to this thread when I'll switch to Either<E, T>.

[melatonina]

By the way, there is not even need to pass via T?. firstOrNone is as simple as

fun <T> Sequence<Option<T>>.firstOrNone() =
    firstOrNull { it.nonEmpty() } ?: None

[Jannis]

traverse is the wrong abstraction in this case. It uses Applicatives and thus short-circuits on failure and not success. But there is one that does the exact other thing: Alternative. It exposes a method called altSum which is like sequence that does exactly the same except that it stops as soon as it hits a "success" case. So in your case: firstOrNone == altSum. Also note that you can always do filterMap(::identity).firstOption() ^^

[melatonina]

Thanks, Jannis

[simon.vergauwen]

Oh, thanks for the update on that @Jannis! Completely missed that, would you be open to add some docs to Traverse that explains this duality?

[Jannis]

Yes, definitly. Although it is sadly not as general as duality implies^^ That holds only for datatypes that are "error + success path" Which is more than enough for a doc entry tho.
Btw the categorical dual of Traverse is also quite interesting, not for this issue, but later on for streaming when using mtl. It's Distributive and basically does the opposite of Traverse, instead of "pulling" the inner datatype out it instead "pushes" the outer datatype in^^ Which is quite interesting when you don't want to sequence, but distribute effects^^ (I use the transformer variant in arrow-check to distribute effects over the possibly infinite tree of values a generator provides. That is actually the only correct way to define stateful generators and it's a super power almost no other encoding can achieve^^)

[Jannis]

Anyway I'll take a look at changing the docs either today or tomorrow ^^

[simon.vergauwen]

Oh that does sound very interesting! Wish I had more time 😅