# Sequence All The Things implement sequence on your own types

This post describes how to write a `sequence`

method for your shiny new type `F`

. This allows you to get from a type `G[F[A]]`

to `F[G[A]]`

– that is, to swap the order of your types. Here I’ll be using scalaz, and there is no magic involved. For many common types everything is already there for you, but if you write your own `F[_]`

then there’s a little work to make it all fit together.

There limits on what the two types can be here, but in general:

`sequence`

takes a`G[F[A]]`

and gives you a`F[G[A]]`

## Intuition

Consider your type to be like `Option`

and the other type to be `List`

. Starting with a list of options, you want to be able to get an optional list, which is present only if all of the options in the original list were present. If anything was absent, the returned `Option[List]`

is absent.

## Executive summary

You only need a few things in order to make this work, which I’ll describe below:

- an
`Applicative[F]`

instance for your type, e.g.`Option`

- a
`Traverse[G]`

instance for the other type, e.g.`List`

- syntax support from
`scalaz.syntax.traverse._`

to add the`sequence`

method to the`G`

type - consider using
`sequenceU`

if your type is more complicated than one with a single type parameter

# Simple start with `MyOption[A]`

Let’s start with the simple example of implementing an option type, called `MyOption`

. The minimal implementation looks something like this:

The usage we’re trying to support might look like this:

For a start, scalaz provides the `Traverse[List]`

instance for us. This import says: give the scalaz helpers (specifically the typeclass instances) for the standard list type.

Now you need an `Applicative`

for `MyOption`

. It turns to be easier to create a `Monad`

, which extends `Applicative`

anyway.

That’s it: you can now do `listOfOptions.sequence`

to turn a `MyOption[List[A]]`

into a `List[MyOption[A]]`

.

Bonus: to do the reverse, create a `Traverse`

for `MyOption`

. Traverse acts a bit like flatMap,

Then you can do `.sequence`

on a `List[MyOption[A]]`

and get a `MyOption[List[A]]`

. Note that it’s not always possible to map in both directions, because of the required properties of being able to find `Applicative`

and `Traverse`

instances.

# Type Lambdas and `Either[L, R]`

It’s more tricky when your type has more than one type parameter, because you need to force your type into fitting into `Applicative[A[_]]`

, which takes one type parameter. The only good way of doing this is with a type lambda. The idea is that you *fix* one of the parameter types; here we fix `L`

. You might call this a partially applied type constructor – this is exactly analogous to partial application of a function, where some of its parameters are fixed.

The expression `({type t[a] = MyEither[L, a]})#t`

means: a type `t`

that takes one type parameter, and which is equal to `MyEither[L, _]`

. This is an unfortunately complicated syntax for a simple idea.

Fixing one type parameter gives you a new type constructor that has only one type parameter. We can use this to create the `Applicative`

. Note it’s not an `object`

now, since we need one per type `L`

that we fix for the first type parameter.

This isn’t quite enough: attempting to compile `listOfMyEithers.sequence`

gives cryptic error messages about `could not find implicit value for parameter ev: scalaz.Leibniz.===[MyEither[String,Int],G[B]]`

, which amounts to saying that it couldn’t find the required implicit to prove that `MyEither`

has an `Applicative`

instance. (The Leibniz part is about the equality condition required between your type and the `Applicative`

.)

It’s possible to solve this with another type lambda, allowing the compiler to understand how you want to deconstruct the `MyEither`

into something that can be expressed with a single type parameter. An easier way is with `sequenceU`

, a different implementation of the same idea of `sequence`

. With the same imports as above:

## Woah, what just happened there?

`sequenceU`

is a method that implements the same behaviour as `sequence`

but expresses the types differently, allowing the types to be inferred. This works through a type called `Unapply`

that represents a type with one type parameter, but using a typeclass to provide the relation between the outer and inner types.

The implicit being used here can be created explicitly as the following. This says, paraphrasing the docs: unpack a value of type `MyEither[A, B]`

into types `[b]M[A, b]`

and `B`

, and then find an `Applicative`

instance for the partially applied type `MyEither[L, _]`

.