cats Documentation

Technical Documentation: typelevel/cats

ℹ️ Provenance: Multi-Tier Ingestion · CodeWiki Reference

Overview (`README.md`) Copy Section

Cats Copy Chapter

Overview Copy Section

Cats is a library which provides abstractions for functional programming in the Scala programming language.

Scala supports both object-oriented and functional programming, and this is reflected in the hybrid approach of the
standard library. Cats strives to provide functional programming abstractions that are core, binary compatible, modular, approachable and efficient. A broader goal of Cats is to provide a foundation for an ecosystem of pure, typeful libraries to support functional programming in Scala applications.

For more detail about Cats' motivations, go here.

Why "cats"? Copy Section

The name is a playful shortening of the word category, from "category theory".

Regardless, you do not need to know anything about category theory to use Cats.

Contributors Copy Chapter

Code Contributors Copy Section

This project exists thanks to all the people who contribute. We welcome contributions to Cats and would love for you to help build
Cats. See our contributor guide for more
information about how you can get involved as a developer. If you are looking for something to start with, here is a beginner friendly list.

Financial Contributors Copy Section

Become a financial contributor and help us sustain our community. Donations directly support office hours for maintainers, better documentation and strategic initiatives.

Platinum Sponsors

Gold Sponsors

Silver Sponsors

Backers

Other contributors

Getting Started Copy Section

Cats is available for Scala.js and Scala Native, as well as the standard JVM runtime.

Cats relies on improved type inference via the fix for SI-2712, which is not enabled by default. For Scala 2.12 you should add the following to your build.sbt:

scalacOptions += "-Ypartial-unification"

(Partial unification is on by default since Scala 2.13, the compiler no longer accepts -Ypartial-unification)

And then create the Cats dependency, by adding the following to your build.sbt:

libraryDependencies += "org.typelevel" %% "cats-core" % "2.9.0"

This will pull in the cats-core module. If you require some other
functionality, you can pick-and-choose from amongst these modules
(used in place of "cats-core"):

• cats-kernel: Small set of basic type classes (required).
• cats-core: Most core type classes and functionality (required).
• cats-laws: Laws for testing type class instances.
• cats-free: Free structures such as the free monad, and supporting type classes.
• cats-testkit: lib for writing tests for type class instances using laws.
• algebra: Type classes to represent algebraic structures.
• alleycats-core: Cats instances and classes which are not lawful.

There are several other Cats modules that are in separate repos so that they can
maintain independent release cycles.

• cats-effect: standard IO type together with Sync, Async and Effect type classes
• cats-mtl: transformer typeclasses for Cats' Monads, Applicatives and Functors.
• mouse: a small companion to Cats that provides convenient syntax (aka extension methods)
• kittens: automatic type class instance derivation for Cats and generic utility functions
• cats-tagless: Utilities for tagless final encoded algebras
• cats-collections: Data structures which facilitate pure functional programming
• cats-testkit-scalatest: Cats testkit integration with Scalatest

Past release notes for Cats are available in CHANGES.md.

Documentation Copy Section

Links:

1. Website: typelevel.org/cats/
2. ScalaDoc: typelevel.org/cats/api/
3. Type classes: typelevel.org/cats/typeclasses.html
4. Data types: typelevel.org/cats/datatypes.html
5. Algebra overview: typelevel.org/cats/algebra.html
6. Glossary: typelevel.org/cats/nomenclature.html
7. Resources for Learners: typelevel.org/cats/resources_for_learners.html
8. FAQ: typelevel.org/cats/faq.html
9. The Typelevel Ecosystem: typelevel.org/cats/typelevelEcosystem.html

Community Copy Section

Discussion around Cats is currently happening on GitHub issues, PR pages,
and Discord:

The Typelevel Discord has #cats and #cats-dev
channels, as well as community channels such as #beginners. Please join us!

People are expected to follow the
Typelevel Code of Conduct when
discussing Cats on GitHub, Discord, or other venues.

We hope that our community will be respectful, helpful, and kind. If
you find yourself embroiled in a situation that becomes heated, or
that fails to live up to our expectations, you should disengage and
contact one of the project maintainers in private. We
hope to avoid letting minor aggressions and misunderstandings escalate
into larger problems.

If you are being harassed, please contact one of us
immediately so that we can support you.

Binary compatibility and versioning Copy Section

After 1.0.0 release, we decided
to use MAJOR.MINOR.PATCH Semantic Versioning 2.0.0
going forward, which is different from the EPOCH.MAJOR.MINOR scheme common among
Java and Scala libraries (including the Scala lang).

Cats strives to provide a solid and stable foundation for an ecosystem of
FP libraries. Thus, we treat backward binary compatibility maintenance with a high priority.
In semantic versioning, backward breaking change is ONLY allowed between MAJOR versions.
We will maintain backward binary compatibility between PATCH AND MINOR versions.
For example, when we release Cats 1.1.0, it will be backward binary compatible
with the previous 1.0.x versions. I.E. the new JAR will be a drop-in replacement for
the old one. This is critical when your application has a diamond
dependency on Cats - depending on two or more libraries that all depend on Cats.
If one library upgrades to the new 1.1.0 Cats before the other one does, your
application still runs thanks to this backward binary compatibility.

Also worth noting is that according to semantic versioning,
MINOR version Y (x.Y.z | x > 0) MUST be incremented
if new, backwards compatible functionality is introduced to the public API.
It MUST be incremented if any public API functionality is marked as deprecated.

Any binary breaking changes will require a MAJOR version bump, which we will be very
cautious about. We will also consider using organization and package name for major
versioning in the future. But that decision is yet to be made.

Adopters Copy Section

A (non-exhaustive) list of companies that use Cats in production is featured in ADOPTERS.md. Don't see yours? You can add it in a PR! And if you can, consider supporting us.

Maintainers Copy Section

The current maintainers (people who can merge pull requests) are:

• rossabaker Ross Baker
• armanbilge Arman Bilge
• johnynek P. Oscar Boykin
• adelbertc Adelbert Chang
• danicheg Daniel Esik
• LukaJCB Luka Jacobowitz
• peterneyens Peter Neyens
• tpolecat Rob Norris
• non Erik Osheim
• barambani Filippo Mariotti
• mpilquist Michael Pilquist
• milessabin Miles Sabin
• djspiewak Daniel Spiewak
• fthomas Frank Thomas
• satorg Sergey Torgashov
• julien-truffaut Julien Truffaut
• kailuowang Kailuo Wang

Retired committers include:

• ceedubs Cody Allen
• travisbrown Travis Brown

We are currently following a practice of requiring at least two
sign-offs to merge code PRs (and for large or contentious issues we may
wait for more). For typos, documentation improvements or minor build fix we
relax this to a single sign-off. More detail in the process document.

Copyright and License Copy Section

All code is available to you under the MIT license, available at
http://opensource.org/licenses/mit-license.php and also in the
COPYING file. The design is informed by many other
projects, in particular Scalaz.

Copyright the maintainers, 2015-2025.

Overview (`scalafix/README.md`) Copy Section

Scalafix rules for cats

How to use Copy Chapter

1. Install the Scalafix sbt plugin

2. Run the rules appropriate to your Cats version (see below)

Migration to Cats v2.2.0 Copy Chapter

First configure the SemanticDB compiler plugin to enable synthetics:

ThisBuild / scalacOptions += "-P:semanticdb:synthetics:on"

Then run Scalafix:

sbt scalafixAll github:typelevel/cats/Cats_v2_2_0

Available rules Copy Section

• Type class instances are now available in implicit scope, so there is a rule to
  remove imports that are no longer needed

Migration to Cats v1.0.0 Copy Chapter

sbt scalafixAll github:typelevel/cats/Cats_v1_0_0

Available rules Copy Section

• All Unapply enabled methods, e.g. sequenceU, traverseU, etc. are removed. Unapply enabled syntax ops are also removed. Please use the partial unification SI-2712 fix instead. The easiest way might be this sbt-plugin.

• The creation methods (left, right, apply, pure, etc.) in EitherT were improved to take less type arguments.

• EitherT.liftT was renamed to EitherT.liftF

• the lift method on WriterT, StateT, RWST and Kleisli was renamed to liftF

• CartesianBuilder (i.e. |@|) syntax is deprecated, use the apply syntax on tuples instead. E.g. (x |@| y |@| z).map(...) should be replaced by (x, y, z).mapN(...)

• Free.suspend is renamed to Free.defer for consistency.

• traverse1_, intercalate1 and sequence1_ in Reducible were renamed to nonEmptyTraverse_, nonEmptyIntercalate and nonEmptySequence_ respectively.

• cats.free.Inject is moved from cats-free to cats-core and renamed to cats.InjectK; cats.data.Prod is renamed to cats.data.Tuple2K; cats.data.Coproduct is renamed to cats.data.EitherK

• Apply syntax on tuple (e.g. (x, y, z).map3(...)) was moved from cats.syntax.tuple._ to cats.syntax.apply._ and renamed to mapN, contramapN and imapN respectively.

• Apply methods forEffect and followedBy were renamed to productL and productR respectively. This also effects forEffectEval, followedByEval, forEffectPar, and followedByPar.

• Split is removed, and the method split is moved to Arrow. Note that only under CommutativeArrow does it guarantee the non-interference between the effects. see #1567

WIP Copy Section

• cats no longer publishes the all-inclusive bundle package "org.typelevel" % "cats", use cats-core, cats-free, or cats-law accordingly instead. If you need cats.free, use "org.typelevel" % "cats-free", if you need cats-laws use "org.typelevel" % "cats-laws", if neither, use "org.typelevel" % "cats-core".

• FunctorFilter, MonadCombine, MonadFilter, MonadReader, MonadState, MonadTrans, MonadWriter and TraverseFilter are no longer in cats, the functionalities they provided are inhereted by the new cats-mtl project. Please check here for migration guide.

• Several cats-core type class instances for cats.kernel were moved from their companion objects to separate traits and thus require imports from cats.instances.xxx._ (or the recommended import cats.implicits._) now. See #1659 for more details.

• foldLeftM is removed from Free, use foldM on Foldable instead, see #1117 for detail.

• iteratorFoldM was removed from Foldable due to #1716

To test the Scalafix rules Copy Chapter

cd scalafix
sbt test

Index (`docs/index.md`) Copy Section

Cats

Overview Copy Section

Cats is a library which provides abstractions for functional programming in the Scala programming language.

Scala supports both object-oriented and functional programming, and this is reflected in the hybrid approach of the
standard library. Cats strives to provide functional programming abstractions that are core, binary compatible, modular, approachable and efficient. A broader goal of Cats is to provide a foundation for an ecosystem of pure, typeful libraries to support functional programming in Scala applications.

For more detail about Cats' motivations, go here.

Why "cats"? Copy Section

The name is a playful shortening of the word category, from "category theory".

Regardless, you do not need to know anything about category theory to use Cats.

Contributors Copy Chapter

Code Contributors Copy Section

This project exists thanks to all the people who contribute. We welcome contributions to Cats and would love for you to help build
Cats. See our contributor guide for more
information about how you can get involved as a developer. If you are looking for something to start with, here is a beginner friendly list.

Financial Contributors Copy Section

Become a financial contributor and help us sustain our community. Donations directly support office hours for maintainers, better documentation and strategic initiatives.

Platinum Sponsors

Gold Sponsors

Silver Sponsors

Backers

Other contributors

Getting Started Copy Section

Cats is available for Scala.js and Scala Native, as well as the standard JVM runtime.

Cats relies on improved type inference via the fix for SI-2712, which is not enabled by default. For Scala 2.12 you should add the following to your build.sbt:

scalacOptions += "-Ypartial-unification"

(Partial unification is on by default since Scala 2.13, the compiler no longer accepts -Ypartial-unification)

And then create the Cats dependency, by adding the following to your build.sbt:

libraryDependencies += "org.typelevel" %% "cats-core" % "@VERSION@"

This will pull in the cats-core module. If you require some other
functionality, you can pick-and-choose from amongst these modules
(used in place of "cats-core"):

• cats-kernel: Small set of basic type classes (required).
• cats-core: Most core type classes and functionality (required).
• cats-laws: Laws for testing type class instances.
• cats-free: Free structures such as the free monad, and supporting type classes.
• cats-testkit: lib for writing tests for type class instances using laws.
• algebra: Type classes to represent algebraic structures.
• alleycats-core: Cats instances and classes which are not lawful.

There are several other Cats modules that are in separate repos so that they can
maintain independent release cycles.

• cats-effect: standard IO type together with Sync, Async and Effect type classes
• cats-mtl: transformer typeclasses for Cats' Monads, Applicatives and Functors.
• mouse: a small companion to Cats that provides convenient syntax (aka extension methods)
• kittens: automatic type class instance derivation for Cats and generic utility functions
• cats-tagless: Utilities for tagless final encoded algebras
• cats-collections: Data structures which facilitate pure functional programming
• cats-testkit-scalatest: Cats testkit integration with Scalatest

Past release notes for Cats are available in CHANGES.md.

Community Copy Section

Discussion around Cats is currently happening on GitHub issues, PR pages,
and Discord:

The Typelevel Discord has #cats and #cats-dev
channels, as well as community channels such as #beginners. Please join us!

People are expected to follow the
Typelevel Code of Conduct when
discussing Cats on GitHub, Discord, or other venues.

We hope that our community will be respectful, helpful, and kind. If
you find yourself embroiled in a situation that becomes heated, or
that fails to live up to our expectations, you should disengage and
contact one of the project maintainers in private. We
hope to avoid letting minor aggressions and misunderstandings escalate
into larger problems.

If you are being harassed, please contact one of us
immediately so that we can support you.

Binary compatibility and versioning Copy Section

After 1.0.0 release, we decided
to use MAJOR.MINOR.PATCH Semantic Versioning 2.0.0
going forward, which is different from the EPOCH.MAJOR.MINOR scheme common among
Java and Scala libraries (including the Scala lang).

Cats strives to provide a solid and stable foundation for an ecosystem of
FP libraries. Thus, we treat backward binary compatibility maintenance with a high priority.
In semantic versioning, backward breaking change is ONLY allowed between MAJOR versions.
We will maintain backward binary compatibility between PATCH AND MINOR versions.
For example, when we release Cats 1.1.0, it will be backward binary compatible
with the previous 1.0.x versions. I.E. the new JAR will be a drop-in replacement for
the old one. This is critical when your application has a diamond
dependency on Cats - depending on two or more libraries that all depend on Cats.
If one library upgrades to the new 1.1.0 Cats before the other one does, your
application still runs thanks to this backward binary compatibility.

Also worth noting is that according to semantic versioning,
MINOR version Y (x.Y.z | x > 0) MUST be incremented
if new, backwards compatible functionality is introduced to the public API.
It MUST be incremented if any public API functionality is marked as deprecated.

Any binary breaking changes will require a MAJOR version bump, which we will be very
cautious about. We will also consider using organization and package name for major
versioning in the future. But that decision is yet to be made.

Adopters Copy Section

A (non-exhaustive) list of companies that use Cats in production is featured on the Adopters page. Don't see yours? You can add it in a PR! And if you can, consider supporting us.

Maintainers Copy Section

The current maintainers (people who can merge pull requests) are:

• rossabaker Ross Baker
• armanbilge Arman Bilge
• johnynek P. Oscar Boykin
• adelbertc Adelbert Chang
• danicheg Daniel Esik
• LukaJCB Luka Jacobowitz
• peterneyens Peter Neyens
• tpolecat Rob Norris
• non Erik Osheim
• barambani Filippo Mariotti
• mpilquist Michael Pilquist
• milessabin Miles Sabin
• djspiewak Daniel Spiewak
• fthomas Frank Thomas
• satorg Sergey Torgashov
• julien-truffaut Julien Truffaut
• kailuowang Kailuo Wang

Retired committers include:

• ceedubs Cody Allen
• travisbrown Travis Brown

We are currently following a practice of requiring at least two
sign-offs to merge code PRs (and for large or contentious issues we may
wait for more). For typos, documentation improvements or minor build fix we
relax this to a single sign-off. More detail in the process document.

Copyright and License Copy Section

All code is available to you under the MIT license, available at
http://opensource.org/licenses/mit-license.php and also in the
COPYING file. The design is informed by many other
projects, in particular Scalaz.

Copyright the maintainers, 2015-2024.

Algebra (`docs/algebra.md`) Copy Section

{% laika.title = Algebra %}

Algebra Overview

Algebra uses type classes to represent algebraic structures. You can use these type classes to represent the abstract capabilities (and requirements) you want generic parameters to possess.

This section will explain the structures available.

algebraic properties and terminology Copy Chapter

We will be talking about properties like associativity and commutativity. Here is a quick explanation of what those properties mean:

Though these properties are illustrated with symbolic operators, they work equally-well with functions. When you see a ⊕ b that is equivalent to f(a, b): ⊕ is an infix representation of the binary function f, and a and b are values (of some type A).

Similarly, when you see ¬a that is equivalent to g(a): ¬ is a prefix representation of the unary function g, and a is a value (of some type A).

basic algebraic structures Copy Chapter

The most basic structures can be found in the algebra package. They all implement a method called combine, which is associative. The identity element (if present) will be called empty, and the inverse method (if present) will be called inverse.

(For a description of what each column means, see §algebraic properties and terminology.)

ring-like structures Copy Chapter

The algebra.ring package contains more sophisticated structures which combine an additive operation (called plus) and a multiplicative operation (called times). Additive identity and inverses will be called zero and negate (respectively); multiplicative identity and inverses will be called one and reciprocal (respectively).

All ring-like structures are associative for both + and *, have commutative +, and have a zero element (an identity for +).

(For a description of what the terminology in each column means, see §algebraic properties and terminology.)

lattice-like structures Copy Chapter

The algebra.lattice package contains more structures that can be somewhat ring-like. Rather than plus and times we have meet and join both of which are always associative, commutative and idempotent, and as such each can be viewed as a semilattice. Meet can be thought of as the greatest lower bound of two items while join can be thought of as the least upper bound between two items.

When zero is present, join(a, zero) = a. When one is present meet(a, one) = a.

When meet and join are both present, they obey the absorption law:

