This post is one in a series.
In the first two posts, I described some of the core functions for dealing with generic data types: map
, bind
, and so on.
In the previous post, I discussed “applicative” vs “monadic” style, and how to lift values and functions to be consistent with each other.
In this post, we’ll look at a common problem: working with lists of elevated values.
Here’s a list of shortcuts to the various functions mentioned in this series:
A common issue is how to deal with lists or other collections of elevated values.
Here are some examples:
Example 1: We have a parseInt
with signature string -> int option
, and we have a list of strings. We want to parse all the strings at once.
Now of course we can use map
to convert the list of strings to a list of options. But what we really want is not a “list of options” but an “option of list”,
a list of parsed ints, wrapped in an option in case any fail.
Example 2: We have a readCustomerFromDb
function with signature CustomerId -> Result<Customer>
, that will return Success
if the record
can be found and returned, and Failure
otherwise. And say we have a list of CustomerId
s and we want to read all the customers at once.
Again, we can use map
to convert the list of ids to a list of results. But what we really want is not a list of Result<Customer>
,
but a Result
containing a Customer list
, with the Failure
case in case of errors.
Example 3: We have a fetchWebPage
function with signature Uri -> Async<string>
, that will return a task that will download the page contents on demand.
And say we have a list of Uris
s and we want to fetch all the pages at once.
Again, we can use map
to convert the list of Uri
s to a list of Async
s. But what we really want is not a list of Async
,
but a Async
containing a list of strings.
Let’s start by coming up with a solution for the first case and then seeing if we can generalize it to the others.
The obvious approach would be:
map
to turn the list of string
into a list of Option<int>
.Option<int>
into an Option<int list>
.But this requires two passes through the list. Can we do it in one pass?
Yes! If we think about how a list is built, there is a “cons” function (::
in F#) that is used to join the head to the tail.
If we elevate this to the Option
world, we can use Option.apply
to join a head Option
to a tail Option
using the lifted version of cons
.
let (<*>) = Option.apply
let retn = Some
let rec mapOption f list =
let cons head tail = head :: tail
match list with
| [] ->
retn []
| head::tail ->
retn cons <*> (f head) <*> (mapOption f tail)
NOTE: I defined cons
explicitly because ::
is not a function and List.Cons
takes a tuple and is thus not usable in this context.
Here is the implementation as a diagram:
If you are confused as to how this works, please read the section on apply
in the first post in this series.
Note also that I am explicitly defining retn
and using it in the implementation rather than just using Some
. You’ll see why in the next section.
Now let’s test it!
let parseInt str =
match (System.Int32.TryParse str) with
| true,i -> Some i
| false,_ -> None
// string -> int option
let good = ["1";"2";"3"] |> mapOption parseInt
// Some [1; 2; 3]
let bad = ["1";"x";"y"] |> mapOption parseInt
// None
We start by defining parseInt
of type string -> int option
(piggybacking on the existing .NET library).
We use mapOption
to run it against a list of good values, and we get Some [1; 2; 3]
, with the list inside the option, just as we want.
And if we use a list where some of the values are bad, we get None
for the entire result.
Let’s repeat this, but this time using the Result
type from the earlier validation example.
Here’s the mapResult
function:
let (<*>) = Result.apply
let retn = Success
let rec mapResult f list =
let cons head tail = head :: tail
match list with
| [] ->
retn []
| head::tail ->
retn cons <*> (f head) <*> (mapResult f tail)
Again I am explicitly defining a retn
rather than just using Success
. And because of this, the body of the code for mapResult
and mapOption
is exactly the same!
Now let’s change parseInt
to return a Result
rather than an Option
:
let parseInt str =
match (System.Int32.TryParse str) with
| true,i -> Success i
| false,_ -> Failure [str + " is not an int"]
And then we can rerun the tests again, but this time getting more informative errors in the failure case:
let good = ["1";"2";"3"] |> mapResult parseInt
// Success [1; 2; 3]
let bad = ["1";"x";"y"] |> mapResult parseInt
// Failure ["x is not an int"; "y is not an int"]
The implementations of mapOption
and mapResult
have exactly the same code,
the only difference is the different retn
and <*>
functions (from Option and Result, respectively).
So the question naturally arises, rather than having mapResult
, mapOption
, and other specific implementations for each elevated type,
can we make a completely generic version of mapXXX
that works for all elevated types?
The obvious thing would be able to pass these two functions in as an extra parameter, like this:
let rec mapE (retn,ap) f list =
let cons head tail = head :: tail
let (<*>) = ap
match list with
| [] ->
retn []
| head::tail ->
(retn cons) <*> (f head) <*> (mapE retn ap f tail)
There are some problems with this though. First, this code doesn’t compile in F#! But even if it did, we’d want to make sure that the same two parameters were passed around everywhere.
We might attempt this by creating a record structure containing the two parameters, and then create one instance for each type of elevated world:
type Applicative<'a,'b> = {
retn: 'a -> E<'a>
apply: E<'a->'b> -> E<'a> -> E<'b>
}
// functions for applying Option
let applOption = {retn = Option.Some; apply=Option.apply}
// functions for applying Result
let applResult = {retn = Result.Success; apply=Result.apply}
The instance of the Applicative
record (appl
say) would be an extra parameter to our generic mapE
function, like this:
let rec mapE appl f list =
let cons head tail = head :: tail
let (<*>) = appl.apply
let retn = appl.retn
match list with
| [] ->
retn []
| head::tail ->
(retn cons) <*> (f head) <*> (mapE retn ap f tail)
In use, we would pass in the specific applicative instance that we want, like this:
// build an Option specific version...
let mapOption = mapE applOption
// ...and use it
let good = ["1";"2";"3"] |> mapOption parseInt
Unfortunately, none of this works either, at least in F#. The Applicative
type, as defined, won’t compile. This is because F# does not support “higher-kinded types”.
That is, we can’t parameterize the Applicative
type with a generic type, only with concrete types.
In Haskell and languages that do support “higher-kinded types”, the Applicative
type that we’ve defined is similar to a “type class”.
What’s more, with type classes, we don’t have to pass around the functions explicitly – the compiler will do that for us.
There is actually a clever (and hacky) way of getting the same effect in F# though using static type constraints. I’m not going to discuss it here, but you can see it used in the FSharpx library.
The alternative to all this abstraction is just creating a mapXXX
function for each elevated world that we want to work with:
mapOption
, mapResult
, mapAsync
and so on.
Personally I am OK with this cruder approach. There are not that many elevated worlds that you work with regularly, and even though you lose out on abstraction, you gain on explicitness, which is often useful when working in a team of mixed abilities.
So let’s look at these mapXXX
functions, also called traverse
.
traverse
/ mapM
functionCommon Names: mapM
, traverse
, for
Common Operators: None
What it does: Transforms a world-crossing function into a world-crossing function that works with collections
Signature: (a->E<b>) -> a list -> E<b list>
(or variants where list is replaced with other collection types)
We saw above that we can define a set of mapXXX
functions, where XXX stands for an applicative world – a world that has apply
and return
.
Each of these mapXXX
functions transforms a world-crossing function into a world-crossing function that works with collections.
And as we noted above, if the language supports type classes, we can get away with a single implementation, called mapM
or traverse
. I’m going to call
the general concept traverse
from now on to make it clear that is different from map
.
Understanding the difference between map
and traverse
can be hard, so let’s see if we can explain it in pictures.
First, let’s introduce some visual notation using the analogy of an “elevated” world sitting above a “normal” world.
Some of these elevated worlds (in fact almost all of them!) have apply
and return
functions. We’ll call these “Applicative worlds”. Examples
include Option
, Result
, Async
, etc.
And some of these elevated worlds have a traverse
function. We’ll call these “Traversable worlds”, and we’ll use List
as a classic example.
If a Traversable world is on top, that produces a type such as List<a>
, and
if an Applicative world is on top, that produces a type such as Result<a>
.
IMPORTANT: I will be using the syntax List<_>
to represent “List world” for consistency with Result<_>
, etc. This is *not meant to be the same as the .NET List class!
In F#, this would be implemented by the immutable list
type*.
But from now on we are going to be dealing with both kinds of elevated worlds in the same “stack”.
The Traversable world can be stacked on top of the Applicative world, which produces a type such as List<Result<a>>
, or alternatively,
the Applicative world world can be stacked on top of the Traversable world, which produces a type such as Result<List<a>>
.
Now let’s see what the different kinds of functions look like using this notation.
Let’s start with a plain cross-world function such as a -> Result<b>
, where the target world is an applicative world.
In the diagram, the input is a normal world (on the left), and the output (on the right) is an applicative world stacked on top of the normal world.
Now if we have a list of normal a
values, and then we use map
to transform each a
value using a function like a -> Result<b>
,
the result will also be a list, but where the contents are Result<b>
values instead of a
values.
When it comes to traverse
the effect is quite different.
If we use traverse
to transform a list of a
values using that function,
the output will be a Result
, not a list. And the contents of the Result
will be a List<b>
.
In other words, with traverse
, the List
stays attached to the normal world, and the Applicative world (such as Result
) is added at the top.
Ok, I know this all sounds very abstract, but it is actually a very useful technique. We’ll see an example of this is used in practice below.
traverse
It turns out that traverse
can be implemented in an applicative style or a monadic style, so there are often two separate implementations to choose from.
The applicative versions tend to end in A
and the monadic versions end in M
, which is helpful!
Let’s see how this works with our trusty Result
type.
First, we’ll implement traverseResult
using both applicative and monadic approaches.
module List =
/// Map a Result producing function over a list to get a new Result
/// using applicative style
/// ('a -> Result<'b>) -> 'a list -> Result<'b list>
let rec traverseResultA f list =
// define the applicative functions
let (<*>) = Result.apply
let retn = Result.Success
// define a "cons" function
let cons head tail = head :: tail
// loop through the list
match list with
| [] ->
// if empty, lift [] to a Result
retn []
| head::tail ->
// otherwise lift the head to a Result using f
// and cons it with the lifted version of the remaining list
retn cons <*> (f head) <*> (traverseResultA f tail)
/// Map a Result producing function over a list to get a new Result
/// using monadic style
/// ('a -> Result<'b>) -> 'a list -> Result<'b list>
let rec traverseResultM f list =
// define the monadic functions
let (>>=) x f = Result.bind f x
let retn = Result.Success
// define a "cons" function
let cons head tail = head :: tail
// loop through the list
match list with
| [] ->
// if empty, lift [] to a Result
retn []
| head::tail ->
// otherwise lift the head to a Result using f
// then lift the tail to a Result using traverse
// then cons the head and tail and return it
f head >>= (fun h ->
traverseResultM f tail >>= (fun t ->
retn (cons h t) ))
The applicative version is the same implementation that we used earlier.
The monadic version applies the function f
to the first element and then passes it to bind
.
As always with monadic style, if the result is bad the rest of the list will be skipped.
On the other hand, if the result is good, the next element in the list is processed, and so on. Then the results are cons’ed back together again.
NOTE: These implementations are for demonstration only! Neither of these implementations are tail-recursive, and so they will fail on large lists!
Alright, let’s test the two functions and see how they differ. First we need our parseInt
function:
/// parse an int and return a Result
/// string -> Result<int>
let parseInt str =
match (System.Int32.TryParse str) with
| true,i -> Result.Success i
| false,_ -> Result.Failure [str + " is not an int"]
Now if we pass in a list of good values (all parsable), the result for both implementations is the same.
// pass in strings wrapped in a List
// (applicative version)
let goodA = ["1"; "2"; "3"] |> List.traverseResultA parseInt
// get back a Result containing a list of ints
// Success [1; 2; 3]
// pass in strings wrapped in a List
// (monadic version)
let goodM = ["1"; "2"; "3"] |> List.traverseResultM parseInt
// get back a Result containing a list of ints
// Success [1; 2; 3]
But if we pass in a list with some bad values, the results differ.
// pass in strings wrapped in a List
// (applicative version)
let badA = ["1"; "x"; "y"] |> List.traverseResultA parseInt
// get back a Result containing a list of ints
// Failure ["x is not an int"; "y is not an int"]
// pass in strings wrapped in a List
// (monadic version)
let badM = ["1"; "x"; "y"] |> List.traverseResultM parseInt
// get back a Result containing a list of ints
// Failure ["x is not an int"]
The applicative version returns all the errors, while the monadic version returns only the first error.
traverse
using fold
I mentioned above that the “from-scratch” implementation was not tail recursive and would fail for large lists. That could be fixed of course, at the price of making the code more complicated.
On the other hand, if your collection type has a “right fold” function, as List
does, then you can use that to make the implementation simpler, faster, and safer too.
In fact, I always like to use fold
and its ilk wherever possible so that I never have to worry about getting tail-recursion right!
So, here are the re-implementations of traverseResult
, using List.foldBack
. I have kept the code as similar as possible,
but delegated the looping over the list to the fold function, rather than creating a recursive function.
/// Map a Result producing function over a list to get a new Result
/// using applicative style
/// ('a -> Result<'b>) -> 'a list -> Result<'b list>
let traverseResultA f list =
// define the applicative functions
let (<*>) = Result.apply
let retn = Result.Success
// define a "cons" function
let cons head tail = head :: tail
// right fold over the list
let initState = retn []
let folder head tail =
retn cons <*> (f head) <*> tail
List.foldBack folder list initState
/// Map a Result producing function over a list to get a new Result
/// using monadic style
/// ('a -> Result<'b>) -> 'a list -> Result<'b list>
let traverseResultM f list =
// define the monadic functions
let (>>=) x f = Result.bind f x
let retn = Result.Success
// define a "cons" function
let cons head tail = head :: tail
// right fold over the list
let initState = retn []
let folder head tail =
f head >>= (fun h ->
tail >>= (fun t ->
retn (cons h t) ))
List.foldBack folder list initState
Note that this approach will not work for all collection classes. Some types do not have a right fold,
so traverse
must be implemented differently.
All these examples have used the list
type as the collection type. Can we implement traverse
for other types too?
Yes. For example, an Option
can be considered a one-element list, and we can use the same trick.
For example, here’s an implementation of traverseResultA
for Option
module Option =
/// Map a Result producing function over an Option to get a new Result
/// ('a -> Result<'b>) -> 'a option -> Result<'b option>
let traverseResultA f opt =
// define the applicative functions
let (<*>) = Result.apply
let retn = Result.Success
// loop through the option
match opt with
| None ->
// if empty, lift None to an Result
retn None
| Some x ->
// lift value to an Result
(retn Some) <*> (f x)
Now we can wrap a string in an Option
and use parseInt
on it. Rather than getting a Option
of Result
, we invert the stack and get a Result
of Option
.
// pass in an string wrapped in an Option
let good = Some "1" |> Option.traverseResultA parseInt
// get back a Result containing an Option
// Success (Some 1)
If we pass in an unparsable string, we get failure:
// pass in an string wrapped in an Option
let bad = Some "x" |> Option.traverseResultA parseInt
// get back a Result containing an Option
// Failure ["x is not an int"]
If we pass in None
, we get Success
containing None
!
// pass in an string wrapped in an Option
let goodNone = None |> Option.traverseResultA parseInt
// get back a Result containing an Option
// Success (None)
This last result might be surprising at first glance, but think of it this way, the parsing didn’t fail, so there was no Failure
at all.
Types that can implement a function like mapXXX
or traverseXXX
are called Traversable. For example, collection types are Traversables as well as some others.
As we saw above, in a language with type classes a Traversable type can get away with just one implementation of traverse
,
but in a language without type classes a Traversable type will need one implementation per elevated type.
Also note that, unlike all the generic functions we have created before, the type being acted on (inside the collection)
must have appropriate apply
and return
functions in order for traverse
to be implemented. That is, the inner type must be an Applicative.
traverse
implementationAs always, a correct implementation of traverse
should have some properties that are true no matter what elevated world we are working with.
These are the “Traversable Laws”,
and a Traversable is defined as a generic data type constructor – E<T>
– plus a set of
functions (traverse
or traverseXXX
) that obey these laws.
The laws are similar to the previous ones. For example, the identity function should be mapped correctly, composition should be preserved, etc.
sequence
functionCommon Names: sequence
Common Operators: None
What it does: Transforms a list of elevated values into an elevated value containing a list
Signature: E<a> list -> E<a list>
(or variants where list is replaced with other collection types)
We saw above how you can use the traverse
function as a substitute for map
when you have a function that generates an applicative type such as Result
.
But what happens if you are just handed a List<Result>
and you need to change it to a Result<List>
. That is, you need to swap the order of the worlds on the stack:
This is where sequence
is useful – that’s exactly what it does! The sequence
function “swaps layers”.
The order of swapping is fixed:
Note that if you aleady have an implementation of traverse
, then sequence
can be derived from it easily.
In fact, you can think of sequence
as traverse
with the id
function baked in.
sequence
Just as with traverse
, there can be applicative and monadic versions of sequence
:
sequenceA
for the applicative one.sequenceM
(or just sequence
) for the monadic one.Let’s implement and test a sequence
implementation for Result
:
module List =
/// Transform a "list<Result>" into a "Result<list>"
/// and collect the results using apply
/// Result<'a> list -> Result<'a list>
let sequenceResultA x = traverseResultA id x
/// Transform a "list<Result>" into a "Result<list>"
/// and collect the results using bind.
/// Result<'a> list -> Result<'a list>
let sequenceResultM x = traverseResultM id x
Ok, that was too easy! Now let’s test it, starting with the applicative version:
let goodSequenceA =
["1"; "2"; "3"]
|> List.map parseInt
|> List.sequenceResultA
// Success [1; 2; 3]
let badSequenceA =
["1"; "x"; "y"]
|> List.map parseInt
|> List.sequenceResultA
// Failure ["x is not an int"; "y is not an int"]
and then the monadic version:
let goodSequenceM =
["1"; "2"; "3"]
|> List.map parseInt
|> List.sequenceResultM
// Success [1; 2; 3]
let badSequenceM =
["1"; "x"; "y"]
|> List.map parseInt
|> List.sequenceResultM
// Failure ["x is not an int"]
As before, we get back a Result<List>
, and as before the monadic version stops on the first error, while the applicative version accumulates all the errors.
We saw above that having type classes like Applicative means that you only need to implement traverse
and sequence
once. In F# and other
languages without high-kinded types you have to create an implementation for each type that you want to traverse over.
Does that mean that the concepts of traverse
and sequence
are irrelevant or too abstract? I don’t think so.
Instead of thinking of them as library functions, I find that it is useful to think of them as recipes – a set of instructions that you can follow mechanically to solve a particular problem.
In many cases, the problem is unique to a context, and there is no need to create a library function – you can create a helper function as needed.
Let me demonstrate with an example. Say that you are given a list of options, where each option contains a tuple, like this:
let tuples = [Some (1,2); Some (3,4); None; Some (7,8);]
// List<Option<Tuple<int>>>
This data is in the form List<Option<Tuple<int>>>
. And now say, that for some reason, you need to turn it into a tuple of two lists, where each list contains options,
like this:
let desiredOutput = [Some 1; Some 3; None; Some 7],[Some 2; Some 4; None; Some 8]
// Tuple<List<Option<int>>>
The desired result is in the form Tuple<List<Option<int>>>
.
So, how would you write a function to do this? Quick!
No doubt you could come up with one, but it might require a bit of thought and testing to be sure you get it right.
On the other hand, if you recognize that this task is just transforming a stack of worlds to another stack, you can create a function mechanically, almost without thinking.
To design the solution, we need to pay attention to which worlds move up and which worlds move down.
In order to do this transform then, I will need two helper functions:
optionSequenceTuple
will move an option down and a tuple up.listSequenceTuple
will move a list down and a tuple up.Do these helper functions need to be in a library? No. It’s unlikely that I will need them again, and even I need them occasionally, I’d prefer to write them scratch to avoid having to take a dependency.
On the other hand, the List.sequenceResult
function implemented earlier that converts a List<Result<a>>
to a Result<List<a>>
is something I do use frequently,
and so that one is worth centralizing.
Once we know how the solution will look, we can start coding mechanically.
First, the tuple is playing the role of the applicative, so we need to define the apply
and return
functions:
let tupleReturn x = (x, x)
let tupleApply (f,g) (x,y) = (f x, g y)
Next, define listSequenceTuple
using exactly the same right fold template as we did before, with List
as the traversable and tuple as the applicative:
let listSequenceTuple list =
// define the applicative functions
let (<*>) = tupleApply
let retn = tupleReturn
// define a "cons" function
let cons head tail = head :: tail
// right fold over the list
let initState = retn []
let folder head tail = retn cons <*> head <*> tail
List.foldBack folder list initState
There is no thinking going on here. I’m just following the template!
We can test it immediately:
[ (1,2); (3,4)] |> listSequenceTuple
// Result => ([1; 3], [2; 4])
And it gives a tuple with two lists, as expected.
Similarly, define optionSequenceTuple
using the same right fold template again.
This time Option
is the traversable and tuple is still the applicative:
let optionSequenceTuple opt =
// define the applicative functions
let (<*>) = tupleApply
let retn = tupleReturn
// right fold over the option
let initState = retn None
let folder x _ = (retn Some) <*> x
Option.foldBack folder opt initState
We can test it too:
Some (1,2) |> optionSequenceTuple
// Result => (Some 1, Some 2)
And it gives a tuple with two options, as expected.
Finally, we can glue all the parts together. Again, no thinking required!
let convert input =
input
// from List<Option<Tuple<int>>> to List<Tuple<Option<int>>>
|> List.map optionSequenceTuple
// from List<Tuple<Option<int>>> to Tuple<List<Option<int>>>
|> listSequenceTuple
And if we use it, we get just what we wanted:
let output = convert tuples
// ( [Some 1; Some 3; None; Some 7], [Some 2; Some 4; None; Some 8] )
output = desiredOutput |> printfn "Is output correct? %b"
// Is output correct? true
Ok, this solution is more work than having one reusable function, but because it is mechanical, it only takes a few minutes to code, and is still easier than trying to come up with your own solution!
Want more? For an example of using sequence
in a real-world problem, please read this post.
At the beginning of this post I noted our tendency as functional programmers to map
first and ask questions later.
In other words, given a Result
producing function like parseInt
, we would start by collecting the results and only then figure out how to deal with them.
Our code would look something like this, then:
["1"; "2"; "3"]
|> List.map parseInt
|> List.sequenceResultM
But of course, this does involve two passes over the list, and we saw how traverse
could combine the map
and the sequence
in one step,
making only one pass over the list, like this:
["1"; "2"; "3"]
|> List.traverseResultM parseInt
So if traverse
is more compact and potentially faster, why ever use sequence
?
Well, sometimes you are given a certain structure and you have no choice, but in other situations I might still prefer the two-step map-sequence
approach just because it
is easier to understand. The mental model for “map” then “swap” seems easier to grasp for most people than the one-step traverse.
In other words, I would always go for readability unless you can prove that performance is impacted. Many people are still learning FP, and being overly cryptic is not helpful, in my experience.
filter
?We’ve seen that functions like map
and sequence
work on lists to transform them into other types, but what about filtering? How can I filter things using these methods?
The answer is – you can’t! map
, and traverse
and sequence
are all “structure preserving”.
If you start with a list of 10 things you still have a list of 10 things afterwards, albeit somewhere else in the stack.
Or if you start with a tree with three branches, you still have a tree of three branches at the end.
In the tuple example above, the original list had four elements, and after the transformation, the two new lists in the tuple also had four elements.
If you need to change the structure of a type, you need to use something like fold
. Fold allows you to build a new structure from an old one,
which means that you can use it to create a new list with some elements missing (i.e. a filter).
The various uses of fold are worthy of their own series, so I’m going to save a discussion of filtering for another time.
In this post, we learned about traverse
and sequence
as a way of working with lists of elevated values.
In the next post we’ll finish up by working through a practical example that uses all the techniques that have been discussed.