# AssociativeEither

`AssociativeEither`

describes a way of combining two values `F[A]`

and `F[B]`

into a value `F[Either[A, B]]`

that is associative.

Its signature is:

```
trait AssociativeEither[F[_]] {
def either[A, B](fa: => F[A], fb: => F[B]): F[Either[A, B]]
}
```

If we import `zio.prelude._`

we can use the `orElseEither`

operator or its symbolic alias `<+>`

to combine any two values of a parameterized type `F`

that have an `AssociativeEither`

instance defined for them.

The `either`

operator must be associative, so if we combine two values `fa`

and `fb`

and then combine the result with `fc`

, that must be the same as combining `fb`

with `fc`

and then combining `fa`

with the result. That is, after reassociating `Either`

values the following property must hold:

```
(fa <+> fb) <+> fc === fa <+> (fb <+> fc)
```

This is the same associative law we saw for concrete types described by the `Associative`

abstraction, but lifted to the context of parameterized types.

The `either`

operator corresponds to running the left value and if that fails running the right value.

To see this, we can observe that since the `either`

operator must return an `Either[A, B]`

we must choose on some basis whether to return the left value or the right value. Furthermore, we must choose on some consistent basis so that the order of operations does not matter.

There are a couple of trivial ways we could do this, like always running the left value or always running the right value. However, the way we can do this that preserves information is to run the right value and then if it fails in some way to run the right value.

What it means to run the left value and then if it fails run the right value depends on the parameterized type.

For `ZIO`

the meaning is quite straightforward. The `orElseEither`

operator runs the left `ZIO`

workflow and returns its result if it succeeds, otherwise it runs the right `ZIO`

workflow and returns its result.

```
import zio._
def orElseEither[R, E, A, B](left: => ZIO[R, E, A], right: => ZIO[R, E, B]): ZIO[R, E, Either[A, B]] =
left.foldM(_ => right.map(b => Right(b)), a => ZIO.succeed(Left(a)))
```

Here we run the `left`

workflow and if it is successful we just wrap it up in a `Left`

. If the `left`

workflow fails we recover from its failure and run the `Right`

effect, packaging its result up in a `Right`

.

We can see that this is associative because no matter how many `ZIO`

workflows we combine with `orElseEither`

the result will always be the first one from left to right to successfully complete execution.

Notice here that if the `left`

workflow succeeds we never run the right workflow at all or even need to construct it. The fact that `either`

and the other binary operators in ZIO Prelude are by name gives us the freedom to model that instead of having to introduce additional interfaces.

Other data types that model failure have similar implementations of the `orElseEither`

operator. For example, here are the implementations of `orElseEither`

for `Either`

and `Option`

.

```
def orElseEither[E, A, B](left: => Either[E, A], => right: Either[E, B])]): Either[E, Either[A, B]] =
left match {
case Left(e) =>
that match {
case Left(e) => Left(e)
case Right(b) => Right(Right(b))
}
case Right(a) => Right(Left(a))
}
def orElseEither[A, B](left: => Option[A], => right: Option[B])]): Option[Either[A, B]] =
left match {
case None =>
that match {
case None => None
case Right(b) => Some(Right(b))
}
case Some(a) => Some(Left(a))
}
```

In both cases if the `left`

value is a success we return its result in a `Left`

. Otherwise if the `right`

value is a success we return its result in a `Right`

and if it is a failure we fail with that error.

Notice in both cases we did not need to evaluate the `right`

value if the `left`

value was a success. We could have just made the `right`

parameter lazy but we could flip any of these binary operators so for correctness it is important that both arguments be lazy.

Another interpretation of `orElseEither`

comes from collections. Consider the following implementation of the `orElseEither`

operator for `Chunk`

.

```
import zio.prelude._
implicit val ChunkAssociativeEither: AssociativeEither[Chunk] =
new AssociativeEither[Chunk] {
def either[A, B](as: => Chunk[A], bs: => Chunk[B]): Chunk[Either[A, B]] =
as.map(Left(_)) ++ bs.map(Right(_))
}
// ChunkAssociativeEither: AssociativeEither[Chunk] = repl.MdocSession$MdocApp0$$anon$1@59dfef29
```

Here we are concatenating the two `Chunk`

values, putting the elements from the left `Chunk`

in a `Left`

and the elements from the right `Chunk`