• meet(a, join(a, b)) = join(a, meet(a, b)) = a

Sometimes meet and join distribute, we say it is distributive in this case:

• meet(a, join(b, c)) = join(meet(a, b), meet(a, c))
• join(a, meet(b, c)) = meet(join(a, b), join(a, c))

Sometimes an additional binary operation imp (for impliciation, also written as →, meet written as ∧) is present. Implication obeys the following laws:

• a → a = 1
• a ∧ (a → b) = a ∧ b
• b ∧ (a → b) = b
• a → (b ∧ c) = (a → b) ∧ (a → c)

The law of the excluded middle can be expressed as:

• (a ∨ (a → 0)) = 1

Note that a BoundedDistributiveLattice gives you a CommutativeRig, but not the other way around: rigs aren't distributive with a + (b * c) = (a + b) * (a + c).

Also, a Bool gives rise to a BoolRing, since each element can be defined as its own negation. Note, Bool's .asBoolRing is not an extension of the .asCommutativeRig method as the plus operations are defined differently.

Documentation Help Copy Section

We'd love your help with this documentation! You can edit this page in your browser by clicking this link.

Alleycats (`docs/alleycats.md`) Copy Section

Alleycats

Overview Copy Chapter

Alleycats is a module of the Cats
project that exists to support types which are not entirely savory or
law-abiding but which may prove useful or necessary in some
situations.

In some cases, a type class instance can almost (but not quite) obey
the required laws (e.g. a Monad instance for scala.util.Try). In
other cases, type classes which lack laws or constraints may still be
useful in some cases (e.g. Empty[_], a type class which provides
some notion of "emptiness").

Rather than argue about whether to permit these types in Cats proper, we
provide a (slightly disreputable) home for them here.

Type classes Copy Chapter

Alleycats introduces several new type classes. Here is an overview of
the instances introduced.

Empty\[A\], Zero\[A\], and One\[A\] Copy Section

A commonly-requested type class is one that encodes the idea of a set
having an identity element. Normally this would be done by defining a
Monoid[A] instance, but in some cases the idea of emptiness is
independent of a particular associative operation.

In this case, Empty[A] may be used in place of Monoid[A]. It
provides access to the identity element (via the .empty method),
and can also provide .isEmpty and .nonEmpty if an Eq[A] is
available.

The two other type classes, Zero[A] and One[A], are similar,
except they correspond to AdditiveMonoid[A] and
MultiplicativeMonoid[A] (found in the algebra.ring package). Their
methods are called zero and one, respectively.

While none of these type classes have their own laws, they are
required not to violate the monoid laws when applicable. This means
that if Empty[A] and Semigroup[A] are both available, that
Empty[A].empty must function as an identity element for
Semigroup[A].combine. In fact, together these instances can be
viewed as a Monoid[A] (and there is an implicit method to that
effect).

The same rules apply to Zero[A] and One[A] and their respective
associative operations.

Pure\[F\[\_\]\] and Extract\[F\[\_\]\] Copy Section

The Pure[F] type class represents the pure method of
Applicative[F] separated from its map and ap methods. Like the
previous type classes, if Pure[F] and Apply[F] are both available
they are required to be consistent (and should provide a valid
Applicative[F] instance).

Similarly, Extract[F] represents the extract method of
Comonad[F] without coflatMap and map methods. When Extract[F]
and CoflatMap[F] are available, they should provide a valid
Comonad[F] instance.

EmptyK\[F\[\_\]\] Copy Section

Finally, EmptyK[F] generalizes the empty[A] method from
MonoidK[F]. The pattern here is the same as before --
SemigroupK[F] and EmptyK[F] should provide a valid MonoidK[F]
instance.

Instances Copy Chapter

Alleycats also provides some "disreputable" type class instances.

Set\[\_\] instances Copy Section

Scala's Set[_] takes advantage of the universal availability of
.hashCode and .equals. This makes it difficult to use
parametricity
to reason about sets, and casts some doubt on their use with functors
and monads.

Alleycats provides Monad[Set] and Traverse[Set]. You can import
these instances via import alleycats.std.set._.

Try\[\_\] instances Copy Section

Scala's Try[_] is intended to replace the need for try { ... } catch { ... } syntax in Scala programs, to ease error-handling, and
to transport exceptions as data. Due to the way Try transparently
catches exceptions in .map and .flatMap, some people are skeptical
that Try fulfills the necessary functor/monad laws.

Alleycats provides a Monad[Try]. You can import this instance via
import alleycats.std.try_._.

Iterable\[\_\] instances Copy Section

Scala's collection.Iterable[_] offers no guarantees that it's immutable,
since it abstracts over the mutable and immutable variants. However it's
the type used to represent a Maps values, and its often desirable to treat the
values of a map as a Foldable collection. Alleycats provides a Foldable[Iterable], eg:

import cats.syntax.all._
import alleycats.std.iterable._

// Result "AppleOrange"
Map(1 -> "Apple", 2 -> "Orange").values.combineAll

Contributing Copy Chapter

This module's goal is to be very liberal about accepting type class
instances, but to only provide instances which are absent from
Cats proper. Law-abiding instances will end up in Cats, and everything else will
end up here.

Colophon (`docs/colophon.md`) Copy Section

Colophon

Cats has been made a much better project, and is a much more enjoyable
project to work on because of many of the other projects on which Cats
is built. Many of these projects have had enhancements made in order
to benefit Cats, for which we are grateful.

We would like to thank the maintainers of these supporting projects,
and we'd encourage you to check out these projects and consider
integrating them into your own projects.

• scalacheck for property-based testing
• discipline for encoding and testing laws
• kind-projector for type lambda syntax
• mdoc type-checked example code makes sure that our examples stay in sync with the rest of our source

There are other libraries that aim to foster Functional Programming in the Scala programming language which Cats has a relationship to:

• scalaz The project which directly inspires Cats. Currently Cats borrows some code directly from scalaz.
• Structures A project very similar in
  nature to Cats, also derived from scalaz. The Structures and Cats
  projects have had a healthy relationship of sharing both ideas and code.

For a full list of Cats and Typelevel related projects and libraries, take a look at The Typelevel Ecosystem

Datatypes (`docs/datatypes.md`) Copy Section

{% laika.title = "Data Types" %}

@:navigationTree {
entries = [ { target = "datatypes", depth = 2 } ]
}

Faq (`docs/faq.md`) Copy Section

{% laika.title = FAQ %}

Frequently Asked Questions

@:navigationTree {
entries = [ { target = "faq.md", depth = 2 } ]
}

What imports do I need? Copy Chapter

The easiest approach to Cats imports is to import everything that's commonly needed:

import cats._
import cats.data._
import cats.syntax.all._

This should be all that you need, but if you'd like to learn more about the details of imports than you can check out the import guide.

I am new to pure functional programming, what quick wins can I get from Cats? Copy Chapter

Please refer to the jump start guide.

What is the difference between Cats and Scalaz? Copy Chapter

Cats and Scalaz have the same goal: to facilitate pure functional programming in Scala applications. However the underlying core strategy is different; Scalaz took the approach of trying to provide a single batteries-included standard library for FP that powers the Scala applications. Cats, on the other hand, aims to help build an ecosystem of pure FP libraries by providing a solid and stable foundation; these libraries can have their own styles and personalities, competing with each other, while at the same time playing nice. It is through this ecosystem of FP libraries (cats included) that Scala applications can be powered with "FP awesome-ness" and beyond by picking whatever best fit their needs.

Based on this core strategy, Cats takes a modular approach and focuses on providing core, binary compatible, approachable and efficient abstractions. It provides a welcoming and supportive environment for the user community governed by the Typelevel Code of Conduct. It also takes great effort in supplying a comprehensive and beginner-friendly documentation.

Where is right-biased Either? Copy Chapter

Up through Cats 0.7.x we had cats.data.Xor, which was effectively scala.util.Either, but right-biased by default and with
a bunch of useful combinators around it. In Scala 2.12.x Either
became right-biased so we revisited the use of Xor and
decided that in the interest of interoperability, we would remove Xor in the Cats 0.8.0 release and
fill in the gaps in the scala.util.Either API via
syntax enrichment.

This syntax and the type class instances for Either can be imported using cats.syntax._, which will also bring in syntactic enrichment and instances for other standard library types, or you can import only the Either enrichment with cats.syntax.either._.

There are a few minor mismatches between Xor and Either. For example, in some cases you may need to specify a type parameter for an enrichment method on Either (such as leftMap) even though it was properly inferred for Xor, due to Either having covariant type parameters.

Similarly, cats.data.XorT has been replaced with cats.data.EitherT, although since this is a type defined in Cats, you don't need to import syntax or instances for it (although you may need imports for the underlying monad).

Why is the compiler having trouble with types with more than one type parameter? Copy Chapter

When you encounter a situation where the same code works fine with a type with one type parameter, e.g. List[A], but doesn't work with types with more than one, e.g. Either[A, B], you probably hit SI-2712. Without going into the details, it's highly recommended to enable a partial SI-2712 fix in your project. The easiest way to achieve that is through this sbt plugin.
Cats used to provide mitigation to this issue semi-transparently, but given the fact that the fix is now mainstream, we decided to drop that mitigation machinery in favor of reducing the complexity. See this issue for details.

Why is some example code not compiling for me? Copy Chapter

A portion of example code requires either the Kind-projector compiler plugin or partial unification turned on in scalac. The easiest way to turn partial unification on is through this sbt plugin.

Why can't the compiler find implicit instances for Future? Copy Chapter

If you have already followed the imports advice but are still getting error messages like could not find implicit value for parameter e: cats.Monad[scala.concurrent.Future] or value |+| is not a member of scala.concurrent.Future[Int], then make sure that you have an implicit scala.concurrent.ExecutionContext in scope. The easiest way to do this is to import scala.concurrent.ExecutionContext.Implicits.global, but note that you may want to use a different execution context for your production application.

Where are implicit instances for `Seq`? Copy Chapter

As of cats-2.3, instances for collection.immutable.Seq are provided by cats.
Mind that, up to scala-2.12, Seq was an alias for collection.Seq and lawful instances can't be provided for it due to its potential mutability.
In scala-2.13, Seq was changed to collection.immutable.Seq which greatly improves Seq's interoperability with cats.

How can I turn my List of `` into a `` of a list? Copy Chapter

It's really common to have a List of values with types like Option, Either, or Validated that you would like to turn "inside out" into an Option (or Either or Validated) of a List. The sequence and traverse methods are really handy for this. You can read more about them in the Traverse documentation.

Where is ListT? Copy Chapter

There are monad transformers for various types, such as OptionT, so people often wonder why there isn't a ListT. For example, in the following example, people might reach for ListT to simplify making nested map and exists calls:

val l: Option[List[Int]] = Some(List(1, 2, 3, 4, 5))

def isEven(i: Int): Boolean = i % 2 == 0

l.map(_.map(_ + 1))
l.exists(_.exists(isEven))

A naive implementation of ListT suffers from associativity issues; see this gist for an example. It's possible to create a ListT that doesn't have these issues, but it tends to be pretty inefficient. For many use-cases, Nested can be used to achieve the desired results.

Here is how we could achieve the effect of the previous example using Nested:

import cats.data.Nested
import cats.syntax.all._

val nl = Nested(l)
nl.map(_ + 1)
nl.exists(isEven)

We can even perform more complicated operations, such as a traverse of the nested structure:

import cats.data.ValidatedNel
type ErrorsOr[A] = ValidatedNel[String, A]
def even(i: Int): ErrorsOr[Int] = if (i % 2 == 0) i.validNel else s"$i is odd".invalidNel

nl.traverse(even)

Where are `Applicative`s for monad transformers? Copy Chapter

An Applicative instance for OptionT[F, *]/EitherT[F, E, *], built without a corresponding Monad instance for F, would be unlawful, so it's not included. See the guidelines for a more detailed explanation.

As an alternative, using .toNested on the monad transformer is recommended, although its ap will still be inconsistent with the Monad instance's.`.

Where is IO/Task? Copy Chapter

In purely functional programming, a monadic IO or Task type is often used to handle side effects such as file/network IO. In some languages and frameworks, such a type also serves as the primary abstraction through which parallelism is achieved. Nearly every real-world purely functional application or service is going to require such a data type, and this gives rise to an obvious question: why doesn't Cats include such a type?

The answer is that Cats does include an IO, it just isn't included in the core library. The decision was made to split IO away from cats-core and (indeed the whole Cats release cycle!) in order to make it easier to ensure modular versioning and compatibility across the ecosystem. The cats-effect project defines a type, cats.effect.IO, which is intended to be a very minimal, very performant data type for managing synchronous and asynchronous side-effects, integrated into the Cats ecosystem.

However, we acknowledge that this type may not meet everyone's needs. The cats-effect project characterizes the space of side-effect-capturing data types with a set of typeclasses (deriving from cats.Monad), and so all such data types are, broadly-speaking, mutually compatible and interchangeable in many generic contexts. For example, Monix provides support for IO, concurrency, and streaming and integrates with the cats-effect type classes.

It may be worth keeping in mind that IO and Task are pretty blunt instruments (they are essentially the Any of side effect management), and you may want to narrow the scope of your effects throughout most of your application. The free monad documentation describes a way to abstractly define controlled effects and interpret them into a type such as IO or Task as late as possible. As more of your code becomes pure through these controlled effects the less it matters which type you end up choosing to represent your side effects.

What do types like `?` and `λ` mean? Copy Chapter

Cats defines a wealth of type classes and type class instances. For a number of the type class and instance combinations, there is a mismatch between the type parameter requirements of the type class and the type parameter requirements of the data type for which the instance is being defined. For example, the Either data type is a type constructor with two type parameters. We would like to be able to define a Monad for Either, but the Monad type class operates on type constructors having only one type parameter.

Enter type lambdas! Type lambdas provide a mechanism to allow one or more of the type parameters for a particular type constructor to be fixed. In the case of Either then, when defining a Monad for Either, we want to fix one of the type parameters at the point where a Monad instance is summoned, so that the type parameters line up. As Either is right biased, a type lambda can be used to fix the left type parameter and allow the right type parameter to continue to vary when Either is treated as a Monad.

Enter kind-projector! kind-projector is a compiler plugin which provides a convenient syntax for dealing with type lambdas. The symbols ? and λ are treated specially by kind-projector, and expanded into the more verbose definitions that would be required were it not to be used. You can read more about kind-projector at the project page.

What is `tailRecM`? Copy Chapter

The FlatMap type class has a tailRecM method with the following signature:

def tailRecM[A, B](a: A)(f: A => F[Either[A, B]]): F[B]

When you are defining a FlatMap instance, its tailRecM implementation must have two properties in order for the instance to be considered lawful. The first property is that tailRecM must return the same result that you would get if you recursively called flatMap until you got a Right value (assuming you had unlimited stack space—we'll get to that in a moment). In other words, it must give the same result as this implementation:

trait Monad[F[_]] {
  def pure[A](x: A): F[A] = ???
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B] = ???

  def tailRecM[A, B](a: A)(f: A => F[Either[A, B]]): F[B] =
    flatMap(f(a)) {
      case Right(b) => pure(b)
      case Left(nextA) => tailRecM(nextA)(f)
    }
}

The reason we can't simply use this implementation for all type constructors (and the reason that tailRecM is useful at all) is that for many monadic types, recursively flatMap-ing in this way will quickly exhaust the stack.

Option is one example of a monadic type whose flatMap consumes stack in such a way that nesting flatMap calls deeply enough (usually around a couple thousand levels) will result in a stack overflow. We can provide a stack-safe tailRecM implementation for Option, though:

import cats.FlatMap
import scala.annotation.tailrec

implicit val optionFlatMap: FlatMap[Option] = new FlatMap[Option] {
  def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
  def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = fa.flatMap(f)

  @tailrec
  def tailRecM[A, B](a: A)(f: A => Option[Either[A, B]]): Option[B] = f(a) match {
    case None => None
    case Some(Left(a1)) => tailRecM(a1)(f)
    case Some(Right(b)) => Some(b)
  }
}

Now we don't have to worry about overflowing the stack, no matter how many times we have to call tailRecM before we get a Right.

This is useful because any operation that you would write using recursive flatMaps can be rewritten to use tailRecM, and if the FlatMap instance for your type constructor is lawful, you don't have to worry about stack safety.

The downside is that how you write a lawful tailRecM for your type constructor may not always be obvious. For some type constructors, such as Future, recursively flatMap-ing is already safe, and the first simple implementation above will be lawful. For types like Option and Try, you'll need to arrange the recursion in such a way that the tailRecM calls are tail calls (which you can confirm with Scala's tailrec annotation). Collection types require yet another approach (see for example the implementation for List).

If you're having trouble figuring out how to implement tailRecM lawfully, you can try to find an instance in Cats itself for a type that is semantically similar to yours (all of the FlatMap instances provided by Cats have lawful, stack-safe tailRecM implementations).

