Once you've grokked traversable's you'll wonder how you ever lived without them. Trying to gain intuition about them by staring at the type signature never brought me much joy. So in this post we'll take a different approach and invent them ourselves by solving a real problem. This will help us get to that "aha" moment where we finally understand how they work and when to use them.
The scenario
Imagine we're working for an e-commerce site where we sell one-time offers, such that when all the stock is sold we never have anymore. When a user places an order we must check the stock levels. If there is availability we temporarily reserve the amount they requested before letting them proceed to the checkout.
Our specific task is to write a createCheckout
function that will take a Basket
and try to reserve the items in it. If they can be successfully reserved it will create a Checkout
which includes the total price of the items along with other metadata we might need to take the payment.
Our domain model looks something like this.
type BasketItem =
{ ItemId: ItemId
Quantity: float }
type Basket =
{ Id: BasketId;
Items: BasketItem list }
type ReservedBasketItem =
{ ItemId: ItemId
Price: float }
type Checkout =
{ Id: CheckoutId
BasketId: BasketId
Price: float }
The createCheckout
function will return Checkout option
. It will return Some
if all of the items are available and None
if any of them aren't. A better implementation would return Result
and detail the specific errors, but we'll use option
to keep the example simple.
let createCheckout (basket: Basket): Checkout option
Fortunately for us, someone else has already written a function which can reserve a BasketItem
if it is in stock, which looks like this.
let reserveBasketItem (item: BasketItem): ReservedBasketItem option
Again, this will return None
if there are not enough items in stock.
Our first implementation
So it seems that all we need to do is write a function that calls reserveBasketItem
for each item in the basket. If they all succeed then it calculates the total price in order to create the Checkout
. Let's try it.
let createCheckout basket =
let reservedItems =
basket.Items |> List.map reserveBasketItem
let totalPrice =
reservedItems
|> List.sumBy (fun item -> item.Price)
{ Id = CheckoutId "some-checkout-id"
BasketId = basket.Id
Price = totalPrice }
Here we're just mapping over the items in the basket to reserve each one and then summing their individual prices to get the total basket price. Seems straight forward, except that's not going to compile, because it's not quite right.
The problem is that reservedItems
has the type list<option<ReservedBasketItem>>
but we need it to be option<list<ReservedBasketItem>>
, where it is None
if any one of the reservations fail. That way we'd only be able to calculate the total price and create the Checkout
if all of the items are available. Let's imagine we've written such a function called reserveItems
that does return this type instead and updated createCheckout
to use it.
let reserveItems (items: BasketItem list): option<list<ReservedBasketItem>>
let createCheckout basket =
let reservedItems = basket.Items |> reserveItems
reservedItems
|> Option.map
(fun items ->
{ Id = CheckoutId "some-checkout-id"
BasketId = basket.Id
Price = items |> List.sumBy (fun x -> x.Price) })
That's better! Now if the items are all reserved and reservedItems
returns Some
then we can access the list of ReservedBasketItem
and use them to create the Checkout
. If any of the items can't be reserved then reservedItems
returns None
and the Option.map
just short circuits meaning createCheckout
will also return None
, as we wanted.
So we've reduced the task to implementing reserveItems
. We've already seen that we can't just call List.map reserveBasketItem
because that gives us a list<option<ReservedBasketItem>>
and so the list
and the option
are the wrong way around. We need a way to invert them.
An invertor π
Let's invent a function called invert
that converts list<option<ReservedBasketItem>>
into option<list<ReservedBasketItem>>
. If we can do that then we can implement reserveItems
like this.
let invert (reservedItems: list<option<ReservedBasketItem>>) : option<list<ReservedBasketItem>>
let reserveItems (items: BasketItem list) : option<list<ReservedBasketItem>> =
items
|> List.map reserveBasketItem
|> invert
In order to implement invert
let's start off by pattern matching on the list.
let invert (reservedItems: list<option<ReservedBasketItem>>) : option<list<ReservedBasketItem>> =
match reservedItems with
| head :: tail -> // do something when the list isn't empty
| [] -> // do something when the list is empty
So we've got two cases to deal with, when the list has at least one item and when the list is empty. Let's start with the base case because it's trivial. If the list is empty then it doesn't contain any failures, so we should just return Some []
.
In the non empty case then we've got to do something with head
which is a ReservedBaskedItem option
and tail
which is a list<option<ReservedBasketItem>>
. Well we know that our goal is to turn list<option<ReservedBasketItem>>
into option<list<ReservedBaskedItem>>
, so we can just recursively call invert
on the tail
to do this.
let rec invert (reservedItems: list<option<ReservedBasketItem>>) : option<list<ReservedBasketItem>> =
match reservedItems with
| head :: tail ->
let invertedTail = invert tail
// Need to recombine the head and the inverted tail
| [] -> Some []
Now we just need a way to combine a ReservedBasketItem option
with a option<list<ReservedBasketItem>>
. If neither of these were wrapped in an option
then we would just "cons" them using the ::
operator, so let's write a consOptions
function which does this but for option
arguments.
let consOptions (head: option 'a) (tail: option<list<'a>>): option<list<'a>> =
match head, tail with
| Some h, Some t -> Some (h :: t)
| _ -> None
Nothing too complicated going on here. Simply check if both the head
and tail
are Some
and if so cons them with ::
operator and wrap that in a Some
. Otherwise if either one is None
then return None
.
Putting it all together we can finally implement invert
like this.
let rec invert (reservedItems: list<option<'a>>) : option<list<'a>> =
match reservedItems with
| head :: tail -> consOptions head (invert tail)
| [] -> Some []
We've also been able to make it completely generic on the type inside the list as it doesn't depend on ReservedBasketItem
in any way.
An Applicative clean up π§½
If you're familiar with applicatives, perhaps because you've followed this series and read Grokking Applicatives then you might have spotted that consOptions
looks sort of like a specialised version of apply
. What consOptions
is trying to do is take some values that are wrapped in options
and apply them to a function, in this case cons.
Let's make use of apply
and clean up invert
.
let rec invert list =
// An alias for :: so we can pass it as a function below
let cons head tail = head :: tail
match list with
| head :: tail -> Some cons |> apply head |> apply (invert tail)
| [] -> Some []
In fact, a proper Applicative
instance should also have a pure
function. All pure
does is create a default value for the Applicative
. In the case of option
pure
is just Some
. Let's use pure
to replace the Some
uses.
let rec invert list =
let cons head tail = head :: tail
match list with
| head :: tail -> pure cons |> apply head |> apply (invert tail)
| [] -> pure []
This might not seem like much of a change, but what we've done is eliminate all direct dependencies on option
. In theory this could work with any applicative, such as Result
or Validation
and what it would do is go from list<Applicative<_>>
to Applicative<list<_>>
. In practice however F# doesn't quite allow such an abstraction and so we have to create a version of invert
for each applicative type we want to use it with.
You can technically get around this with statically resolved type parameters. I would recommend checking out FSharpPlus if you want this abstraction rather than rolling it yourself though.
You just discovered sequence
π
invert
is usually called sequence
and it's one of the functions that a Traversable
type gives us. As we can see sequence
takes a collection of wrapped values like an option
and turns it into wrapped collection instead. You can think of sequence
as flipping the two types over.
sequence
works for all sorts of other type combinations too. For example you can take a list<Result<'a>>
and flip it into a Result<list<'a>>
. You can even use it with different collection types and some that don't even seem like typical collections, for instance you could go from Result<option<'a>, 'e>
to option<Result<'a, 'e>>
.
Test yourself on sequence
π§βπ«
See if you can implement sequence
for list<Result<_>>
to Result<list<_>>
.
That's right, it's exactly the same as for the Solution
module Result =
let apply a f =
match f, a with
| Ok g, Ok x -> g x |> Ok
| Error e, Ok _ -> e |> Error
| Ok _, Error e -> e |> Error
| Error e1, Error _ -> e1 |> Error
let pure = Ok
let rec sequence list =
let cons head tail = head :: tail
match list with
| head :: tail -> Result.pure cons |> Result.apply head |> Result.apply (sequence tail)
| [] -> Result.pure []
list<option<_>>
providing we use the applicative Result.apply
and Result.pure
functions for Result
. I've included their definitions too in a Result
module above.
There's still more land to discover π
Let's go back to our original program and see how it looks with our new sequence
discovery.
let createCheckout basket =
let reservedItems =
basket.Items
|> List.map reserveBasketItem
|> sequence
reservedItems
|> Option.map
(fun items ->
{ Id = CheckoutId "some-checkout-id"
BasketId = basket.Id
Price = items |> Seq.sumBy (fun x -> x.Price) })
It's pretty good, but we have to make two passes over the basket.Items
when creating reservedItems
. In the first pass we try and reserve each item and then in the second pass we combine all of those reservations together to determine whether the whole operation succeed or not. It would be nice if we could do that in one go.
Let's see if we can do it all within sequence
. That means that we'll need to pass the reserveBasketItem
function to sequence
and we'll end up with the following signature.
let sequence (f: 'a -> 'b option) (list: 'a list): option<list<'b>>
So we start with a list and we want to apply the function f
to each element of it. Although, rather than just mapping over the list and returning list<option<'b>>
we want to accumulate all of the option
values into a single option<list<'b>>
where it is None
if for any element f
produces a None
.
let rec sequence f list =
let cons head tail = head :: tail
match list with
| head :: tail -> Some cons |> apply (f head) |> apply (sequence tail f)
| [] -> Some []
This is basically the same as before, except now we just apply f
to head
and pass it into the recursive call in order to also transform the tail
elements. All we've done is combine the operation that generates the option
values with the act of combining them together into a single option
of the list.
You just discovered traverse
π
It turns out we typically call the function traverse
when we combine both the sequencing and the mapping at the same time. So a Traversable
actually has two functions associated with it called sequence
and traverse
. In fact, sequence
is just a special case of traverse
where we supply the identity function, id
, for f
. So we could actually write it like this.
let sequence = traverse id
With traverse
in place we can finally finish off our task and write checkoutBasket
nicely like this.
let createCheckout basket =
basket.Items
|> traverse reserveBasketItem
|> Option.map
(fun items ->
{ Id = CheckoutId "some-checkout-id"
BasketId = basket.Id
Price = items |> Seq.sumBy (fun x -> x.Price) })
Test yourself on traverse
π§βπ«
See if you can implement traverse
when the input is option<'a>
and the function is 'a -> Result<'b, 'c>
, so that it returns a Result<option<'b>, 'c>
.
Here I've included the definitions of One concrete use case for this transformation might be if we're trying to write a parser. The parser function might say parse Solution
module Result =
let apply a f =
match f, a with
| Ok g, Ok x -> g x |> Ok
| Error e, Ok _ -> e |> Error
| Ok _, Error e -> e |> Error
| Error e1, Error _ -> e1 |> Error
let pure = Ok
let traverse f opt =
match opt with
| Some x -> Result.pure Some |> Result.apply (f x)
| None -> Result.pure None
apply
and pure
for Result
and then implemented traverse
using those. Hopefully this makes it clearer which parts of the traverse operation relate to the outer option
type and which ones relate to the inner Result
type.string
into Result<int, ParseError>
but we have to hand a string option
. Of course we could pattern match on the option
ourselves and then only run the parser in the Some
case, but we could also write myOptionalValue |> traverse parseInt
.
Another interesting case is when we're dealing with a regular function, say string
which just converts the argument to a string. See if you can figure out what traverse should look like in this case. Specifically, if we want to write [1; 2; 3] |> traverse string
and have it output ["1"; "2"; "3"]
.
I've written this in the same style as the others by extracting an Solution
module Identity =
let apply a f = f a
let pure f = f
let rec traverse list f =
let cons head tail = head :: tail
match list with
| head :: tail -> Identity.pure cons |> Identity.apply (f head) |> Identity.apply (traverse tail f)
| [] -> Identity.pure []
Identity
functor/applicative. Identity
is actually the degenerate case for an applicative because all apply
does is call the function with the argument and all pure
does is return the function unaltered. So there is no wrapping going on like with the other applicatives. This is interesting though because traverse
now has the type list<'a> -> ('a -> 'b) -> list<'b>
, which you might recognise from Grokking Functors as map
. So map
is actually a special case of traverse
when the inner type is just the Identity
applicative.
Spotting Traversable
in the wild πΎ
Whenever you've got some collection of values wrapped in something like option
or Result
and what you actually need is an option<list<'a>>
or Result<list<'a>, 'e>
etc then sequence
is probably what you need to use. Similarly, if you have to run a computation over a collection that produces wrapped values then you can use traverse
and combine the mapping and flipping into one operation.
Warning, two types of error handling ahead β οΈ
When we're sequencing a list<option<_>>
we only need to know that at least one of the elements is None
in order to return None
. However, when working with something like list<Result<'a, 'e>>
then we might actually care about gathering up all of the errors. As we pointed out in Grokking Applicative Validation there can be applicative instances that either short circuit on the first error or accumulate all errors. The same applies here with Traversable
. Let's quickly run some experiments in the F# REPL with FSharpPlus to see how it handles things.
> [Ok 1; Error "first error"; Error "second error"] |> sequence;;
val it : Result<int list, string> = Error "first error"
[Success 1; Failure ["first error"]; Failure ["second error"]] |> sequence;;
val it : Validation<string list, int list> =
Failure ["first error"; "second error"]
In the first case, when using Result
we see that it just returns the first error it encounters, while with Validation
it actually accumulates all the errors for us.
What did we learn π§βπ
Traversable
is more powerful version of map
that is particularly useful when we have a computation that either needs to be run (or has already been run) over a list of values and we want to treat it as a failure if any single one fails. We can also grok it by realising that it flips the two outer types over. We use traverse
when we still need to run the computation and sequence
when we've been given the list of computation results instead.
Oldest comments (9)
Clearest explanation of this concept I've seen so far. I stumbled on traversables by accident once and while I got a working solution, I've always been worried I'd be unable to replicate it again.
Your writing makes the application (pun not intended) super clear. Thank you.
Thanks and youβre welcome. Youβll be traversing like a pro from now on. π
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>>
tooption<list<T>>
, which I think means the outer monad has to be traversable? Is there also a way to go fromoption<list<T>>
tolist<option<T>>
? (I'm not even sure of a situation where you would want to do this).Not a stupid question at all. It's definitely a much less intuitive situation to go from
option<list<T>>
tolist<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
theSome
function to each element of the inner list if whole thing isSome list
otherwise we want to return a list containing a single value ofNone
. In code it looks like this.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 theoption
inside thelist
because in more cases you'd just match on theoption
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 fromlist<option<_>>
tooption<list<_>>
and by having this available we can "sort of" recover the original. Although we have lost some information in the case of aNone
element in the original list because when we first sequenced it we chucked away all of theSome
elements, so it's not a perfect recovery.Wonderful post just like the rest of the series.
I think I have noticed a small error in the first code snippet after
An Applicative clean up π§½
which usessequence
instead ofinvert
Thanks for pointing that out. Youβre right. And thanks for the kind words.
Fixed π¨π
This is a truly amazing series of posts!
Thanks to your approach of introducing a new concept by tying it to a real-world problem, I finally understood Applicative, sequence and traverse.
Looking forward to tackling the Reader Monad next!
π Glad itβs helped you get to grips with them.