in a `Right`

. We can think of this as running the left `Chunk`

until it fails by running out of elements and then running the right `Chunk`

.

We can see a similar interpretation in the implementation of the `orElseEither`

operator for the `Schedule`

data type from `ZIO`

. It runs the left schedule while it wants to continue and when it stops runs the right schedule, emitting either a `Left`

with the output of the left schedule or a `Right`

with the output of the right schedule each time.

The `AssociativeEither`

abstraction isn't limited to covariant data types.

Let's see how we can use the `orElseEither`

operator to combine values of a contravariant type.

The `Predicate`

type knows how to evaluate a value of type `A`

to return a `Boolean`

. This `Boolean`

could describe whether the value of type `A`

is valid data for example, or whether we should take some further action.

```
trait Predicate[-A] {
def run(a: A): Boolean
}
```

We could implement an instance of the `AssociativeEither`

abstraction for `Predicate`

like this:

```
object Predicate {
implicit val PredicateAssociativeEither: AssociativeEither[Predicate] =
new AssociativeEither[Predicate] {
def either[A, B](left: => Predicate[A], right: => Predicate[B]): Predicate[Either[A, B]] =
new Predicate[Either[A, B]] {
def run(either: Either[A, B]): Boolean =
either match {
case Left(a) => left.run(a)
case Right(b) => right.run(b)
}
}
}
}
```

The interpretation is slightly different here. Now failing means not being able to handle a value at all.

The left `Predicate`

knows how to determine whether `A`

values satisfy the condition and the right `Predicate`

knows how to determine whether `B`

values satisfy the condition. So when we get an `Either[A, B]`

we have to match on it to determine whether it is an `A`

that the left `Predicate`

can handle at all.

If so, we send it to the left `Predicate`

and return its result. Otherwise we send it to the right `Predicate`

and return its result.

Just like the `AssociativeBoth`

abstraction, if a data type with an `AssociativeEither`

instance is covariant there are additional operators we can define on it.

```
def orElse[F[+_]: AssociativeEither : Covariant, A](fa: => F[A], fb: => F[A]): F[A] =
fa.orElseEither(fb).map(_.merge)
```

The `orElse`

operator just combines two `F[A]`

values with `orElseEither`

and then maps the result to merge the left and right sides of the `Either`

. This is probably the version of the `orElse`

operator we are most familiar with.

We can also define additional operators if a data type that has a `AssociativeEither`

instance defined for it is contravariant.

```
def eitherWith[F[-_]: AssociativeEither : Contravariant, A, B, C](fa: F[A], fb: F[B])(
f: C => Either[A, B]
): F[C] =
fa.orElseEither(fb).contramap(f)
```

The `eitherWith`

operator first converts input of type `C`

into `Either[A, B]`

values with `contramap`

and the function `f`

, then runs the `fa`

and `fb`

values using that input and the `orElseEither`

operator.

For example, if our data type was a `Predicate`

the `eitherWith`

operator could split incoming payloads into one of two types, sending them to the appropriate predicate for evaluation and then returning the results. Of course, if we can handle a payload with two types in this way we can also handle payloads with any number of cases by repeatedly applying the `eitherWith`

operator.

The `AssociativeEither`

functional abstraction represents the second fundamental way of combining two values of a parameterized type. Whereas `AssociativeBoth`

combines the `A`

and `B`

values into the sum type represented by `(A, B)`

, `AssociativeEither`

combines them into the product type represented by `Either[A, B]`

.

For existing data types the `orElseEither`

operator and its variants tend to already be implemented, often with more domain specific names, so there isn't necessarily an immediate benefit if you are working with existing data types from ZIO or the Scala standard library.

However, if you are defining your own parameterized types it can be helpful to think about what it would mean for running a value to fail and what it would mean to run another value instead. There are also operators in ZIO Prelude that are defined on types with an `AssociativeEither`

instance, so implementing an instance for your own data type can let you take advantage of that functionality and test your implementation with the laws in ZIO Prelude.

Finally, the `AssociativeEither`

abstraction can be quite helpful in some cases for writing generic code in terms of the abstractions in ZIO Prelude.

The combination of the ability to express running the left value and then running the right value with `AssociativeBoth`

and running the left value and if it fails running the right value with `AssociativeEither`

can be quite powerful. For example, we can define many parsers in this way.