In some cases you may decide that providing a lawful tailRecM may be impractical or even impossible (if so we'd like to hear about it). For these cases we provide a way of testing all of the monad laws except for the stack safety of tailRecM: just replace MonadTests[F].monad[A, B, C] in your tests with MonadTests[F].stackUnsafeMonad[A, B, C].

What does this symbol mean? Copy Chapter

Below is a list of symbols used in Cats.

The ~>, ⊥, ⊤, :<: and :≺: symbols can be imported with import cats._.

All other symbols can be imported with import cats.syntax.all._

How can I test instances against their type classes' laws? Copy Chapter

You can find more information here.

How can I help? Copy Chapter

The Сats community welcomes and encourages contributions, even if you are completely new to Сats and functional programming. Here are a few ways to help out:

• Find an undocumented method and write a ScalaDoc entry for it. See Arrow.scala for some examples of ScalaDoc entries that use sbt-doctest.
• Find an open issue, leave a comment on it to let people know you are working on it, and submit a pull request. If you are new to Сats, you may want to look for items with the low-hanging-fruit label.

See the contributing guide for more information.

How to try Cats in a REPL? Copy Chapter

The easiest way is probably using Ammonite-REPL. Install it following the instructions there. Then in the amm console you can type in

// interp.configureCompiler(_.settings.YpartialUnification.value = true) // If using scala 2.11 or 2.12
import $ivy.`org.typelevel::cats-core:2.1.1`, cats._, cats.data._, cats.implicits._

Or if you want, you can add these lines to ~/.ammonite/predef.sc so that they are enabled every ammonite session.

Why aren't monad transformers like `OptionT` and `EitherT` covariant like `Option` and `Either`? Copy Chapter

Please see Variance of Monad Transformers on the Typelevel blog.

Why isn't `Set` a lawful `Functor` (and hence `Applicative`, `Monad`, etc.)? Copy Chapter

Although in many cases Set can behave as a Functor indeed, there are some edge cases where it doesn't.
For example, Set can violate the "covariant composition" law of Functor, which is:

fa.map(f).map(g) <-> fa.map(f.andThen(g))

Since Set is internally based on universal hashing and equality, it violates this law when used with a data type that
overrides equals and hashCode in a such a way that its instances may appear equal but de-facto contain different
values. One example of this type is scala.concurrent.duration.Duration:

import scala.concurrent.duration.*

val f: String => Duration = Duration.apply
val g: Duration => String = _.toString

val set = Set("1 minute", "60 seconds", "60000 milliseconds")

set.map(f).map(g) // ==> Set("1 minute")
set.map(f.andThen(g)) // ==> Set("1 minute", "60 seconds", "60000 milliseconds")

Another good real-world example to be aware of is CIString.

That said, there's a Monad[Set] instance in the Alleycats
module, which you can use on your own risk if you are sure about data types you are working with.

Guidelines (`docs/guidelines.md`) Copy Section

Guidelines

All guidelines in Сats should have clear justifications. There is no room for tribal wisdom in a simple library.

Syntax Copy Chapter

Composing Implicit Conversions in Traits Copy Section

Implicit syntax conversions provided in publicly-exposed traits should be marked final
so that any composition of the traits provides conversions that can all be inlined.

Ops Classes Copy Section

Ops classes should be marked final and extend AnyVal, to take full advantage of inlining and prevent unnecessary allocations.

The most notable exception is the case where all of the ops in the class are provided by zero-cost macros anyway,
for example with Simulacrum.

Partially-Applied Type Copy Section

In Scala, when there are multiple type parameters in a function, either scalac infers all type parameters or the user has to
specify all of them. Often we have functions where there are one or more types that are inferable but not all of them. For example, there is helper function in OptionT that creates an OptionT[F, A] from an A. It could be written as:

import cats._
import cats.syntax.all._
import cats.data.OptionT

def pure[F[_], A](a: A)(implicit F: Applicative[F]): OptionT[F, A] =
  OptionT(F.pure(Some(a)))


pure[List, Int](1)

Note that the type A should've been given by the a: A argument, but since scalac cannot infer F[_], the user still has to specify all type params.
In Сats, we use a technique described in
Rob Norris’s Kinda-Curried Type Parameters to overcome this restriction of scala inference. Here is a version of the pure using this technique in Сats.

package cats.data

object OptionT {

  private[data] final class PurePartiallyApplied[F[_]](val dummy: Boolean = true ) extends AnyVal {
    def apply[A](value: A)(implicit F: Applicative[F]): OptionT[F, A] =
      OptionT(F.pure(Some(value)))
  }

  def pure[F[_]]: PurePartiallyApplied[F] = new PurePartiallyApplied[F]
}

We introduced an intermediate or, as the name suggested, type parameter partially applied type PurePartiallyApplied to divide the function into two steps: the first step is a construction of the partially applied type, for which the type F[_] is given by the user; the second step is the apply method inside partially applied type, for which the A can be inferred from the argument. Now we can write:

OptionT.pure[List](1)

The user doesn't need to specify the type A which is given by the parameter.

You probably noticed that there is a val dummy: Boolean in the PurePartiallyApplied class. This is a trick we used
to make this intermediate class a Value Class so that there is no cost of allocation, i.e. at runtime, it doesn't create an instance of PurePartiallyApplied. We also hide this partially applied class by making it package private and placing it inside an object.

Implicit naming Copy Section

In a widely-used library it's important to minimize the chance that the names of implicits will be used by others and
therefore name our implicits according to the following rules:

• Implicits should start with "cats" followed by the package name (where the instance is defined).
• If the package contains instances leave instances out.
• The type and the type class should be mentioned in the name.
• If the instance is for multiple type classes, use InstancesFor instead of a type class name.
• If the instance is for a standard library type add Std after the package. i.e. catsStdShowForVector and catsKernelStdGroupForTuple.

As an example, an implicit instance of Monoid for List defined in the package Kernel should be named catsKernelStdMonoidForList.

This rule is relatively flexible. Use what you see appropriate. The goal is to maintain uniqueness and avoid conflicts.

Implicit instance priority Copy Section

When there are multiple instances provided implicitly, if the type class of them are in the same inheritance hierarchy,
the instances need to be separated out into different abstract class/traits so that they don't conflict with each other. The names of these abstract classes/traits should be numbered with a priority with 0 being the highest priority. The abstract classes/trait
with higher priority inherits from the ones with lower priority. The most specific (whose type class is the lowest in the hierarchy) instance should be placed in the abstract class/ trait with the highest priority. Here is an example.

trait Functor[F[_]]


trait Monad[F[_]] extends Functor

...
object Kleisli extends KleisliInstance0

abstract class KleisliInstance0 extends KleisliInstance1 {
  implicit def catsDataMonadForKleisli[F[_], A]: Monad[Kleisli[F, A, *]] = ...
}

abstract class KleisliInstance1 {
  implicit def catsDataFunctorForKleisli[F[_], A]: Functor[Kleisli[F, A, *]] = ...
}

Type classes that ONLY define laws. Copy Section

We can introduce new type classes for the sake of adding laws that don't apply to the parent type class, e.g. CommutativeSemigroup and
CommutativeArrow.

Applicative instances for monad transformers Copy Section

We explicitly don't provide an instance of Applicative for e.g. EitherT[F, String, *] given an Applicative[F].
An attempt to construct one without a proper Monad[F] instance would be inconsistent in ap with the provided Monad instance
for EitherT[F, String, *]. Such an instance will be derived if you use Nested instead:

import cats._, cats.data._, cats.implicits._

val a = EitherT(List(Left("err"), Right(1)))
val x = (a *> a).value
> x: List[Either[String, Int]] = List(Left("err"), Left("err"), Right(1))

val y = (a.toNested *> a.toNested).value
> y: List[Either[String, Int]] = List(Left("err"), Left("err"), Left("err"), Right(1))

x === y
> false

Classes extending AnyVal Copy Section

AnyVal-extending class constructor parameters must be marked as private.

Imports (`docs/imports.md`) Copy Section

Imports

The easiest approach to Сats imports is to import everything that's commonly needed:

import cats._
import cats.data._
import cats.syntax.all._

The cats._ import brings in quite a few type classes (similar to interfaces) such as Monad, Semigroup, and Foldable. Instead of the entire cats package, you can import only the types that you need, for example:

import cats.Monad
import cats.Semigroup
import cats.Foldable

The cats.data._, import brings in data structures such as Validated and State. Instead of the entire cats.data package, you can import only the types that you need, for example:

import cats.data.Validated
import cats.data.State

The cats.syntax.all._ import adds syntax enrichment onto certain types to provide some handy methods such as right-biased Either combinators:

import cats.syntax.all._

// Сats adds right-biased combinators to the standard library's Either
val e: Either[String, Int] = Right(3)
e.map(_ + 1)

// cats adds an orEmpty method to the standard library's Option
val o: Option[String] = None
o.orEmpty

If you'd like to import à la carte, you can do so, by importing from cats.syntax for syntax enrichment.
For example, if you'd like to import the Semigroup syntax:

import cats.syntax.semigroup._

"Hello, " |+| "World!"

The import adds the |+| syntax.

Note: Beware that if you import a type class instance or its syntax twice, you will receive conflicting implicits with a less than helpful error message.
This usually happens when importing different type classes in the same hierarchy or when importing syntax enrichment for all type classes using cats.syntax.all._ or cats.implicits._ together with a more specific import like cats.syntax.option._ or cats.instances.either._.
Below is an example of this phenomenon:

import cats.syntax.all._

1 |+| 2

import cats.syntax.semigroup._

3 |+| 5 // error: value |+| is not a member of Int

Compilation fails on the second invocation of |+| because we now have conflicting implicits from Semigroup.

Jump Start Guide (`docs/jump_start_guide.md`) Copy Section

{% laika.title = Jump Start Guide %}

Introduction

This jump start guide barely scratches the surface of what Cats can do, but instead provides a concise hands-on introduction to the patterns you're most likely to take advantage of in your Scala project.
If you're using the constructs like Future,
Option or
Either on a daily basis,
it's very likely that Cats can simplify and improve the readability of your code.

Please refer to the wiki on GitHub for guidelines on how to add the library to your project dependencies.
We are sticking to version 2.13.0 in the entire post.

Let's go through the library package-wise, looking at the syntax available in each package.

Option Helpers

import cats.syntax.all._

Importing this package enables obj.some syntax — equivalent to Some(obj).
The only real difference is that the value is already upcast to Option[T] from Some[T].

Using obj.some instead of Some(obj) can sometimes e.g. improve readability when you need to provide dummy implementation for service methods for the purpose of testing.
For example, if you put the following implicit class into the scope:

import scala.concurrent.Future

implicit class ToFutureSuccessful[T](obj: T) {
  def asFuture: Future[T] = Future.successful(obj)
}

then you can use the chained syntax shown below:

class Account { /* ... */ }

trait AccountService {
  def getAccountById(id: Int): Future[Option[Account]]
}

class DummyAccountServiceImpl extends AccountService {

  def dummyAccount: Account = ???

  /* ... */
  override def getAccountById(id: Int): Future[Option[Account]] = dummyAccount.some.asFuture
  /* ... */
}

That's more readable than Future.successful(Some(dummyAccount)), especially if this pattern repeats frequently.
Chaining .some.asFuture at the end rather than putting it at the front also helps focus on what's actually being returned rather than on the expected wrapper type.

none[T], in turn, is shorthand for Option.empty[T] which is just None, but already upcast from None.type to Option[T].
Providing a more specialized type sometimes helps the Scala compiler properly infer the type of expressions containing None.

Either Helpers

import cats.syntax.all._

obj.asRight is Right(obj), obj.asLeft is Left(obj).
In both cases the type of returned value is widened from Right or Left to Either.
Just as was the case with .some, these helpers are handy to combine with .asFuture to improve readability:

case class User(accountId: Long) { /* ... */ }

trait UserService {
  def ensureUserExists(id: Int): Future[Either[Exception, User]]
}

class UserServiceSpec extends UserService {

  def dummyUser: User = ???

  /* ... */
  override def ensureUserExists(id: Int): Future[Either[Exception, User]] = dummyUser.asRight.asFuture // instead of Future.successful(Right(dummyUser))
  /* ... */
}

Either.fromOption(option: Option[A], ifNone: => E), in turn, is a useful helper for converting an Option to an Either.
If the provided option is Some(x), it becomes Right(x).
Otherwise it becomes Left with the provided ifNone value inside.

Tuples

The apply package provides (..., ..., ...).mapN syntax, which allows for an intuitive construct for applying a function that takes more than one parameter to multiple effectful values (like futures).

Let's say we have 3 futures, one of type Int, one of type String, one of type User and a method accepting three parameters — Int, String and User.

import scala.concurrent.ExecutionContext.Implicits.global

class ProcessingResult { /* ... */ }

def intFuture: Future[Int] = { /* ... */ ??? }
def stringFuture: Future[String] = { /* ... */ ??? }
def userFuture: Future[User] = { /* ... */ ??? }

def process(value: Int, contents: String, user: User): ProcessingResult = { /* ... */ ??? }

Our goal is to apply the function to the values computed by those 3 futures.
With apply syntax this becomes very easy and concise:

import cats.syntax.all._

def processAsync: Future[ProcessingResult] = {
  (intFuture, stringFuture, userFuture).mapN {
    (value, contents, user) =>
      process(value, contents, user)
  }
}

By default the implicit instances (namely, Functor[Future] and
Semigroupal[Future]) required for mapN to work properly are always visible. They are present in the respective companion objects of the instances and hence we do not need to import them explicitly.

This above idea can be expressed even shorter, just:

def processAsync2: Future[ProcessingResult] = (intFuture, stringFuture, userFuture).mapN(process)

If any of the chained futures fails, the resulting future will also fail with the same exception as the first failing future in the chain (this is fail-fast behavior).

What's important, all futures will run in parallel, as opposed to what would happen in a for comprehension:

def processAsync3: Future[ProcessingResult] = {
  for {
    value <- intFuture
    contents <- stringFuture
    user <- userFuture
  } yield process(value, contents, user)
}

In the above snippet (which under the hood translates to flatMap and map calls), stringFuture will not run until intFuture is successfully completed,
and in the same way userFuture will be run only after stringFuture completes.
But since the computations are independent of one another, it's perfectly viable to run them in parallel with mapN instead.

Traversing

import cats.syntax.all._

`traverse` Copy Chapter

If you have an instance obj of type F[A] that can be mapped over (like Future) and a function fun of type A => G[B], then calling obj.map(fun) would give you F[G[B]].
In many common real-life cases, like when F is Option and G is Future, you would get Option[Future[B]], which most likely isn't what you wanted.

traverse comes as a solution here.
If you call traverse instead of map, like obj.traverse(fun), you'll get G[F[A]], which will be Future[Option[B]] in our case; this is much more useful and easier to process than Option[Future[B]].

def updateUser(user: User): Future[User] = { /* ... */ ??? }

def updateUsers(users: List[User]): Future[List[User]] = {
  users.traverse(updateUser)
}

As a side note, there is also a dedicated method Future.traverse in the Future companion object,
but the Cats version is far more readable and can easily work on any structure for which certain type classes are available.

`sequence` Copy Chapter

sequence represents an even simpler concept: it can be thought of as simply swapping the types from F[G[A]] to G[F[A]] without even mapping the enclosed value like traverse does.

val foo: List[Future[String]] = List(Future("hello"), Future("world"))
val bar = foo.sequence // will have Future[List[String]] type

obj.sequence is in fact implemented in Cats as obj.traverse(identity).

On the other hand, obj.traverse(fun) is roughly equivalent to obj.map(fun).sequence.

`flatTraverse` Copy Chapter

If you have an obj of type F[A] and a function fun of type A => G[F[B]], then doing obj.map(f) yields result of type F[G[F[B]]] — very unlikely to be what you wanted.

Traversing the obj instead of mapping helps a little — you'll get G[F[F[B]] instead.
Since G is usually something like Future and F is List or Option, you would end up with Future[Option[Option[A]] or Future[List[List[A]]] — a bit awkward to process.

lazy val valueOpt: Option[Int] = { /* ... */ ??? }
def compute(value: Int): Future[Option[Int]] = { /* ... */ ??? }
def computeOverValue: Future[Option[Option[Int]]] = valueOpt.traverse(compute) // has type Future[Option[Option[Int]]], not good

The solution could be to map the result with a _.flatten call like:

def computeOverValue2: Future[Option[Int]] = valueOpt.traverse(compute).map(_.flatten)

and this way you'll get the desired type G[F[B]] at the end.

However, there is a neat shortcut for this called flatTraverse:

def computeOverValue3: Future[Option[Int]] = valueOpt.flatTraverse(compute)

and that solves our problem for good.

Monad Transformers

OptionT Copy Chapter

import cats.data.OptionT

An instance of OptionT[F, A] can be thought of as a wrapper over F[Option[A]]
which adds a couple of useful methods specific to nested types that aren't available in F or Option itself.
Most typically, your F will be Future (or sometimes slick's DBIO, but this requires having an implementation of Cats type classes like Functor or Monad for DBIO).
Wrappers such as OptionT are generally known as monad transformers.

A quite common pattern is mapping the inner value stored inside an instance of F[Option[A]] to an instance of F[Option[B]] with a function of type A => B.
This can be done with rather verbose syntax like:

lazy val resultFuture: Future[Option[Int]] = ???

def mappedResultFuture: Future[Option[String]] = resultFuture.map { maybeValue =>
  maybeValue.map { value =>
    // Do something with the value and return String
    ???
  }
}

With the use of OptionT, this can be simplified as follows:

def mappedResultFuture2: OptionT[Future, String] = OptionT(resultFuture).map { value =>
  // Do something with the value and return String
  ???
}

The above map will return a value of type OptionT[Future, String].

To get the underlying Future[Option[String]] value, simply call .value on the OptionT instance.
It's also a viable solution to fully switch to OptionT[Future, A] in method parameter/return types and completely (or almost completely) ditch Future[Option[A]] in type declarations.

There are several ways to construct an OptionT instance.
The method headers in the table below are slightly simplified: the type parameters and type classes required by each method are skipped.

In production code you'll most commonly use the OptionT(...) syntax in order to wrap an instance of Future[Option[A]] into OptionT[F, A].
The other methods, in turn, prove useful to set up OptionT-typed dummy values in unit tests.

We have already come across one of OptionT's methods, namely map.
There are several other methods available and they mostly differ by the signature of the function they accept as the parameter.
As was the case with the previous table, the expected type classes are skipped.

In practice, you're most likely to use map and semiflatMap.

As is always the case with flatMap and map, you can use it not only explicitly, but also under the hood in for comprehensions, as in the example below:

class Money { /* ... */ }

def findUserById(userId: Long): OptionT[Future, User] = { /* ... */ ??? }

def findAccountById(accountId: Long): OptionT[Future, Account] = { /* ... */ ??? }

def getReservedFundsForAccount(account: Account): OptionT[Future, Money] = { /* ... */ ??? }

def getReservedFundsForUser(userId: Long): OptionT[Future, Money] = for {
  user <- findUserById(userId)
  account <- findAccountById(user.accountId)
  funds <- getReservedFundsForAccount(account)
} yield funds

The OptionT[Future, Money] instance returned by getReservedFundsForUser will enclose a None value if any of the three composed methods returns an OptionT corresponding to None.
Otherwise, if the result of all three calls contains Some, the final outcome will also contain Some.

EitherT Copy Chapter

import cats.data.EitherT

EitherT[F, A, B] is the monad transformer for Either — you can think of it as a wrapper over a F[Either[A, B]] value.

Just as in the above section, I simplified the method headers, skipping type parameters or their context bounds and lower bounds.

Let's have a quick look at how to create an EitherT instance:

Another useful way to construct an EitherT instance is to use OptionT's methods toLeft and toRight:

abstract class BaseException(message: String) extends Exception(message)

case class UserNotFoundException(message: String) extends BaseException(message)

def getUserById(userId: Int): Future[Option[User]] = { /* ... */ ??? }

def ensureUserExists(userId: Int): EitherT[Future, BaseException, User] = {
  OptionT(getUserById(userId))
    .toRight(left = UserNotFoundException(s"user not found, userId=$userId"))
}

toRight is pretty analogous to the method Either.fromOption mentioned before: just as fromOption built an Either from an Option, toRight creates an EitherT from an OptionT.
If the original OptionT stores Some value, it will be wrapped into Right; otherwise the value provided as the left parameter will be wrapped into a Left.
To provide the left value within the monad, there is corresponding toRightF method.

toLeft is toRight's counterpart which wraps the Some value into Left and transforms None into Right enclosing the provided right value.
This is less commonly used in practice, but can serve e.g. for enforcing uniqueness checks in code.
We return Left if the value has been found, and Right if it doesn't yet exist in the system.

The methods available in EitherT are pretty similar to those we've seen in OptionT, but there are some notable differences.

You might get into some confusion at first when it comes to e.g. map.
In the case of OptionT, it was pretty obvious what should be done: map should go over the Option enclosed within Future, and then map the enclosed Option itself.
This is slightly less obvious in case of EitherT: should it map over both Left and Right values, or only the Right value?

The answer is that EitherT is right-biased, therefore plain map actually deals with the Right value.
This is unlike Either in the Scala standard library up to 2.11, which is in turn unbiased: there's no map available in Either, only for its left and right projections.

Having said that, let's take a quick look at the right-biased methods that EitherT offers:

As a side note, there are also certain methods in EitherT (that you're likely to need at some point) which map over the Left value, like leftMap, or over both Left and Right values, like fold or bimap.

EitherT is very useful for fail-fast chained verifications:

case class Item(state: String)
class ItemOrder  { /* ... */ }

case class ItemNotFoundException(message: String) extends BaseException(message)
case class InvalidItemStateException(message: String) extends BaseException(message)

def getItemById(itemId: Int): Future[Option[Item]] = { /* .. */ ??? }

def ensureItemExists(itemId: Int): EitherT[Future, BaseException, Item] = {
  OptionT(getItemById(itemId))
    .toRight(ItemNotFoundException(s"item not found, itemId = $itemId"))
}

def ensureItemStateIs(actual: String, expected: String): EitherT[Future, BaseException, Unit] = {
  // Returns a Unit value wrapped into Right and then into Future if condition is true,
  // otherwise the provided exception wrapped into Left and then into Future.
  EitherT.cond(actual == expected, (), InvalidItemStateException(s"actual=$actual, expected=$expected"))
}

def placeOrderForItem(userId: Int, itemId: Int, count: Int): Future[ItemOrder] = { /* ... */ ??? }

def buyItem(userId: Int, itemId: Int, count: Int): EitherT[Future, BaseException, ItemOrder] = {
  for {
    user <- ensureUserExists(userId)
    item <- ensureItemExists(itemId)
    _ <- ensureItemStateIs(item.state, "AVAILABLE_IN_STOCK")
    // EitherT.liftF is necessary to make EitherT[Future, BaseException, ItemOrder] out of Future[ItemOrder]
    placedOrder <- EitherT.liftF(placeOrderForItem(userId, itemId, count))
  } yield placedOrder
}

In the above example, we're running various checks against the item one by one.
If any of the checks fails, the resulting EitherT will contain a Left value.
Otherwise, if all of the checks yield a Right (of course we mean a Right wrapped into an EitherT), then the final outcome will also contain Right.
This is a fail-fast behavior: we're effectively stopping the for comprehension flow at the first Left-ish result.

If you're instead looking for validation that accumulates the errors (e.g. when dealing with user-provided form data), cats.data.Validated may be a good choice.

Common issues

The Cats type class instances for standard library types are available in implicit scope and hence no longer have to be imported. If anything doesn't compile as expected, first make sure all the required Cats syntax implicits are in the scope — try importing cats.syntax.all._ and see if the problem persists. The only exception is here is Cat's own Order and PartialOrder type classes which are available by importing cats.implicits._.
As mentioned before, though, it's better to use narrow imports, but if the code doesn't compile it's sometimes worth just importing the entire library to check if it solves the problem.

If you're using Futures, make sure to provide an implicit ExecutionContext in the scope, otherwise Cats won't be able to infer implicit instances for Future's type classes.

IntelliJ sometimes reports errors in Cats-loaded code even though the source passes under scalac.
One such example are invocations of the methods of cats.data.Nested class, which compile correctly under scalac, but don't type check under IntelliJ's presentation compiler.
It should work without trouble under Scala IDE, though.

As an advice for your future learning: the Applicative type class, despite it's key significance in functional programming, comes slightly difficult to understand.
In my opinion it's much less intuitive than Functor or Monad, even though it actually stands right between Functor and Monad in the inheritance hierarchy.
The best approach to grasp Applicative is to first understand how product (which transforms an F[A] and F[B] to an F[(A, B)]) works rather than focus on the somewhat exotic ap operation itself.

Motivations (`docs/motivations.md`) Copy Section

{% laika.title = Motivations %}

Approachability

As this library evolves, we are placing a lot of emphasis on trying to
make decisions which will help keep this library approachable for
people new to the concepts in this library. We are collecting
anecdotes from successes and failures we have experienced in the past
in trying to teach others about these concepts, and trying to make
decisions which will help ease the process of getting acquainted to
the library for a newcomer. If you have any feedback for us in this
regard, we would love to hear from you. See the Contributing
page to find out ways to give us feedback.

Modularity

We are trying to make the library modular. It will have a tight
core which will contain only the type classes,
the bare minimum of data structures that are needed to support
them, and type class instances for those data structures and standard
library types.

Documentation

We feel that having lots of documentation is a very important goal for
our project. It will be a big win towards our goal of
approachability. We will strive to have the code well documented, we
will strive to have lots of documentation external to the code, and we
will strive to have a large corpus of compiler verified examples of
how the software can be used.

Writing documentation is a huge part of developing software, and one
that is often neglected. It is also a very easy way to get started
with contributing to the project.

Efficiency

Although unfortunately there are times when programming only with
pure functions and writing efficient code in Scala can be at odds, we
are attempting to do our best at keeping our library as efficient as
we can without making unnecessary sacrifices of purity and
usability. Where sacrifices have to be made, we will strive to make
these obvious, and will keep them well documented.

Nomenclature (`docs/nomenclature.md`) Copy Section

Glossary

This is a catalogue of the major functions, type classes, and data types in Cats. It serves as a bird's-eye view of each class capabilities. It is also intended as a go-to reference for Cats users, who may not recall the answer to questions like these:

• What is the difference between unit and void?
• To discard the first value and keep only the first effect, is it <* or *>?
• How do I make a computation F[A] fail by checking a condition on the value?

The signatures and type-classes have been simplified, are described below. If you want a printable version, you can also check out this cats-cheatsheet.

WARNING: this page is written manually, and not automatically generated, so many things may be missing. If you find a mistake, or addition, please submit a PR following the guidelines below.

Type-Classes over an `F[_]` Copy Chapter

Functor Copy Section

Apply Copy Section

Applicative Copy Section

FlatMap Copy Section

FunctorFilter Copy Section

ApplicativeError Copy Section

The source code of Cats uses the E type variable for the error type.

MonadError Copy Section

Like the previous section, we use the E for the error parameter type.

UnorderedFoldable Copy Section

Foldable Copy Section

Reducible Copy Section

Traverse Copy Section

SemigroupK Copy Section

MonoidK Copy Section

Alternative Copy Section

NonEmptyAlternative Copy Section

Transformers Copy Chapter

Constructors and wrappers Copy Section

OptionT Copy Section

For convenience, in these types we use the symbol OT to abbreviate OptionT.

EitherT Copy Section

Here, we use ET to abbreviate EitherT; and we use A and B as type variables for the left and right sides of the Either.

Kleisli (or ReaderT) Copy Section

Here, we use Ki as a short-hand for Kleisli.

Type Classes for types `F[_, _]` Copy Chapter

Bifunctor Copy Section

Profunctor

Strong Profunctor

Compose, Category, Choice

Arrow

ArrowChoice

Simplifications Copy Chapter

Because Сats is a Scala library and Scala has many knobs and switches, the actual definitions and the implementations of the functions and type-classes in Сats can be a bit obfuscated at first. To alleviate this, in this glossary we focus on the plain type signatures of the method, and ignore many of the details from Scala. In particular, in our type signatures:

• We use A,B,C for type variables of kind *, and F, G, H for type variables of a higher kind.
• We write type signatures in currified form: parameters are taken one at a time, and they are separated with the arrow => operation. In Scala, a method's parameters may be split in several comma-separated lists.
• We do not differentiate between methods from the type-class trait (e.g. trait Functor), or the companion object, or the syntax companion (implicit class).
• For functions defined as method of the typeclass trait, we ignore the receiver object.
• We ignore implicit parameters that represent type-class constraints; and write them on a side column instead.
• We use A => B for both Function1[A, B] and PartialFunction[A, B] parameters, without distinction. We add a side note when one is a PartialFunction.
• Some functions are defined through the Partially Applied Type Params pattern. We ignore this.
• We ignore the distinction between by-name and by-value input parameters. We use the notation => A, without parameters, to indicate constant functions.
• We ignore Scala variance annotations. We also ignore extra type parameters, which in some methods are added with a subtype-constraint, (e.g. B >: A). These are usually meant for flexibility, but we replace each one by its bound.

Resources For Learners (`docs/resources_for_learners.md`) Copy Section

{% laika.title = Resources for Learners %}

Books

• Functional Programming in Scala
  by Michael Pilquist, Rúnar Bjarnason, and Paul Chiusano - While this book does not
  specifically cover Cats, it is a great introduction to functional
  programming in Scala in general and covers some of the abstractions
  that can be found in Cats.
• Scala with Cats
  by Noel Welsh and Dave Gurnell - The aims of this book are two-fold:
  to introduce monads, functors, and other functional programming patterns
  as a way to structure program design, and to explain how these
  concepts are implemented in Cats.

Tutorials

• herding cats by Eugene Yokota

Example Projects

• Scala Pet Store
  Demonstrates FP techniques while maintaining approachability for people with an OO background. Uses tagless final for the core domain, and popular Typelevel libraries including Cats, Http4s, Circe and Doobie.

Videos

• Functional Structures in Scala
    by Michael Pilquist offers a series
  of lectures about basic functional structures.
• Category Theory for Programmers
  by Bartosz Milewski is a series
  of category theory lectures oriented towards programmers.
  The code examples are written in Haskell and C++,
  but the course is designed for programmers of any background,
  even the ones without a strong maths knowledge.
  • part 1
  • part 2
  • part 3
• Easy and efficient data validation with Cats by Daniela Sfregola this talk introduces Cats, and some of its most interesting components for data validation. In particular, we’ll discuss some options to achieve efficient and expressive data validation. We will also argue that, compared to other options in the language, Cats is particularly suited for the task thanks to its easy-to-use data types and more approachable syntax.
• Cats by example by Thomas Höfer provides a beginner series on various datatypes from Cats.

Social network

• @impurepics regularly tweet informative and kawaii educational pieces about Cats and FP in Scala.

Typeclasses (`docs/typeclasses.md`) Copy Section

Type Classes

Type classes are a powerful tool used in functional programming to enable ad-hoc polymorphism, more commonly
known as overloading. Where many object-oriented languages leverage subtyping for polymorphic code, functional
programming tends towards a combination of parametric polymorphism (think type parameters, like Java generics)
and ad-hoc polymorphism.

Example: collapsing a list Copy Chapter

The following code snippets show code that sums a list of integers, concatenates a list of strings, and unions a list
of sets.

def sumInts(list: List[Int]): Int = list.foldRight(0)(_ + _)

def concatStrings(list: List[String]): String = list.foldRight("")(_ ++ _)

def unionSets[A](list: List[Set[A]]): Set[A] = list.foldRight(Set.empty[A])(_ union _)

All of these follow the same pattern: an initial value (0, empty string, empty set) and a combining function
(+, ++, union). We'd like to abstract over this so we can write the function once instead of once for every type
so we pull out the necessary pieces into an interface.

trait Monoid[A] {
  def empty: A
  def combine(x: A, y: A): A
}

// Implementation for Int
val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
  def empty: Int = 0
  def combine(x: Int, y: Int): Int = x + y
}

The name Monoid is taken from abstract algebra which specifies precisely this kind of structure.

We can now write the functions above against this interface.

def combineAll[A](list: List[A], m: Monoid[A]): A = list.foldRight(m.empty)(m.combine)

Type classes vs. subtyping Copy Chapter

The definition above takes an actual monoid argument instead of doing the usual object-oriented practice of using
subtype constraints.

// Subtyping
def combineAll[A <: Monoid[A]](list: List[A]): A = ???

This has a subtle difference with the earlier explicit example. In order to seed the foldRight with the empty value,
we need to get a hold of it given only the type A. Taking Monoid[A] as an argument gives us this by calling the
appropriate empty method on it. With the subtype example, the empty method would be on a value of type
Monoid[A] itself, which we are only getting from the list argument. If list is empty, we have no values to work
with and therefore can't get the empty value. Not to mention the oddity of getting a constant value from a non-static
object.

For another motivating difference, consider the simple pair type.

final case class Pair[A, B](first: A, second: B)

Defining a Monoid[Pair[A, B]] depends on the ability to define a Monoid[A] and Monoid[B], where the definition
is point-wise, i.e. the first element of the first pair combines with the first element of the second pair and the second element of the first pair combines with the second element of the second pair. With subtyping such a constraint would be encoded as something like

final case class Pair[A <: Monoid[A], B <: Monoid[B]](first: A, second: B) extends Monoid[Pair[A, B]] {
  def empty: Pair[A, B] = ???

  def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] = ???
}

Not only is the type signature of Pair now messy but it also forces all instances of Pair to have a Monoid
instance, whereas Pair should be able to carry any types it wants and if the types happens to have a
Monoid instance then so would it. We could try bubbling down the constraint into the methods themselves.

final case class Pair[A, B](first: A, second: B) extends Monoid[Pair[A, B]] {
  def empty(implicit eva: A <:< Monoid[A], evb: B <:< Monoid[B]): Pair[A, B] = ???

  def combine(x: Pair[A, B], y: Pair[A, B])(implicit eva: A <:< Monoid[A], evb: B <:< Monoid[B]): Pair[A, B] = ???
}

But now these don't conform to the interface of Monoid due to the implicit constraints.

Implicit derivation Copy Section

Note that a Monoid[Pair[A, B]] is derivable given Monoid[A] and Monoid[B]:

final case class Pair[A, B](first: A, second: B)

def deriveMonoidPair[A, B](A: Monoid[A], B: Monoid[B]): Monoid[Pair[A, B]] =
  new Monoid[Pair[A, B]] {
    def empty: Pair[A, B] = Pair(A.empty, B.empty)

    def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] =
      Pair(A.combine(x.first, y.first), B.combine(x.second, y.second))
  }

One of the most powerful features of type classes is the ability to do this kind of derivation automatically.
We can do this through Scala's implicit mechanism.

import cats.Monoid

object Demo {
  final case class Pair[A, B](first: A, second: B)

  object Pair {
    implicit def tuple2Instance[A, B](implicit A: Monoid[A], B: Monoid[B]): Monoid[Pair[A, B]] =
      new Monoid[Pair[A, B]] {
        def empty: Pair[A, B] = Pair(A.empty, B.empty)

        def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] =
          Pair(A.combine(x.first, y.first), B.combine(x.second, y.second))
      }
  }
}

