Discussion on: Grokking Traversable

[Richard Thornton]

This post is really great! (As is the whole series ⭐️)

If I can ask a potentially stupid question. So in your example you can go from list<option<T>> to option<list<T>>, which I think means the outer monad has to be traversable? Is there also a way to go from option<list<T>> to list<option<T>>? (I'm not even sure of a situation where you would want to do this).

[Matt Thornton]

Not a stupid question at all. It's definitely a much less intuitive situation to go from option<list<T>> to list<option<T>> than it is going the other way, but it's possible to do it.

We just need to create an applicative instance for List. That in itself is probably worth thinking about first. Basically it takes a list of arguments and a list of functions and applies each argument to each function. So in effect we get a cross product of results.

Thinking about it that way then what we want to do is apply the Some function to each element of the inner list if whole thing is Some list otherwise we want to return a list containing a single value of None. In code it looks like this.

module Option =
    module ListApplicative =
        let apply a f =
            a
            |> List.collect (fun x -> f |> List.map (fun g -> g x))
            // collect is like SelectMany in C# it flattens a list of lists

        let pure x = [ x ]

    let sequence opt =
        match opt with
        | Some x ->
            ListApplicative.pure Some
            |> ListApplicative.apply x
        | None -> ListApplicative.pure None

I'm also struggling to think of a real world example for this conversion though. I can see a situation where someone hands you a option<list<T>> (perhaps from a DB call for a collection that might not exist or something), but then I can't think of a scenario in which you'd want to push the option inside the list because in more cases you'd just match on the option to decide whether or not to operate on the inner list.

I guess one way to think about it is just as the dual of the more typical sequence where you go from list<option<_>> to option<list<_>> and by having this available we can "sort of" recover the original. Although we have lost some information in the case of a None element in the original list because when we first sequenced it we chucked away all of the Some elements, so it's not a perfect recovery.