We also change any functions that have a Monoid constraint on the type parameter to take the argument implicitly,
and any instances of the type class to be implicit.

implicit val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
  def empty: Int = 0
  def combine(x: Int, y: Int): Int = x + y
}

def combineAll[A](list: List[A])(implicit A: Monoid[A]): A = list.foldRight(A.empty)(A.combine)

Now we can also combineAll a list of Pairs as long as Pair's type parameters themselves have Monoid
instances.

implicit val stringMonoid: Monoid[String] = new Monoid[String] {
  def empty: String = ""
  def combine(x: String, y: String): String = x ++ y
}

import Demo.{Pair => Paired}

combineAll(List(Paired(1, "hello"), Paired(2, " "), Paired(3, "world")))

A note on syntax Copy Chapter

In many cases, including the combineAll function above, the implicit arguments can be written with syntactic sugar.

def combineAll[A : Monoid](list: List[A]): A = ???

While nicer to read as a user, it comes at a cost for the implementer.

import cats.Monoid

// Defined in the standard library, shown for illustration purposes
// Implicitly looks in implicit scope for a value of type `A` and just hands it back
def implicitly[A](implicit ev: A): A = ev

def combineAll[A : Monoid](list: List[A]): A =
  list.foldRight(implicitly[Monoid[A]].empty)(implicitly[Monoid[A]].combine)

For this reason, many libraries that provide type classes provide a utility method on the companion object of the type
class, usually under the name apply, that skirts the need to call implicitly everywhere.

object Monoid {
  def apply[A : Monoid]: Monoid[A] = implicitly[Monoid[A]]
}

def combineAll[A : Monoid](list: List[A]): A =
  list.foldRight(Monoid[A].empty)(Monoid[A].combine)

Laws

Conceptually, all type classes come with laws. These laws constrain implementations for a given
type and can be exploited and used to reason about generic code.

For instance, the Monoid type class requires that
combine be associative and empty be an identity element for combine. That means the following
equalities should hold for any choice of x, y, and z.

combine(x, combine(y, z)) = combine(combine(x, y), z)
combine(x, id) = combine(id, x) = x

With these laws in place, functions parametrized over a Monoid can leverage them for say, performance
reasons. A function that collapses a List[A] into a single A can do so with foldLeft or
foldRight since combine is assumed to be associative, or it can break apart the list into smaller
lists and collapse in parallel, such as

val list = List(1, 2, 3, 4, 5)
val (left, right) = list.splitAt(2)

// Imagine the following two operations run in parallel
val sumLeft = combineAll(left)
val sumRight = combineAll(right)

// Now gather the results
val result = Monoid[Int].combine(sumLeft, sumRight)

Cats provides laws for type classes via the kernel-laws and laws modules which makes law checking
type class instances easy.

You can find out more about law testing here.

Type classes in Cats Copy Chapter

From cats-infographic by @tpolecat.

Incomplete type class instances in cats Copy Chapter

Originally from @hobwekiva

Further reading Copy Chapter

• [Returning the "Current" Type in Scala][fbounds]

[fbounds]: http://tpolecat.github.io/2015/04/29/f-bounds.html "Returning the "Current" Type in Scala"

TypelevelEcosystem (`docs/typelevelEcosystem.md`) Copy Section

Typelevel Ecosystem

By sharing the same set of type classes, instances and data types provided by Cats, projects can speak the same “Cats language”, and integrate with each other with ease.

Libraries Copy Chapter

Here you can find a comprehensive list of libraries and projects related to Typelevel:

Your project talks Cats too? Submit a PR to add it here!

The full-size Cats logo is available for use for Cats related projects, contents, souvenirs, etc.

We offer a Cats Friendly Badge to let others know your project works with Cats!

Below are quick html and markdown snippets to use the badge in your own project.

<a href=""><img src="https://typelevel.org/cats/img/cats-badge-tiny.png" alt="Cats friendly" /></a>

Datatypes Chain (`docs/datatypes/chain.md`) Copy Section

Chain

API Documentation: @:api(cats.data.Chain)

Chain is an immutable sequence data structure that allows constant time prepending, appending and concatenation.
This makes it especially efficient when used as a [Monoid], e.g. with [Validated] or [Writer].
As such it aims to be used where @:api(scala.collection.immutable.List) and @:api(scala.collection.immutable.Vector) incur a performance penalty.
Cats also includes type class implementations to support using Chain as a general-purpose collection type, including [Traverse], [Monad], and [Alternative].

Motivation Copy Chapter

List is a great data type, it is very simple and easy to understand.
It has very low overhead for the most important functions such as [fold][Foldable] and [map][Functor] and also supports prepending a single element in constant time.

Traversing a data structure with something like [Writer[List[Log], A]][Writer] or [ValidatedNel[Error, A]][Validated] is powerful and allows us to precisely specify what kind of iteration we want to do while remaining succinct.
However, in terms of efficiency it's a whole different story unfortunately.
That is because both of these traversals make use of the List monoid (or the [NonEmptyList] semigroup), which by the nature of List is very inefficient.
If you use [traverse][Traverse] with a data structure with n elements and [Writer] or [Validated] as the [Applicative] type, you will end up with a runtime of O(n^2).
This is because, with List, appending a single element requires iterating over the entire data structure and therefore takes linear time.

So @:api(scala.collection.immutable.List) isn't all that great for this use case, so let's use @:api(scala.collection.immutable.Vector) or @:api(cats.data.NonEmptyVector)` instead, right?

Well, Vector has its own problems and in this case it's unfortunately not that much faster than List at all. You can check this blog post by Li Haoyi for some deeper insight into Vector's issues.

Chain evolved from what used to be fs2.Catenable and Erik Osheim's Chain library.
Similar to List, it is also a very simple data structure, but unlike List it supports constant O(1) time append, prepend and concat.
This makes its [Monoid] instance [super performant][Benchmarks] and a much better fit for usage with [Validated], [Writer], [Ior] or [Const].

NonEmptyChain Copy Chapter

NonEmptyChain is the non-empty version of Chain.
It does not have a [Monoid] instance since it cannot be empty, but it does have a [Semigroup] instance.
Likewise, it defines a [NonEmptyTraverse] instance, but no @:api(cats.TraverseFilter) instance.

To simplify the usage of NonEmptyChain, Cats includes type aliases like ValidatedNec and IorNec, as well as helper functions like groupByNec and Validated.invalidNec.

There are numerous ways to construct a NonEmptyChain, e.g. you can create one from a single element, a NonEmptyList or a NonEmptyVector:

import cats.data._

NonEmptyChain(1, 2, 3, 4)

NonEmptyChain.fromNonEmptyList(NonEmptyList(1, List(2, 3)))
NonEmptyChain.fromNonEmptyVector(NonEmptyVector(1, Vector(2, 3)))

NonEmptyChain.one(1)

You can also create an @:api(scala.Option) of NonEmptyChain from a Chain or any other collection type:

import cats.data._

NonEmptyChain.fromChain(Chain(1, 2, 3))
NonEmptyChain.fromSeq(List.empty[Int])
NonEmptyChain.fromSeq(Vector(1, 2, 3))

Sometimes, you'll want to prepend or append a single element to a chain and return the result as a NonEmptyChain:

import cats.data._

NonEmptyChain.fromChainAppend(Chain(1, 2, 3), 4)
NonEmptyChain.fromChainAppend(Chain.empty[Int], 1)
NonEmptyChain.fromChainPrepend(1, Chain(2, 3))

How it works Copy Chapter

Chain is implemented as a simple unbalanced binary tree ADT with four cases:
an empty Chain with no elements, a singleton Chain with exactly one element, a concatenation of two chains, or a wrapper for a @:api(scala.collection.immutable.Seq).

In code it looks like this:

sealed abstract class Chain[+A]

case object Empty extends Chain[Nothing]
case class Singleton[A](a: A) extends Chain[A]
case class Append[A](left: Chain[A], right: Chain[A]) extends Chain[A]
case class Wrap[A](seq: Seq[A]) extends Chain[A]

The Append constructor is what gives us the fast concatenation ability.
Concatenating two existing Chains is just a call to the Append constructor, which is always constant time O(1).

In case we want to append or prepend a single element,
all we have to do is wrap the element with the Singleton constructor and then use the Append constructor to append or prepend the Singleton Chain.

The Wrap constructor lifts any Seq into a Chain.
This can be useful for concatenating already created collections that don't have great concatenation performance.
Append(Wrap(list1), Wrap(list2)).foldMap(f) will in general be much faster than just concatenating list1 and list2 and folding the result.

Chain doesn't directly expose the Append and Wrap constructors, because the arguments might refer to an empty Chain or Seq.
Instead of calling Append directly you can simply use Chain.concat or ++, which will check if one of the arguments is empty:

def concat[A](c: Chain[A], c2: Chain[A]): Chain[A] =
  if (c.isEmpty) c2
  else if (c2.isEmpty) c
  else Append(c, c2)

To construct a Chain from a Seq you should use Chain.fromSeq which will also check for emptiness:

def fromSeq[A](s: Seq[A]): Chain[A] =
  if (s.isEmpty) nil
  else if (s.lengthCompare(1) == 0) one(s.head)
  else Wrap(s)

In conclusion Chain supports constant time concatenation, because it builds an unbalance tree of Appends.
append and prepend are treated as concatenation with single element collection to keep the same performance characteristics.
This unbalanced tree will always allow iteration in linear time.

Benchmarks Copy Chapter

To get a good idea of performance of Chain, here are some benchmarks that test monoidal append (higher score is better):

Benchmark                                Mode  Cnt         Score         Error  Units
CollectionMonoidBench.accumulateChain   thrpt   25        81.973 ±       3.921  ops/s
CollectionMonoidBench.accumulateList    thrpt   25        21.150 ±       1.756  ops/s
CollectionMonoidBench.accumulateVector  thrpt   25        11.725 ±       0.306  ops/s

As you can see accumulating things with Chain is almost 4 times faster than List and nearly 8 times faster than Vector.
So appending is a lot more performant than the standard library collections, but what about operations like map or fold?
Fortunately we've also benchmarked these (again, higher score is better):

/* Detailed source-code truncated for AI context efficiency. */

While not dominant, Chain performance is in the middle of the pack for most operations benchmarked.
Chain does have poor random access performance, and should be avoided in favor of Vector for random access heavy use cases.

Chain excels with concatenation heavy workloads and has comparable performance to List and Vector for most other operations.
So next time you write any code that uses List or Vector as a [Monoid], be sure to use Chain instead!

Note: All benchmarks above were run using JMH 1.32 with Scala 2.13.8 on JDK 11.
For full details, see here.
You can also check out the benchmark source code.

Datatypes Const (`docs/datatypes/const.md`) Copy Section

Const

API Documentation: @:api(cats.data.Const)

At first glance Const seems like a strange data type - it has two type parameters, yet only
stores a value of the first type. What possible use is it? As it turns out, it does
have its uses, which serve as a nice example of the consistency and elegance of functional programming.

Thinking about `Const` Copy Chapter

The Const data type can be thought of similarly to the const function, but as a data type.

def const[A, B](a: A)(b: => B): A = a

The const function takes two arguments and simply returns the first argument, ignoring the second.

case class Const[A, B](getConst: A)

The Const data type takes two type parameters, but only ever stores a value of the first type parameter.
Because the second type parameter is not used in the data type, the type parameter is referred to as a
"phantom type".

Why do we care? Copy Chapter

It would seem Const gives us no benefit over a data type that would simply not have the second type parameter.
However, while we don't directly use the second type parameter, its existence becomes useful in certain contexts.

Example 1: Lens Copy Section

The following is heavily inspired by Julien Truffaut's
blog post on
Monocle, a fully-fledged optics library in Scala.

Types that contain other types are common across many programming paradigms. It is of course desirable in many
cases to get out members of other types, or to set them. In traditional object-oriented programming this is
handled by getter and setter methods on the outer object. In functional programming, a popular solution is
to use a lens.

A lens can be thought of as a first class getter/setter. A Lens[S, A] is a data type that knows how to get
an A out of an S, or set an A in an S.

trait Lens[S, A] {
  def get(s: S): A

  def set(s: S, a: A): S

  def modify(s: S)(f: A => A): S =
    set(s, f(get(s)))
}

It can be useful to have effectful modifications as well - perhaps our modification can fail (Option) or
can return several values (List).

trait Lens[S, A] {
  def get(s: S): A

  def set(s: S, a: A): S

  def modify(s: S)(f: A => A): S =
    set(s, f(get(s)))

  def modifyOption(s: S)(f: A => Option[A]): Option[S] =
    f(get(s)).map(a => set(s, a))

  def modifyList(s: S)(f: A => List[A]): List[S] =
    f(get(s)).map(a => set(s, a))
}

Note that both modifyOption and modifyList share the exact same implementation. If we look closely, the
only thing we need is a map operation on the data type. Being good functional programmers, we abstract.

import cats.Functor
import cats.syntax.all._

trait Lens[S, A] {
  def get(s: S): A

  def set(s: S, a: A): S

  def modify(s: S)(f: A => A): S =
    set(s, f(get(s)))

  def modifyF[F[_] : Functor](s: S)(f: A => F[A]): F[S] =
    f(get(s)).map(a => set(s, a))
}

We can redefine modify in terms of modifyF by using cats.Id. We can also treat set as a modification
that simply ignores the current value. Due to these modifications however, we must leave modifyF abstract
since having it defined in terms of set would lead to infinite circular calls.

import cats.Id

trait Lens[S, A] {
  def modifyF[F[_] : Functor](s: S)(f: A => F[A]): F[S]

  def set(s: S, a: A): S = modify(s)(_ => a)

  def modify(s: S)(f: A => A): S = modifyF[Id](s)(f)

  def get(s: S): A
}

What about get? Certainly we can't define get in terms of the others.. the others are to modify an existing
value, whereas get is to retrieve it. Let's give it a shot anyways.

Looking at modifyF, we have an S we can pass in. The tricky part will be the A => F[A], and then somehow
getting an A out of F[S]. If we imagine F to be a type-level constant function however, we could imagine
it would simply take any type and return some other constant type, an A perhaps. This suggests our F is a
Const.

We then take a look at the fact that modifyF takes an F[_], a type constructor that takes a single type parameter.
Const takes two, so we must fix one. The function returns an F[S], but we want an A, which implies we
have the first type parameter fixed to A and leave the second one free for the function to fill in as it wants.

Substituting in Const[A, _] wherever we see F[_], the function wants an A => Const[A, A] and will give us back
a Const[A, S]. Looking at the definition of Const, we see that we only ever have a value of the first type parameter
and completely ignore the second. Therefore, we can treat any Const[X, Y] value as equivalent to X (plus or minus
some wrapping into Const). This leaves us with needing a function A => A. Given the type, the only thing we can do
is to take an A and return it right back (lifted into Const).

Before we plug and play however, note that modifyF has a Functor constraint on F[_]. This means we need to
define a Functor instance for Const, where the first type parameter is fixed.

Note: the example below assumes usage of the kind-projector compiler plugin and will not compile if it is not being used in a project.

import cats.Functor
import cats.data.Const

implicit def constFunctor[X]: Functor[Const[X, *]] =
  new Functor[Const[X, *]] {
    // Recall Const[X, A] ~= X, so the function is not of any use to us
    def map[A, B](fa: Const[X, A])(f: A => B): Const[X, B] =
      Const(fa.getConst)
  }

Now that that's taken care of, let's substitute and see what happens.

import cats.Id

trait Lens[S, A] {
  def modifyF[F[_] : Functor](s: S)(f: A => F[A]): F[S]

  def set(s: S, a: A): S = modify(s)(_ => a)

  def modify(s: S)(f: A => A): S = modifyF[Id](s)(f)

  def get(s: S): A = {
    val storedValue = modifyF[Const[A, *]](s)(a => Const(a))
    storedValue.getConst
  }
}

It works! We get a Const[A, S] out on the other side, and we simply just retrieve the A value stored inside.

What's going on here? We can treat the effectful "modification" we are doing as a store operation - we take an A
and store it inside a Const. Knowing only F[_] has a Functor instance, it can only map over the Const
which will do nothing to the stored value. After modifyF is done getting the new S, we retrieve the stored A
value and we're done!

Example 2: Traverse Copy Section

In the popular The Essence of the Iterator Pattern
paper, Jeremy Gibbons and Bruno C. d. S. Oliveria describe a functional approach to iterating over a collection of
data. Among the abstractions presented are Foldable and Traverse, replicated below (also available in Cats).

import cats.{Applicative, Monoid}

trait Foldable[F[_]] {
  // Given a collection of data F[A], and a function mapping each A to a B where B has a Monoid instance,
  // reduce the collection down to a single B value using the monoidal behavior of B
  def foldMap[A, B : Monoid](fa: F[A])(f: A => B): B
}

trait Traverse[F[_]] {
  // Given a collection of data F[A], for each value apply the function f which returns an effectful
  // value. The result of traverse is the composition of all these effectful values.
  def traverse[G[_] : Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
}

These two type classes seem unrelated - one reduces a collection down to a single value, the other traverses
a collection with an effectful function, collecting results. It may be surprising to see that in fact Traverse
subsumes Foldable.

trait Traverse[F[_]] extends Foldable[F] {
  def traverse[G[_] : Applicative, A, X](fa: F[A])(f: A => G[X]): G[F[X]]

  def foldMap[A, B : Monoid](fa: F[A])(f: A => B): B
}

To start, we observe that if we are to implement foldMap in terms of traverse, we will want a B out
at some point. However, traverse returns a G[F[X]]. It would seem there is no way to unify these two.
However, if we imagine G[_] to be a sort of type-level constant function, where the fact that it's taking a
F[X] is irrelevant to the true underlying value, we can begin to see how we might be able to pull this off.

traverse however wants G[_] to have an Applicative instance, so let's define one for Const. Since
F[X] is the value we want to ignore, we treat it as the second type parameter and hence, leave it as the free
one.

import cats.data.Const

implicit def constApplicative[Z]: Applicative[Const[Z, *]] =
  new Applicative[Const[Z, *]] {
    def pure[A](a: A): Const[Z, A] = ???

    def ap[A, B](f: Const[Z, A => B])(fa: Const[Z, A]): Const[Z, B] = ???
  }

Recall that Const[Z, A] means we have a Z value in hand, and don't really care about the A type parameter.
Therefore we can more or less treat the type Const[Z, A] as just Z.

In functions pure and ap we have a problem. In pure, we have an A value, but want to return a Z value. We have
no function A => Z, so our only option is to completely ignore the A value. But we still don't have a Z! Let's
put that aside for now, but still keep it in the back of our minds.

In ap we have two Z values, and want to return a Z value. We could certainly return one or the other, but we
should try to do something more useful. This suggests composition of Zs, which we don't know how to do.

So now we need a constant Z value, and a binary function that takes two Zs and produces a Z. Sound familiar?
We want Z to have a Monoid instance!

implicit def constApplicative[Z : Monoid]: Applicative[Const[Z, *]] =
  new Applicative[Const[Z, *]] {
    def pure[A](a: A): Const[Z, A] = Const(Monoid[Z].empty)

    def ap[A, B](f: Const[Z, A => B])(fa: Const[Z, A]): Const[Z, B] =
      Const(Monoid[Z].combine(fa.getConst, f.getConst))
  }

We have our Applicative!

Going back to Traverse, we fill in the first parameter of traverse with fa since that's
the only value that fits.

Now we need a A => G[B]. We have an A => B, and we've decided to use Const for our G[_]. We need to
fix the first parameter of Const since Const takes two type parameters and traverse wants a type constructor
which only takes one. The first type parameter which will be the type of the actual values we store, and therefore will
be the type of the value we get out at the end, so we leave the second one free, similar to the Applicative instance.
We don't care about the second type parameter and there are no restrictions on it, so we can just use Nothing,
the type that has no values.

So to summarize, what we want is a function A => Const[B, Nothing], and we have a function A => B. Recall
that Const[B, Z] (for any Z) is the moral equivalent of just B, so A => Const[B, Nothing] is equivalent
to A => B, which is exactly what we have, we just need to wrap it.

trait Traverse[F[_]] extends Foldable[F] {
  def traverse[G[_] : Applicative, A, X](fa: F[A])(f: A => G[X]): G[F[X]]

  def foldMap[A, B : Monoid](fa: F[A])(f: A => B): B = {
    val const: Const[B, F[Nothing]] = traverse[Const[B, *], A, Nothing](fa)(a => Const(f(a)))
    const.getConst
  }
}

Hurrah!

What's happening here? We can see traverse is a function that goes over a collection, applying an
effectful function to each value, and combining all of these effectful values. In our case, the effect
is mapping each value to a value of type B, where we know how to combine Bs via its Monoid instance.
The Monoid instance is exactly what is used when traverse goes to collect the effectful values together.
Should the F[A] be "empty", it can use Monoid#empty as a value to return back.

Pretty nifty. traverse-ing over a collection with an effectful function is more general than traversing
over a collection to reduce it down to a single value.

Datatypes Contt (`docs/datatypes/contt.md`) Copy Section

ContT

API Documentation: @:api(cats.data.ContT)

A pattern that appears sometimes in functional programming is that of a function
first computing some kind of intermediate result and then passing that result to
another function which was passed in as an argument, in order to delegate the
computation of the final result.

For example:

case class User(id: Int, name: String, age: Int)
sealed abstract class UserUpdateResult
case class Succeeded(updatedUserId: Int) extends UserUpdateResult
case object Failed extends UserUpdateResult

import cats.Eval

def updateUser(persistToDatabase: User => Eval[UserUpdateResult])
              (existingUser: User, newName: String, newAge: Int): Eval[UserUpdateResult] = {
  val trimmedName = newName.trim
  val cappedAge = newAge max 150
  val updatedUser = existingUser.copy(name = trimmedName, age = cappedAge)

  persistToDatabase(updatedUser)
}

(Note: We will be using Eval throughout the examples on this page. If you are not
familiar with Eval, it's worth reading the Eval documentation first.)

Our updateUser function takes in an existing user and some updates to perform.
It sanitises the inputs and updates the user model, but it delegates the
database update to another function which is passed in as an argument.

This pattern is known as "continuation passing style" or CPS, and the function
passed in (persistToDatabase) is known as a "continuation".

Note the following characteristics:

• The return type of our updateUser function (Eval[UserUpdateResult]) is the
  same as the return type of the continuation function that was passed in.
• Our function does a bit of work to build an intermediate value, then passes
  that value to the continuation, which takes care of the remainder of the
  work.

In Cats we can encode this pattern using the ContT data type:

import cats.data.ContT

def updateUserCont(existingUser: User,
                   newName: String,
                   newAge: Int): ContT[Eval, UserUpdateResult, User] =
  ContT.apply[Eval, UserUpdateResult, User] { next =>
    val trimmedName = newName.trim
    val cappedAge = newAge min 150
    val updatedUser = existingUser.copy(name = trimmedName, age = cappedAge)

    next(updatedUser)
  }

We can construct a computation as follows:

val existingUser = User(100, "Alice", 42)

val computation = updateUserCont(existingUser, "Bob", 200)

And then call run on it, passing in a function of type User => Eval[UserUpdateResult] as the continuation:

val eval = computation.run { user =>
  Eval.later {
    println(s"Persisting updated user to the DB: $user")
    Succeeded(user.id)
  }
}

Finally we can run the resulting Eval to actually execute the computation:

eval.value

Composition Copy Chapter

You might be wondering what the point of all this was, as the function that uses
ContT seems to achieve the same thing as the original function, just encoded
in a slightly different way.

The point is that ContT is a monad, so by rewriting our function into a
ContT we gain composibility for free.

For example we can map over a ContT:

val anotherComputation = computation.map { user =>
  Map(
    "id" -> user.id.toString,
    "name" -> user.name,
    "age" -> user.age.toString
  )
}

val anotherEval = anotherComputation.run { userFields =>
  Eval.later {
    println(s"Persisting these fields to the DB: $userFields")
    Succeeded(userFields("id").toInt)
  }
}

anotherEval.value

And we can use flatMap to chain multiple ContTs together.

The following example builds 3 computations: one to sanitise the inputs and
update the user model, one to persist the updated user to the database, and one
to publish a message saying the user was updated. It then chains them together
in continuation-passing style using flatMap and runs the whole computation.

val updateUserModel: ContT[Eval, UserUpdateResult, User] =
  updateUserCont(existingUser, "Bob", 200).map { updatedUser =>
    println("Updated user model")
    updatedUser
  }

val persistToDb: User => ContT[Eval, UserUpdateResult, UserUpdateResult] = {
  user =>
    ContT.apply[Eval, UserUpdateResult, UserUpdateResult] { next =>
      println(s"Persisting updated user to the DB: $user")

      next(Succeeded(user.id))
    }
}

val publishEvent: UserUpdateResult => ContT[Eval, UserUpdateResult, UserUpdateResult] = {
  userUpdateResult =>
    ContT.apply[Eval, UserUpdateResult, UserUpdateResult] { next =>
      userUpdateResult match {
        case Succeeded(userId) =>
          println(s"Publishing 'user updated' event for user ID $userId")
        case Failed =>
          println("Not publishing 'user updated' event because update failed")
      }

      next(userUpdateResult)
    }
}

val chainOfContinuations =
  updateUserModel flatMap persistToDb flatMap publishEvent

val eval = chainOfContinuations.run { finalResult =>
  Eval.later {
    println("Finished!")
    finalResult
  }
}

eval.value

Why Eval? Copy Chapter

If you're wondering why we used Eval in our examples above, it's because the
Monad instance for ContT[M[_], A, B] requires an instance of cats.Defer
for M[_]. This is an implementation detail - it's needed in order to preserve
stack safety.

In a real-world application, you're more likely to be using something like
cats-effect IO, which has a Defer instance.

Datatypes Either (`docs/datatypes/either.md`) Copy Section

{% laika.excludeFromNavigation = true %}

Either

The Either type is provided by the Scala standard library, but Cats provides syntax enrichment and typeclass instances
to extend its functionality, including [Functor], [Applicative], [Monad] and
MonadError.

If you would like to accumulate errors instead of the short-circuiting behavior of Either, see the
[Parallel] typeclass, or the [Validated] data type.

Datatypes Eithert (`docs/datatypes/eithert.md`) Copy Section

EitherT

API Documentation: @:api(cats.data.EitherT)

Either can be used for error handling in most situations. However, when
Either is placed into effectful types such as Option orFuture, a large
amount of boilerplate is required to handle errors. For example, consider the
following program:

import scala.util.Try
import cats.syntax.all._

def parseDouble(s: String): Either[String, Double] =
  Try(s.toDouble).map(Right(_)).getOrElse(Left(s"$s is not a number"))

def divide(a: Double, b: Double): Either[String, Double] =
  Either.cond(b != 0, a / b, "Cannot divide by zero")

def divisionProgram(inputA: String, inputB: String): Either[String, Double] =
  for {
    a <- parseDouble(inputA)
    b <- parseDouble(inputB)
    result <- divide(a, b)
  } yield result

divisionProgram("4", "2") // Right(2.0)
divisionProgram("a", "b") // Left("a is not a number")

Suppose parseDouble and divide are rewritten to be asynchronous and return
Future[Either[String, Double]] instead. The for-comprehension can no longer be
used since divisionProgram must now compose Future and Either together,
which means that the error handling must be performed explicitly to ensure that
the proper types are returned:

import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.Future

def parseDoubleAsync(s: String): Future[Either[String, Double]] =
  Future.successful(parseDouble(s))
def divideAsync(a: Double, b: Double): Future[Either[String, Double]] =
  Future.successful(divide(a, b))

def divisionProgramAsync(inputA: String, inputB: String): Future[Either[String, Double]] =
  parseDoubleAsync(inputA) flatMap { eitherA =>
    parseDoubleAsync(inputB) flatMap { eitherB =>
      (eitherA, eitherB) match {
        case (Right(a), Right(b)) => divideAsync(a, b)
        case (Left(err), _) => Future.successful(Left(err))
        case (_, Left(err)) => Future.successful(Left(err))
      }
    }
  }

Clearly, the updated code is less readable and more verbose: the details of the
program are now mixed with the error handling. In addition, as more Eithers
and Futures are included, the amount of boilerplate required to properly
handle the errors will increase dramatically.

EitherT Copy Chapter

EitherT[F[_], A, B] is a lightweight wrapper for F[Either[A, B]] that makes
it easy to compose Eithers and Fs together. To use EitherT, values of
Either, F, A, and B are first converted into EitherT, and the
resulting EitherT values are then composed using combinators. For example, the
asynchronous division program can be rewritten as follows:

import cats.data.EitherT
import cats.syntax.all._

def divisionProgramAsync(inputA: String, inputB: String): EitherT[Future, String, Double] =
  for {
    a <- EitherT(parseDoubleAsync(inputA))
    b <- EitherT(parseDoubleAsync(inputB))
    result <- EitherT(divideAsync(a, b))
  } yield result

divisionProgramAsync("4", "2").value
divisionProgramAsync("a", "b").value

Note that when F is a monad, then EitherT will also form a monad, allowing
monadic combinators such as flatMap to be used in composing EitherT values.

From `A` or `B` to `EitherT[F, A, B]` Copy Chapter

To obtain a left version or a right version of EitherT when given an A or a
B, use EitherT.leftT and EitherT.rightT (which is an alias for
EitherT.pure), respectively.

val number: EitherT[Option, String, Int] = EitherT.rightT(5)
val error: EitherT[Option, String, Int] = EitherT.leftT("Not a number")

From `F[A]` or `F[B]` to `EitherT[F, A, B]` Copy Chapter

Similarly, use EitherT.left and EitherT.right to convert an F[A] or an F[B]
into an EitherT. It is also possible to use EitherT.liftF as an alias for
EitherT.right.

val numberO: Option[Int] = Some(5)
val errorO: Option[String] = Some("Not a number")

val number: EitherT[Option, String, Int] = EitherT.right(numberO)
val error: EitherT[Option, String, Int] = EitherT.left(errorO)

From `Either[A, B]` or `F[Either[A, B]]` to `EitherT[F, A, B]` Copy Chapter

Use EitherT.fromEither to lift a value of Either[A, B] into EitherT[F, A, B].
An F[Either[A, B]] can be converted into EitherT using the EitherT constructor.

val numberE: Either[String, Int] = Right(100)
val errorE: Either[String, Int] = Left("Not a number")
val numberFE: List[Either[String, Int]] = List(Right(250))

val numberET: EitherT[List, String, Int] = EitherT.fromEither(numberE)
val errorET: EitherT[List, String, Int] = EitherT.fromEither(errorE)
val numberFET: EitherT[List, String, Int] = EitherT(numberFE)

From `Option[B]` or `F[Option[B]]` to `EitherT[F, A, B]` Copy Chapter

An Option[B] or an F[Option[B]], along with a default value, can be passed to
EitherT.fromOption and EitherT.fromOptionF, respectively, to produce an
EitherT. For F[Option[B]] and default F[A], there is EitherT.fromOptionM.

val myOption: Option[Int] = None
val myOptionList: List[Option[Int]] = List(None, Some(2), Some(3), None, Some(5))

val myOptionET = EitherT.fromOption[Future](myOption, "option not defined")
val myOptionListET = EitherT.fromOptionF(myOptionList, "option not defined")
val myOptionListETM = EitherT.fromOptionM(myOptionList, List("option not defined"))

From `ApplicativeError[F, E]` to `EitherT[F, E, A]` Copy Chapter

An ApplicativeError[F, E] or a MonadError[F, E], can be converted into EitherT[F, E, A]
using the attemptT method on them.

val myTry: Try[Int] = Try(2)
val myFuture: Future[String] = Future.failed(new Exception())

val myTryET: EitherT[Try, Throwable, Int] = myTry.attemptT
val myFutureET: EitherT[Future, Throwable, String] = myFuture.attemptT

Extracting an `F[Either[A, B]]` from an `EitherT[F, A, B]` Copy Chapter

Use the value method defined on EitherT to retrieve the underlying F[Either[A, B]]:

val errorT: EitherT[Future, String, Int] = EitherT.leftT("foo")

val error: Future[Either[String, Int]] = errorT.value

Datatypes Eval (`docs/datatypes/eval.md`) Copy Section

Eval

API Documentation: @:api(cats.Eval)

Eval is a data type for controlling synchronous evaluation.
Its implementation is designed to provide stack-safety at all times using a technique called trampolining.

There are two different factors that play into evaluation: memoization and laziness.

Memoized evaluation evaluates an expression only once and then remembers (memoizes) that value.
Lazy evaluation refers to when the expression is evaluated.
We talk about eager evaluation if the expression is immediately evaluated when defined and about lazy evaluation if the expression is evaluated when it's first used.

For example, in Scala, a lazy val is both lazy and memoized, a method definition def is lazy, but not memoized, since the body will be evaluated on every call.
A normal val evaluates eagerly and also memoizes the result.

Eval is able to express all of these evaluation strategies and allows us to chain computations using its Monad instance.

Eval.now

First of the strategies is eager evaluation, we can construct an Eval eagerly using Eval.now:

import cats.Eval
import cats.syntax.all._


val eager = Eval.now {
  println("Running expensive calculation...")
  1 + 2 * 3
}

We can run the computation using the given evaluation strategy anytime by using the value method.

eager.value

Eval.later

If we want lazy evaluation, we can use Eval.later:

val lazyEval = Eval.later {
  println("Running expensive calculation...")
  1 + 2 * 3
}

lazyEval.value

lazyEval.value

Notice that "Running expensive calculation" is printed only once, since the value was memoized internally.
Eval.later is different to using a lazy val in a few different ways.
First, it allows the runtime to perform garbage collection of the thunk after evaluation, leading to more memory being freed earlier.
Secondly, when lazy vals are evaluated, in order to preserve thread-safety, the Scala compiler will lock the whole surrounding class, whereas Eval will only lock itself.

Eval.always

If we want lazy evaluation, but without memoization akin to Function0, we can use Eval.always

val always = Eval.always {
  println("Running expensive calculation...")
  1 + 2 * 3
}

always.value

always.value

Here we can see, that the expression is evaluated every time we call .value.

Chaining lazy computations Copy Section

One of the most useful applications of Eval is its ability to chain together computations in a stack-safe way.
You can see one such usage when looking at the foldRight method found in Foldable.
Another great example are mutual tail-recursive calls:

object MutualRecursion {
  def even(n: Int): Eval[Boolean] =
    Eval.always(n == 0).flatMap {
      case true => Eval.True
      case false => odd(n - 1)
    }

  def odd(n: Int): Eval[Boolean] =
    Eval.always(n == 0).flatMap {
      case true => Eval.False
      case false => even(n - 1)
    }
}


MutualRecursion.odd(199999).value

Because Eval guarantees stack-safety, we can chain a lot of computations together using flatMap without fear of blowing up the stack.

You can also use Eval.defer to defer any computation that will return an Eval[A].
This is useful, because nesting a call to .value inside any of the Eval creation methods can be unsafe.

Datatypes Freeapplicative (`docs/datatypes/freeapplicative.md`) Copy Section

Free Applicative

API Documentation: @:api(cats.free.FreeApplicative)

FreeApplicatives are similar to Free (monads) in that they provide a nice way to represent
computations as data and are useful for building embedded DSLs (EDSLs). However, they differ
from Free in that the kinds of operations they support are limited, much like the distinction
between Applicative and Monad.

Dependency Copy Chapter

If you'd like to use cats' free applicative, you'll need to add a library dependency
for the cats-free module.

Example Copy Chapter

Consider building an EDSL for validating strings - to keep things simple we'll just have
a way to check a string is at least a certain size and to ensure the string contains numbers.

sealed abstract class ValidationOp[A]
case class Size(size: Int) extends ValidationOp[Boolean]
case object HasNumber extends ValidationOp[Boolean]

Much like the Free monad tutorial, we use smart constructors to lift our algebra into the FreeApplicative.

import cats.free.FreeApplicative
import cats.free.FreeApplicative.lift

type Validation[A] = FreeApplicative[ValidationOp, A]

def size(size: Int): Validation[Boolean] = lift(Size(size))

val hasNumber: Validation[Boolean] = lift(HasNumber)

Because a FreeApplicative only supports the operations of Applicative, we do not get the nicety
of a for-comprehension. We can however still use Applicative syntax provided by Cats.

import cats.syntax.all._

val prog: Validation[Boolean] = (size(5), hasNumber).mapN { case (l, r) => l && r}

As it stands, our program is just an instance of a data structure - nothing has happened
at this point. To make our program useful we need to interpret it.

import cats.Id
import cats.arrow.FunctionK
import cats.syntax.all._

// a function that takes a string as input
type FromString[A] = String => A

val compiler = new FunctionK[ValidationOp, FromString] {
  def apply[A](fa: ValidationOp[A]): FromString[A] = str =>
    fa match {
      case Size(size) => str.size >= size
      case HasNumber  => str.exists(c => "0123456789".contains(c))
    }
}

val validator = prog.foldMap[FromString](compiler)
validator("1234")
validator("12345")

Differences from `Free` Copy Chapter

So far everything we've been doing has been not much different from Free - we've built
an algebra and interpreted it. However, there are some things FreeApplicative can do that
Free cannot.

Recall a key distinction between the type classes Applicative and Monad - Applicative
captures the idea of independent computations, whereas Monad captures that of dependent
computations. Put differently Applicatives cannot branch based on the value of an existing/prior
computation. Therefore when using Applicatives, we must hand in all our data in one go.

In the context of FreeApplicatives, we can leverage this static knowledge in our interpreter.

Parallelism Copy Section

Because we have everything we need up front and know there can be no branching, we can easily
write a validator that validates in parallel.

import cats.data.Kleisli
import cats.syntax.all._
import scala.concurrent.Future
import scala.concurrent.ExecutionContext.Implicits.global

// recall Kleisli[Future, String, A] is the same as String => Future[A]
type ParValidator[A] = Kleisli[Future, String, A]

val parCompiler = new FunctionK[ValidationOp, ParValidator] {
  def apply[A](fa: ValidationOp[A]): ParValidator[A] = Kleisli { str =>
    fa match {
      case Size(size) => Future { str.size >= size }
      case HasNumber => Future { str.exists(c => "0123456789".contains(c)) }
    }
  }
}

val parValidator = prog.foldMap[ParValidator](parCompiler)

Logging Copy Section

We can also write an interpreter that simply creates a list of strings indicating the filters that
have been used - this could be useful for logging purposes. Note that we need not actually evaluate
the rules against a string for this, we simply need to map each rule to some identifier. Therefore
we can completely ignore the return type of the operation and return just a List[String] - the
Const data type is useful for this.

import cats.data.Const
import cats.syntax.all._

type Log[A] = Const[List[String], A]

val logCompiler = new FunctionK[ValidationOp, Log] {
  def apply[A](fa: ValidationOp[A]): Log[A] = fa match {
    case Size(size) => Const(List(s"size >= $size"))
    case HasNumber => Const(List("has number"))
  }
}

def logValidation[A](validation: Validation[A]): List[String] =
  validation.foldMap[Log](logCompiler).getConst

logValidation(prog)
logValidation(size(5) *> hasNumber *> size(10))
logValidation((hasNumber, size(3)).mapN(_ || _))

Why not both? Copy Section

It is perhaps more plausible and useful to have both the actual validation function and the logging
strings. While we could easily compile our program twice, once for each interpreter as we have above,
we could also do it in one go - this would avoid multiple traversals of the same structure.

Another useful property Applicatives have over Monads is that given two Applicatives F[_] and
G[_], their product type FG[A] = (F[A], G[A]) is also an Applicative. This is not true in the general
case for monads.

Therefore, we can write an interpreter that uses the product of the ParValidator and Log Applicatives
to interpret our program in one go. We can create this interpreter easily by using FunctionK#and.

import cats.data.Tuple2K

type ValidateAndLog[A] = Tuple2K[ParValidator, Log, A]

val prodCompiler: FunctionK[ValidationOp, ValidateAndLog] = parCompiler and logCompiler

val prodValidation = prog.foldMap[ValidateAndLog](prodCompiler)

The way FreeApplicative#foldMap works Copy Section

Despite being an imperative loop, there is a functional intuition behind FreeApplicative#foldMap.

The new FreeApplicative's foldMap is a sort of mutually-recursive function that operates on an argument stack and a
function stack, where the argument stack has type List[FreeApplicative[F, _]] and the functions have type List[Fn[G, _, _]].
Fn[G[_, _]] contains a function to be Ap'd that has already been translated to the target Applicative,
as well as the number of functions that were Ap'd immediately subsequently to it.

Main re-association loop

Pull an argument out of the stack, eagerly remove right-associated Ap nodes, by looping on the right and
adding the Ap nodes' arguments on the left to the argument stack; at the end, pushes a single function to the
function stack of the applied functions, the rest of which will be pushed in this loop in later iterations.
Once all of the Ap nodes on the right are removed, the loop resets to deal with the ones on the left.

Here's an example FreeApplicative value to demonstrate the loop's function, at the end of every iteration.
Every node in the tree is annotated with an identifying number and the concrete type of the node
(A -> Ap, L -> Lift, P -> Pure), and an apostrophe to denote where argF (the current argument) currently
points; as well the argument and function branches off Ap nodes are explicitly denoted.

==> begin.
           '1A
           /  \
       arg/    \fun
         /      \
        /        \
       2A        3A
   arg/  \fun arg/  \fun
     /    \     /    \
    4L    5P   6L     7L

args: Nil
functions: Nil
==> loop.

            1A
           /  \
       arg/    \fun
         /      \
        /        \
       2A        '3A
   arg/  \fun arg/  \fun
     /    \     /    \
    4L    5P   6L    7L

args: 2A :: Nil
functions: Nil
==> loop.

            1A
           /  \
       arg/    \fun
         /      \
        /        \
       2A         3A
   arg/  \fun arg/  \fun
     /    \     /    \
    4L    5P   6L   '7L

args: 6L :: 2A :: Nil
functions: Fn(gab = foldArg(7L), argc = 2) :: Nil
==> finished.

At the end of the loop the entire right branch of Aps under argF has been peeled off into a single curried function,
all of the arguments to that function are on the argument stack and that function itself is on the function stack,
annotated with the amount of arguments it takes.

Function application loop

Once argF isn't an Ap node, a loop runs which pulls functions from the stack until it reaches a curried function,
in which case it applies the function to argF transformed into a G[Any] value, and pushes the resulting function
back to the function stack, before returning to the main loop.

I'll continue the example from before here:

==> loop.
            1A
           /  \
       arg/    \fun
         /      \
        /        \
       2A         3A
   arg/  \fun arg/  \fun
     /    \     /    \
    4L    5P  '6L    7L

args: 2A :: Nil
functions: Fn(gab = foldArg(7L) ap foldArg(6L), argc = 1) :: Nil
==> finished.

At the end of this loop every function on the top of the function stack with length == 1 (not curried)
has been applied to a single argument from the argument stack, and the first curried function (length != 1)
on the stack has been applied to a single argument from the argument stack.
The reason we can't keep applying the curried function to arguments is that the node on top of the argument
stack must be an Ap node if the function is curried, so we can't translate it directly to G[_].

Once the last function has been applied to the last argument, the fold has finished and the result is returned.

References Copy Chapter

Deeper explanations can be found in this paper Free Applicative Functors by Paolo Capriotti

Datatypes Freemonad (`docs/datatypes/freemonad.md`) Copy Section

Free Monad

API Documentation: @:api(cats.free.Free)

What is it? Copy Chapter

A free monad is a construction which allows you to build a monad
from any Functor. Like other monads, it is a pure way to represent
and manipulate computations.

In particular, free monads provide a practical way to:

• represent stateful computations as data, and run them
• run recursive computations in a stack-safe way
• build an embedded DSL (domain-specific language)
• retarget a computation to another interpreter using natural transformations

(In Cats, the type representing a free monad is abbreviated as Free[_].)

Using Free Monads Copy Chapter

If you'd like to use Cats' free monad, you'll need to add a library dependency
for the cats-free module.

A good way to get a sense for how free monads work is to see them in
action. The next section uses Free[_] to create an embedded DSL
(Domain Specific Language).

If you're interested in the theory behind free monads, the
What is Free in theory? section discusses free monads
in terms of category theory.

Study your topic Copy Section

Let's imagine that we want to create a DSL for a key-value store. We
want to be able to do three things with keys:

• put a value into the store, associated with its key.
• get a value from the store given its key.
• delete a value from the store given its key.

The idea is to write a sequence of these operations in the embedded
DSL as a "program", compile the "program", and finally execute the
"program" to interact with the actual key-value store.

For example:

put("toto", 3)
get("toto") // returns 3
delete("toto")

But we want:

• the computation to be represented as a pure, immutable value
• to separate the creation and execution of the program
• to be able to support many different methods of execution

Study your grammar Copy Section

We have 3 commands to interact with our KeyValue store:

• Put a value associated with a key into the store
• Get a value associated with a key out of the store
• Delete a value associated with a key from the store

Create an ADT representing your grammar Copy Section

ADT stands for Algebraic Data Type. In this context, it refers to a
closed set of types which can be combined to build up complex,
recursive values.

We need to create an ADT to represent our key-value operations:

sealed trait KVStoreA[A]
case class Put[T](key: String, value: T) extends KVStoreA[Unit]
case class Get[T](key: String) extends KVStoreA[Option[T]]
case class Delete(key: String) extends KVStoreA[Unit]

Free your ADT Copy Section

There are five basic steps to "freeing" the ADT:

1. Create a type based on Free[_] and KVStoreA[_].
2. Create smart constructors for KVStore[_] using liftF.
3. Build a program out of key-value DSL operations.
4. Build a compiler for programs of DSL operations.
5. Execute our compiled program.

1. Create a `Free` type based on your ADT

import cats.free.Free

type KVStore[A] = Free[KVStoreA, A]

2. Create smart constructors using `liftF`

These methods will make working with our DSL a lot nicer, and will
lift KVStoreA[_] values into our KVStore[_] monad (note the
missing "A" in the second type).

import cats.free.Free.liftF

// Put returns nothing (i.e. Unit).
def put[T](key: String, value: T): KVStore[Unit] =
  liftF[KVStoreA, Unit](Put[T](key, value))

// Get returns a T value.
def get[T](key: String): KVStore[Option[T]] =
  liftF[KVStoreA, Option[T]](Get[T](key))

// Delete returns nothing (i.e. Unit).
def delete(key: String): KVStore[Unit] =
  liftF(Delete(key))

// Update composes get and set, and returns nothing.
def update[T](key: String, f: T => T): KVStore[Unit] =
  for {
    vMaybe <- get[T](key)
    _ <- vMaybe.map(v => put[T](key, f(v))).getOrElse(Free.pure(()))
  } yield ()

3. Build a program

Now that we can construct KVStore[_] values we can use our DSL to
write "programs" using a for-comprehension:

def program: KVStore[Option[Int]] =
  for {
    _ <- put("wild-cats", 2)
    _ <- update[Int]("wild-cats", (_ + 12))
    _ <- put("tame-cats", 5)
    n <- get[Int]("wild-cats")
    _ <- delete("tame-cats")
  } yield n

This looks like a monadic flow. However, it just builds a recursive
data structure representing the sequence of operations.

4. Write a compiler for your program

As you may have understood now, Free[_] is used to create an embedded
DSL. By itself, this DSL only represents a sequence of operations
(defined by a recursive data structure); it doesn't produce anything.

Free[_] is a programming language inside your programming language!

So, like any other programming language, we need to compile our
abstract language into an effective language and then run it.

To do this, we will use a natural transformation between type
containers. Natural transformations go between types like F[_] and
G[_] (this particular transformation would be written as
FunctionK[F,G] or as done here using the symbolic
alternative as F ~> G).

In our case, we will use a simple mutable map to represent our key
value store:

import cats.arrow.FunctionK
import cats.{Id, ~>}
import scala.collection.mutable

// the program will crash if a type is incorrectly specified.
def impureCompiler: KVStoreA ~> Id  =
  new (KVStoreA ~> Id) {

    // a very simple (and imprecise) key-value store
    val kvs = mutable.Map.empty[String, Any]

    def apply[A](fa: KVStoreA[A]): Id[A] =
      fa match {
        case Put(key, value) =>
          println(s"put($key, $value)")
          kvs(key) = value
          ()
        case Get(key) =>
          println(s"get($key)")
          kvs.get(key).asInstanceOf[A]
        case Delete(key) =>
          println(s"delete($key)")
          kvs.remove(key)
          ()
      }
  }

Please note this impureCompiler is impure -- it mutates kvs and
also produces logging output using println. The whole purpose of
functional programming isn't to prevent side-effects, it is just to
push side-effects to the boundaries of your system in a well-known and
controlled way.

Id[_] represents the simplest type container: the type itself. Thus,
Id[Int] is just Int. This means that our program will execute
immediately, and block until the final value can be returned.

However, we could easily use other type containers for different
behavior, such as:

• Future[_] for asynchronous computation
• List[_] for gathering multiple results
• Option[_] to support optional results
• Either[E, *] to support failure
• a pseudo-random monad to support non-determinism
• and so on...

5. Run your program

The final step is naturally running your program after compiling it.

Free[_] is just a recursive structure that can be seen as sequence
of operations producing other operations. In this way it is similar to
List[_]. We often use folds (e.g. foldRight) to obtain a single
value from a list; this recurses over the structure, combining its
contents.

The idea behind running a Free[_] is exactly the same. We fold the
recursive structure by:

• consuming each operation.
• compiling the operation into our effective language using
  impureCompiler (applying its effects if any).
• computing next operation.
• continue recursively until reaching a Pure state, and returning it.

This operation is called Free.foldMap:

final def foldMap[M[_]](f: FunctionK[S,M])(M: Monad[M]): M[A] = ...

M must be a Monad to be flattenable (the famous monoid aspect
under Monad). As Id is a Monad, we can use foldMap.

To run your Free with previous impureCompiler:

val result: Option[Int] = program.foldMap(impureCompiler)

An important aspect of foldMap is its stack-safety. It evaluates
each step of computation on the stack then unstack and restart. This
process is known as trampolining.

As long as your natural transformation is stack-safe, foldMap will
never overflow your stack. Trampolining is heap-intensive but
stack-safety provides the reliability required to use Free[_] for
data-intensive tasks, as well as infinite processes such as streams.

6. Use a pure compiler (optional)

The previous examples used an effectful natural transformation. This
works, but you might prefer folding your Free in a "purer" way. The
State data structure can be used to keep track of the program
state in an immutable map, avoiding mutation altogether.

import cats.data.State

type KVStoreState[A] = State[Map[String, Any], A]
val pureCompiler: KVStoreA ~> KVStoreState = new (KVStoreA ~> KVStoreState) {
  def apply[A](fa: KVStoreA[A]): KVStoreState[A] =
    fa match {
      case Put(key, value) => State.modify(_.updated(key, value))
      case Get(key) =>
        State.inspect(_.get(key).asInstanceOf[A])
      case Delete(key) => State.modify(_ - key)
    }
}

(You can see that we are again running into some places where Scala's
support for pattern matching is limited by the JVM's type erasure, but
it's not too hard to get around.)

val result: (Map[String, Any], Option[Int]) = program.foldMap(pureCompiler).run(Map.empty).value

Composing Free monads ADTs. Copy Chapter

Real world applications often time combine different algebras.
The injection type class described by Swierstra in Data types à la carte
lets us compose different algebras in the context of Free.

Let's see a trivial example of unrelated ADT's getting composed as a EitherK that can form a more complex program.

import cats.data.EitherK
import cats.free.Free
import cats.{Id, InjectK, ~>}
import scala.collection.mutable.ListBuffer

/* Handles user interaction */
sealed trait Interact[A]
case class Ask(prompt: String) extends Interact[String]
case class Tell(msg: String) extends Interact[Unit]

/* Represents persistence operations */
sealed trait DataOp[A]
case class AddCat(a: String) extends DataOp[Unit]
case class GetAllCats() extends DataOp[List[String]]

Once the ADTs are defined we can formally state that a Free program is the EitherK of its Algebras.

type CatsApp[A] = EitherK[DataOp, Interact, A]

In order to take advantage of monadic composition we use smart constructors to lift our Algebra to the Free context.

class Interacts[F[_]](implicit I: InjectK[Interact, F]) {
  def tell(msg: String): Free[F, Unit] = Free.liftInject[F](Tell(msg))
  def ask(prompt: String): Free[F, String] = Free.liftInject[F](Ask(prompt))
}

object Interacts {
  implicit def interacts[F[_]](implicit I: InjectK[Interact, F]): Interacts[F] = new Interacts[F]
}

class DataSource[F[_]](implicit I: InjectK[DataOp, F]) {
  def addCat(a: String): Free[F, Unit] = Free.liftInject[F](AddCat(a))
  def getAllCats: Free[F, List[String]] = Free.liftInject[F](GetAllCats())
}

object DataSource {
  implicit def dataSource[F[_]](implicit I: InjectK[DataOp, F]): DataSource[F] = new DataSource[F]
}

ADTs are now easily composed and trivially intertwined inside monadic contexts.

def program(implicit I : Interacts[CatsApp], D : DataSource[CatsApp]): Free[CatsApp, Unit] = {

  import I._, D._

  for {
    cat <- ask("What's the kitty's name?")
    _ <- addCat(cat)
    cats <- getAllCats
    _ <- tell(cats.toString)
  } yield ()
}

Finally we write one interpreter per ADT and combine them with a FunctionK to EitherK so they can be
compiled and applied to our Free program.

def readLine(): String = "snuggles"

object ConsoleCatsInterpreter extends (Interact ~> Id) {
  def apply[A](i: Interact[A]) = i match {
    case Ask(prompt) =>
      println(prompt)
      readLine()
    case Tell(msg) =>
      println(msg)
  }
}

object InMemoryDatasourceInterpreter extends (DataOp ~> Id) {

  private[this] val memDataSet = new ListBuffer[String]

  def apply[A](fa: DataOp[A]) = fa match {
    case AddCat(a) => memDataSet.append(a); ()
    case GetAllCats() => memDataSet.toList
  }
}

val interpreter: CatsApp ~> Id = InMemoryDatasourceInterpreter or ConsoleCatsInterpreter

Now if we run our program and type in "snuggles" when prompted, we see something like this:

import DataSource._, Interacts._

val evaled: Unit = program.foldMap(interpreter)

For the curious ones: what is Free in theory? Copy Chapter

Mathematically-speaking, a free monad (at least in the programming
language context) is a construction that is left adjoint to a
forgetful functor whose domain is the category of Monads and whose
co-domain is the category of Endofunctors. Huh?

Concretely, it is just a clever construction that allows us to build a
very simple Monad from any functor.

The above forgetful functor takes a Monad and:

• forgets its monadic part (e.g. the flatMap function)
• forgets its pointed part (e.g. the pure function)
• finally keeps the functor part (e.g. the map function)

By reversing all arrows to build the left-adjoint, we deduce that the
free monad is basically a construction that:

• takes a functor
• adds the pointed part (e.g. pure)
• adds the monadic behavior (e.g. flatMap)

In terms of implementation, to build a monad from a functor we use
the following classic inductive definition:

sealed abstract class Free[F[_], A]
case class Pure[F[_], A](a: A) extends Free[F, A]
case class Suspend[F[_], A](a: F[Free[F, A]]) extends Free[F, A]

(This generalizes the concept of fixed point functor.)

In this representation:

• Pure builds a Free instance from an A value (it reifies the
  pure function)
• Suspend builds a new Free by applying F to a previous Free
  (it reifies the flatMap function)

So a typical Free structure might look like:

Suspend(F(Suspend(F(Suspend(F(....(Pure(a))))))))

Free is a recursive structure. It uses A in F[A] as the
recursion "carrier" with a terminal element Pure.

From a computational point of view, Free recursive structure can be
seen as a sequence of operations.

• Pure returns an A value and ends the entire computation.
• Suspend is a continuation; it suspends the current computation
  with the suspension functor F (which can represent a command for
  example) and hands control to the caller. A represents a value
  bound to this computation.

Please note this Free construction has the interesting quality of
encoding the recursion on the heap instead of the stack as classic
function calls would. This provides the stack-safety we heard about
earlier, allowing very large Free structures to be evaluated safely.

For the very curious ones Copy Section

If you look at implementation in cats, you will see another member of
the Free[_] ADT:

case class FlatMapped[S[_], B, C](c: Free[S, C], f: C => Free[S, B]) extends Free[S, B]

FlatMapped represents a call to a subroutine c and when c is
finished, it continues the computation by calling the function f
with the result of c.

It is actually an optimization of Free structure allowing to solve a
problem of quadratic complexity implied by very deep recursive Free
computations.

It is exactly the same problem as repeatedly appending to a List[_].
As the sequence of operations becomes longer, the slower a flatMap
"through" the structure will be. With FlatMapped, Free becomes a
right-associated structure not subject to quadratic complexity.

FreeT Copy Chapter

Often times we want to interleave the syntax tree when building a Free monad
with some other effect not declared as part of the ADT.
FreeT solves this problem by allowing us to mix building steps of the AST
with calling action in other base monad.

In the following example a basic console application is shown.
When the user inputs some text we use a separate State monad to track what the user
typed.

As we can observe in this case FreeT offers us the alternative to delegate denotations to State
monad with stronger equational guarantees than if we were emulating the State ops in our own ADT.

/* Detailed source-code truncated for AI context efficiency. */

Another example is more basic usage of FreeT with some context Ctx for which we provide Try interpreter,
combined with OptionT for reducing boilerplate.

import cats.free._
import cats._
import cats.data._
import cats.syntax.all._
import scala.util.Try

sealed trait Ctx[A]

case class Action(value: Int) extends Ctx[Int]

def op1: FreeT[Ctx, Option, Int] =
  FreeT.liftF[Ctx, Option, Int](Action(7))

def op2: FreeT[Ctx, Option, Int] =
  FreeT.liftT[Ctx, Option, Int](Some(4))

def op3: FreeT[Ctx, Option, Int] =
  FreeT.pure[Ctx, Option, Int](1)

val opComplete: FreeT[Ctx, Option, Int] =
  for {
    a <- op1
    b <- op2
    c <- op3
  } yield a + b + c


/*  Our interpreters  */

type OptTry[A] = OptionT[Try, A]

def tryInterpreter: Ctx ~> OptTry = new (Ctx ~> OptTry) {
  def apply[A](fa: Ctx[A]): OptTry[A] = {
    fa match {
      case Action(value) =>
        OptionT.liftF(Try(value))
    }
  }
}

def optTryLift: Option ~> OptTry = new (Option ~> OptTry) {
  def apply[A](fa: Option[A]): OptTry[A] = {
    fa match {
      case Some(value) =>
        OptionT(Try(Option(value)))
      case None =>
        OptionT.none
    }
  }
}

val hoisted = opComplete.hoist(optTryLift)
val evaluated = hoisted.foldMap(tryInterpreter)
val result = evaluated.value

Future Work (TODO) Copy Chapter

There are many remarkable uses of Free[_]. In the future, we will
include some here, such as:

• Trampoline
• Option
• Iteratee
• Source
• etc...

We will also discuss the Coyoneda Trick.

Credits Copy Chapter

This article was written by
Pascal Voitot and edited by other
members of the Cats community.

Datatypes Functionk (`docs/datatypes/functionk.md`) Copy Section

FunctionK

API Documentation: @:api(cats.arrow.FunctionK)

A FunctionK transforms values from one first-order-kinded type (a type that takes a single type
parameter, such as List or Option) into another first-order-kinded type. This transformation is
universal, meaning that a FunctionK[List, Option] will translate all List[A] values into an
Option[A] value for all possible types of A. This explanation may be easier to understand if we
first step back and talk about ordinary functions.

Ordinary Functions Copy Chapter

Consider the following scala method:

def first(l: List[Int]): Option[Int] = l.headOption

This isn't a particularly helpful method, but it will work as an example. Instead of writing this as a
method, we could have written this as a function value:

val first: List[Int] => Option[Int] = l => l.headOption

And here, => is really just some syntactic sugar for Function1, so we could also write that as:

val first: Function1[List[Int], Option[Int]] = l => l.headOption

Let's cut through the syntactic sugar even a little bit further. Function1 isn't really a special type.
It's just a trait that looks something like this:

// we are calling this `MyFunction1` so we don't collide with the actual `Function1`
trait MyFunction1[A, B] {
  def apply(a: A): B
}

So if we didn't mind being a bit verbose, we could have written our function as:

val first: Function1[List[Int], Option[Int]] = new Function1[List[Int], Option[Int]] {
  def apply(l: List[Int]): Option[Int] = l.headOption
}

Abstracting via Generics Copy Chapter

Recall our first method:

def first(l: List[Int]): Option[Int] = l.headOption

The astute reader may have noticed that there's really no reason that this method needs to be tied directly to Int. We could use generics to make this a bit more general:

def first[A](l: List[A]): Option[A] = l.headOption

But how would we represent this new first method as a =>/Function1 value? We are looking for something like a type of List[A] => Option[A] forAll A, but this isn't valid scala syntax. Function1 isn't quite the right fit, because its apply method doesn't take a generic type parameter.

Higher Kinds to the Rescue Copy Chapter

It turns out that we can represent our universal List to Option transformation with something that looks a bit like Function1 but
that adds a type parameter to the apply method and utilizes higher kinds:

trait MyFunctionK[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

Cats provides this type as FunctionK (we used MyFunctionK for our example type to avoid confusion). So now we can write first as a FunctionK[List, Option] value:

import cats.arrow.FunctionK

val first: FunctionK[List, Option] = new FunctionK[List, Option] {
  def apply[A](l: List[A]): Option[A] = l.headOption
}

Syntactic Sugar Copy Chapter

If the example above looks a bit too verbose for you, the kind-projector
compiler plugin provides a more concise syntax.
After adding the plugin to your project, you could write the first example as:

val first: FunctionK[List, Option] = λ[FunctionK[List, Option]](_.headOption)

Cats also provides a ~> type alias for FunctionK, so an even more concise version would be:

import cats.~>

val first: List ~> Option = λ[List ~> Option](_.headOption)

Being able to use ~> as an alias for FunctionK parallels being able to use => as an alias for Function1.

Use-cases Copy Chapter

FunctionK tends to show up when there is abstraction over higher-kinds. For example, interpreters for free monads and free applicatives are represented as FunctionK instances.

Types with more than one type parameter Copy Chapter

Earlier it was mentioned that FunctionK operates on first-order-kinded types (types that take a single type parameter such as List or Option). It's still possible to use FunctionK with types that would normally take more than one type parameter (such as Either) if we fix all of the type parameters except for one. For example:

type ErrorOr[A] = Either[String, A]

val errorOrFirst: FunctionK[List, ErrorOr] =
  λ[FunctionK[List, ErrorOr]](_.headOption.toRight("ERROR: the list was empty!"))

Natural Transformation Copy Chapter

In category theory, a natural transformation provides a morphism between Functors while preserving the internal structure. It's one of the most fundamental notions of category theory.

If we have two Functors F and G, FunctionK[F, G] is a natural transformation via parametricity. That is, given fk: FunctionK[F, G], for all functions A => B and all fa: F[A] the following are equivalent:

fk(F.map(fa)(f)) <-> G.map(fk(fa))(f)

We don't need to write a law to test the implementation of the fk for the above to be true. It's automatically given by parametricity.

Thus natural transformation can be implemented in terms of FunctionK. This is why a parametric polymorphic function FunctionK[F, G] is sometimes referred as a natural transformation. However, they are two different concepts that are not isomorphic.

For more details, Bartosz Milewski has written a great blog post titled
"Parametricity: Money for Nothing and Theorems for Free".

Datatypes Id (`docs/datatypes/id.md`) Copy Section

Id

API Documentation: Id

The identity monad can be seen as the ambient monad that encodes the
effect of having no effect. It is ambient in the sense that plain pure
values are values of Id.

It is encoded as:

type Id[A] = A

That is to say that the type Id[A] is just a synonym for A. We can
freely treat values of type A as values of type Id[A], and
vice-versa.

import cats._

val x: Id[Int] = 1
val y: Int = x

Using this type declaration, we can treat our Id type constructor as a
Monad and as a Comonad. The pure
method, which has type A => Id[A] just becomes the identity
function. The map method from Functor just becomes function
application:

import cats.Functor

val one: Int = 1
Functor[Id].map(one)(_ + 1)

Compare the signatures of map and flatMap and coflatMap:

def map[A, B](fa: Id[A])(f: A => B): Id[B]
  def flatMap[A, B](fa: Id[A])(f: A => Id[B]): Id[B]
  def coflatMap[A, B](a: Id[A])(f: Id[A] => B): Id[B]

You'll notice that in the flatMap signature, since Id[B] is the same
as B for all B, we can rewrite the type of the f parameter to be
A => B instead of A => Id[B], and this makes the signatures of the
two functions the same, and, in fact, they can have the same
implementation, meaning that for Id, flatMap is also just function
application:

import cats.Monad

val one: Int = 1
Monad[Id].map(one)(_ + 1)
Monad[Id].flatMap(one)(_ + 1)

And that similarly, coflatMap is just function application:

import cats.Comonad

Comonad[Id].coflatMap(one)(_ + 1)

Datatypes Ior (`docs/datatypes/ior.md`) Copy Section

Ior

API Documentation: @:api(cats.data.Ior)

Ior represents an inclusive-or relationship between two data types.
This makes it very similar to the Either data type, which represents an "exclusive-or" relationship.
What this means, is that an Ior[A, B] (also written as A Ior B) can contain either an A, a B, or both an A and B.
Another similarity to Either is that Ior is right-biased,
which means that the map and flatMap functions will work on the right side of the Ior, in our case the B value.
You can see this in the function signature of map:

def map[B, C](fa: A Ior B)(f: B => C): A Ior C

We can create Ior values using Ior.left, Ior.right and Ior.both:

import cats.data._

val right = Ior.right[String, Int](3)

val left = Ior.left[String, Int]("Error")

val both = Ior.both("Warning", 3)

Cats also offers syntax enrichment for Ior. The leftIor and rightIor functions can be imported from cats.syntax.ior._:

import cats.syntax.all._

val right = 3.rightIor

val left = "Error".leftIor

When we look at the Monad or Applicative instances of Ior, we can see that they actually require a Semigroup instance on the left side.
This is because Ior will actually accumulate failures on the left side, very similar to how the Validated data type does.
This means we can accumulate data on the left side while also being able to short-circuit upon the first left-side-only value.
For example, sometimes, we might want to accumulate warnings together with a valid result and only halt the computation on a "hard error"
Here's an example of how we might be able to do that:

import cats.syntax.all._
import cats.data.{ NonEmptyChain => Nec, Ior}


type Failures = Nec[String]

case class Username(value: String) extends AnyVal
case class Password(value: String) extends AnyVal

case class User(name: Username, pw: Password)

def validateUsername(u: String): Failures Ior Username = {
  if (u.isEmpty)
    Nec.one("Can't be empty").leftIor
  else if (u.contains("."))
    Ior.both(Nec.one("Dot in name is deprecated"), Username(u))
  else
    Username(u).rightIor
}

def validatePassword(p: String): Failures Ior Password = {
  if (p.length < 8)
    Nec.one("Password too short").leftIor
  else if (p.length < 10)
    Ior.both(Nec.one("Password should be longer"), Password(p))
  else
    Password(p).rightIor
}

def validateUser(name: String, password: String): Failures Ior User =
  (validateUsername(name), validatePassword(password)).mapN(User)

Now we're able to validate user data and also accumulate non-fatal warnings:

validateUser("John", "password12")

validateUser("john.doe", "password")

validateUser("jane", "short")

To extract the values, we can use the fold method, which expects a function for each case the Ior can represent:

validateUser("john.doe", "password").fold(
  errorNec => s"Error: ${errorNec.head}",
  user => s"Success: $user",
  (warnings, user) => s"Warning: ${user.name.value}; The following warnings occurred: ${warnings.show}"
)

Using with NonEmptyChain Copy Chapter

Similar to Validated, there is also a type alias for using a NonEmptyChain on the left side.

import cats.data.NonEmptyChain

type IorNec[B, A] = Ior[NonEmptyChain[B], A]

import cats.syntax.all._, cats.data.NonEmptyChain

val left: IorNec[String, Int] = Ior.fromEither("Error".leftNec[Int])

Conversions Copy Chapter

We can also convert our Ior to Either, Validated or Option.
All of these conversions will discard the left side value if both are available:

Ior.both("Warning", 42).toEither

Datatypes Iort (`docs/datatypes/iort.md`) Copy Section

IorT

API Documentation: @:api(cats.data.IorT)

IorT[F[_], A, B] is a light wrapper on an F[Ior[A, B]]. Similar to
OptionT[F[_], A] and EitherT[F[_], A, B], it is a monad transformer for
Ior, that can be more convenient to work with than using F[Ior[A, B]]
directly.

The boilerplate Copy Chapter

Consider the following program that uses Ior to propagate log messages when
validating an address:

import cats.data.Ior
import cats.data.{ NonEmptyChain => Nec }
import cats.syntax.all._
import scala.util.{Success, Try}

type Logs = Nec[String]

def parseNumber(input: String): Ior[Logs, Option[Int]] =
  Try(input.trim.toInt) match {
    case Success(number) if number > 0 => Ior.Right(Some(number))
    case Success(_) => Ior.Both(Nec.one(s"'$input' is non-positive number"), None)
    case _ => Ior.Both(Nec.one(s"'$input' is not a number"), None)
  }

def parseStreet(input: String): Ior[Logs, String] = {
  if (input.trim.isEmpty)
    Ior.Left(Nec.one(s"'$input' is not a street"))
  else
    Ior.Right(input)
}

def numberToString(number: Option[Int]): Ior[Logs, String] =
  number match {
    case Some(n) => Ior.Right(n.toString)
    case None => Ior.Both(Nec.one("used default address number"), "n/a")
  }

def addressProgram(numberInput: String, streetInput: String): Ior[Logs, String] =
  for {
    number <- parseNumber(numberInput)
    street <- parseStreet(streetInput)
    sNumber <- numberToString(number)
  } yield s"$sNumber, $street"

Due to the monadic nature of Ior combining the results of parseNumber,
parseStreet, and numberToString can be as concise as a for-comprehension.
As the following examples demonstrate, log messages of the different processing
steps are combined when using flatMap.

addressProgram("7", "Buckingham Palace Rd")
addressProgram("SW1W", "Buckingham Palace Rd")
addressProgram("SW1W", "")

Suppose parseNumber, parseStreet, and numberToString are rewritten to be
asynchronous and return Future[Ior[Logs, *]] instead. The for-comprehension
can no longer be used since addressProgram must now compose Future and
Ior together, which means that the error handling must be performed
explicitly to ensure that the proper types are returned:

import scala.concurrent.Future
import scala.concurrent.ExecutionContext.Implicits.global

def parseNumberAsync(input: String): Future[Ior[Logs, Option[Int]]] =
  Future.successful(parseNumber(input))

def parseStreetAsync(input: String): Future[Ior[Logs, String]] =
  Future.successful(parseStreet(input))

def numberToStringAsync(number: Option[Int]): Future[Ior[Logs, String]] =
  Future.successful(numberToString(number))

def programHelper(number: Option[Int], streetInput: String): Future[Ior[Logs, String]] =
  parseStreetAsync(streetInput).flatMap { streetIor =>
    numberToStringAsync(number).map { sNumberIor =>
      for {
        street <- streetIor
        sNumber <- sNumberIor
      } yield s"$sNumber, $street"
    }
  }

def addressProgramAsync(numberInput: String, streetInput: String): Future[Ior[Logs, String]] =
  parseNumberAsync(numberInput).flatMap {
    case Ior.Left(logs) => Future.successful(Ior.Left(logs))
    case Ior.Right(number) => programHelper(number, streetInput)
    case b @ Ior.Both(_, number) => programHelper(number, streetInput).map(s => b.flatMap(_ => s))
  }

To keep some readability the program was split in two parts, otherwise code
would be repeated. Note that when parseNumberAsync returns an Ior.Both it
is necessary to combine it with the result of programHelper, otherwise some
log messages would be lost.

import scala.concurrent.Await
import scala.concurrent.duration._

Await.result(addressProgramAsync("7", "Buckingham Palace Rd"), 1.second)
Await.result(addressProgramAsync("SW1W", "Buckingham Palace Rd"), 1.second)
Await.result(addressProgramAsync("SW1W", ""), 1.second)

IorT to the rescue Copy Chapter

The program of the previous section can be re-written using IorT as follows:

import cats.data.IorT

def addressProgramAsyncIorT(numberInput: String, streetInput: String): IorT[Future, Logs, String] =
  for {
    number <- IorT(parseNumberAsync(numberInput))
    street <- IorT(parseStreetAsync(streetInput))
    sNumber <- IorT(numberToStringAsync(number))
  } yield s"$sNumber, $street"

This version of addressProgramAsync is almost as concise as the
non-asynchronous version. Note that when F is a monad, then IorT will also
form a monad, allowing monadic combinators such as flatMap to be used in
composing IorT values.

Await.result(addressProgramAsyncIorT("7", "Buckingham Palace Rd").value, 1.second)
Await.result(addressProgramAsyncIorT("SW1W", "Buckingham Palace Rd").value, 1.second)
Await.result(addressProgramAsyncIorT("SW1W", "").value, 1.second)

Looking back at the implementation of parseStreet the return type could be
Either[Logs, String] instead. Thinking of situations like this, where not all
the types match, IorT provides factory methods of IorT[F, A, B] from:

• A, B or both
• F[A], F[B] or both
• Ior[A, B] or F[Ior[A, B]]
• Either[A, B] or F[Either[A, B]]
• Option[B] or F[Option[B]]
• A Boolean test