scalaz

A left disjunction

Often used to represent the failure case of a result

Type-aligned pair. Isomorphic to

(F[A], G[A]) forSome { type A }

but more robust with respect to type inference.

Notation is conjunction /\ blended with ~, which is often used to indicate higher kindedness.

The coproduct (or free product) of monoids M and N. Conceptually this is an alternating list of M and N values, with the identity as the empty list, and composition as list concatenation that combines adjacent elements when possible.

An immutable map of key/value pairs implemented as a balanced binary tree

Based on Haskell's Data.Map

An adjunction formed by two functors F and G such that F is left-adjoint to G. The composite functor GF is a monad and the composite functor FG is a comonad.

The minimal definition is either (unit, counit) or (leftAdjunct, rightAdjunct)

An algebraic data type representing the characters 'a' to 'z'

https://hackage.haskell.org/package/semigroupoids-5.2.2/docs/Data-Functor-Alt.html

Derive a Semigroup or Monoid instance from a Plus or PlusEmpty.

https://hackage.haskell.org/package/reducers-3.12.1/docs/Data-Semigroup-Alt.html#t:Alter

Derive a Semigroup or Monoid instance from an Apply or Applicative.

https://hackage.haskell.org/package/reducers-3.12.1/docs/Data-Semigroup-Applicative.html#t:Ap

Applicative Functor, described in Applicative Programming with Effects

Whereas a scalaz.Functor allows application of a pure function to a value in a context, an Applicative also allows application of a function in a context to a value in a context (ap).

It follows that a pure function can be applied to arguments in a context. (See apply2, apply3, ... )

Applicative instances come in a few flavours:

• All scalaz.Monads are also Applicative
• Any scalaz.Monoid can be treated as an Applicative (see scalaz.Monoid#applicative)
• Zipping together corresponding elements of Naperian data structures (those of of a fixed, possibly infinite shape)

scalaz.Applicative combined with scalaz.PlusEmpty.

scalaz.Applicative without point.

A scalaz.Category supporting all ordinary functions, as well as combining arrows product-wise. Every Arrow forms a scalaz.Contravariant in one type parameter, and a scalaz.Applicative in the other, just as with ordinary functions.

scalaz.Semigroup which is also idempotent, i.e. appending a value with itself results in the same value.

A constrained transformation natural in both sides of a bifunctor

A function universally quantified over two parameters.

A type giving rise to two unrelated scalaz.Foldables.

A type giving rise to two unrelated scalaz.Functors.

An scalaz.Apply functor, where a lifted function can introduce new values and new functor context to be incorporated into the lift context. The essential new operation of scalaz.Monads.

scalaz.Bind capable of using constant stack space when doing recursive binds.

Implementations of tailrecM should not make recursive calls without the @tailrec annotation.

Based on Phil Freeman's work on stack safety in PureScript, described in Stack Safety for Free.

A type giving rise to two unrelated scalaz.Traverses.

scalaz.Compose with identity.

A cofree comonad for some functor S, i.e. an S-branching stream.

A constrained natural transformation

Contravariant functors. For example, functions provide a scalaz.Functor in their result type, but a scalaz.Contravariant for each argument type.

Note that the dual of a scalaz.Functor is just a scalaz.Functor itself.

Providing an instance of this is a useful alternative to marking a type parameter with - in Scala.

Decomposition of fi.contramap(k) into its components, as it is frequently convenient to apply k separately from sorting or whatever process with fi, even when B is unknown, which is very common.

This is isomorphic to F as long as F itself is a contravariant functor. The homomorphism from F[A] to ContravariantCoyoneda[F,A] exists even when F is not a contravariant functor.

See ContravariantCoyonedaUsage.scala in the scalaz source tree for an interesting usage demonstration.

As ContravariantCoyoneda(o)(identity).unlift = o, further factoring can occur as follows, for free:

ContravariantCoyoneda(o contramap g)(f).unlift =
 ContravariantCoyoneda(o)(g compose f).unlift

F on the left, and G on the right, of scalaz.\/.

A Cord is a purely functional data structure for efficiently creating a String from smaller parts, useful for printing ADTs that must write out their contents into a text format.

A z interpolator is available for building String from literals, using the Show typeclass to populate each "hole", and a cord interpolator for building Cord instances.

If a more efficient solution is required to write a large String to a network socket or file, consider https://github.com/scalaz/scalaz/issues/1797

If you require a general text manipulation data structure, consider using FingerTree or creating a custom structure to resemble that used by the popular text editors:

• https://ecc-comp.blogspot.co.uk/2015/05/a-brief-glance-at-how-5-text-editors.html
• https://pavelfatin.com/typing-with-pleasure/

The corecursive list; i.e. the arguments to unfold saved off to a data structure. Generally does not have methods itself; as with scalaz.NonEmptyList, it provides typeclass instances instead, and you typically import typeclass syntax to get methods.

The corecursive list can be a very efficient way to represent "listlike" things in some cases; because it is so unlike "normal" collections, though, it's important to understand how its operations are implemented and what their performance characteristics are going to be. For example, using cons iteratively to add a bunch of elements to the beginning of a scala.collection.immutable.List is very efficient; it's very ''inefficient'' for corecursive list.

Operations are generally designed to preserve the isomorphism with scalaz.EphemeralStream; for example, ap could be a "zipping" ap, but instead is a less efficient "combination" style. This means that the scalaz.Monad has the same behavior as that of scalaz.EphemeralStream and more traditional strict list structures.

Corepresentable functors

The dual view of the Yoneda lemma. Also a free functor on F. This is isomorphic to F as long as F itself is a functor. The homomorphism from F[A] to Coyoneda[F,A] exists even when F is not a functor.

Difference lists: a data structure for O(1) append on lists. Based on Data.DList, a Haskell library by Don Stewart.

A difference list is a function that given a list, returns the original contents of the difference list prepended at the given list.

This structure supports O(1) append and snoc operations on lists, making it very useful for append-heavy uses, such as logging and pretty printing.

Covariant Day Convolution

Based on Edward Kmett implementation in Haskell: https://hackage.haskell.org/package/kan-extensions/docs/Data-Functor-Day.html

Day convolution is a special form of Functor multiplication. In monoidal category of endofunctors Applicative is a monoid object when Day covolution is used as tensor. If we use Functor composition as tensor then then monoid form a Monad instead of Applicative.

Can be seen as generalization of method apply2 from Apply:

def apply2(fa => F[A], fb => F[B])(f: (A, B) => C): F[C]

trait Day[F[_], G[_], A] { self =>
 // ...
 val fx: F[X]
 val gy: G[Y]
 def xya: (X, Y) => A
}

Coproduct analogue of Divide

https://hackage.haskell.org/package/contravariant-1.4.1/docs/Data-Functor-Contravariant-Divisible.html#t:Decidable

Density Comonad.

Density is Left Kan Extension where both Functors are the same.

Without any restrictions on F we can define Functor, Cobind, Comonad for Density[F]. Density is Comonad for free.

A Double-ended queue, based on the Bankers Double Ended Queue as described by C. Okasaki in "Purely Functional Data Structures"

A queue that allows items to be put onto either the front (cons) or the back (snoc) of the queue in constant time, and constant time access to the element at the very front or the very back of the queue. Dequeueing an element from either end is constant time when amortized over a number of dequeues.

This queue maintains an invariant that whenever there are at least two elements in the queue, neither the front list nor back list are empty. In order to maintain this invariant, a dequeue from either side which would leave that side empty constructs the resulting queue by taking elements from the opposite side

Implementation of a Discrete Interval Encoding Tree https://web.engr.oregonstate.edu/~erwig/diet/ that is actually implemented using a Vector and is balanced at all times as a result.

An algebraic data type representing the digits 0 - 9

Dual of scalaz.Traverse. To transform F[G[B]] to G[F[B]], you may use Traverse[F] and Applicative[G], but alternatively Functor[F] and Distributive[G], which permits greater sharing and nonstrictness.

Divide is the contravariant analogue of scalaz.Apply

Divisible is the contravariant analogue of scalaz.Applicative

Represents a computation of type F[A \/ B].

Example:

val x: Option[String \/ Int] = Some(\/-(1))
EitherT(x).map(1+).run // Some(\/-(2))

Endomorphisms. They have special properties among functions, so are captured in this newtype.

Endomorphisms using by-name evaluation. They have special properties among functions, so are captured in this newtype.

Endomorphisms have special properties among arrows, so are captured in this newtype.

Endomorphic[Function1, A] is equivalent to Endo[A]

An scalaz.Orderable with discrete values.

Like scala.collection.immutable.Stream, but doesn't save computed values. As such, it can be used to represent similar things, but without the space leak problem frequently encountered using that type.

A type safe alternative to universal equality (scala.Any#==).

Finger trees with leaves of type A and Nodes that are annotated with type V.

Finger Trees provide a base for implementations of various collection types, as described in "Finger trees: a simple general-purpose data structure", by Ralf Hinze and Ross Paterson. A gentle introduction is presented in the blog post "Monoids and Finger Trees" by Heinrich Apfelmus.

This is done by choosing a suitable type to annotate the nodes. For example, a binary tree can be implemented by annotating each node with the size of its subtree, while a priority queue can be implemented by labelling the nodes by the minimum priority of its children.

The operations on FingerTree enforce the constraint measured (in the form of a Reducer instance).

Finger Trees have excellent (amortized) asymptotic performance:

• Access to the first and last elements is O(1)
• Appending/prepending a single value is O(1)
• Concatenating two trees is (O lg min(l1, l2)) where l1 and l2 are their sizes
• Random access to an element at n is O(lg min(n, l - n)), where l is the size of the tree.
• Constructing a tree with n copies of a value is O(lg n).

A type parameter implying the ability to extract zero or more values of that type.

A scalaz.Foldable where foldMap is total over semigroups. That is, toList cannot return an empty list.

A universally quantified value

A free monad for a type constructor S. Binding is done using the heap instead of the stack, allowing tail-call elimination.

Free applicative functors. Less expressive than free monads, but more flexible to inspect and interpret.

Functors, covariant by nature if not by Scala type. Their key operation is map, whose behavior is constrained only by type and the functor laws.

Many useful functors also have natural scalaz.Apply or scalaz.Bind operations. Many also support scalaz.Traverse.

Generator a class of container of elements that knows how to efficiently apply a scalaz.Reducer to extract an answer by combining elements. A Reducer may supply efficient left-to-right and right-to-left reduction strategies that a Generator may avail itself of.

An efficient, asymptotically optimal, implementation of priority queues extended with support for efficient size.

The implementation of 'Heap' is based on bootstrapped skew binomial heaps as described by: G. Brodal and C. Okasaki , "Optimal Purely Functional Priority Queues", Journal of Functional Programming 6:839-857 (1996),

Based on the heaps Haskell library by Edward Kmett

Safe, invariant alternative to stdlib List. Most methods on List have a sensible equivalent here, either on the IList interface itself or via typeclass instances (which are the same as those defined for stdlib List). All methods are total and stack-safe.

A linked list with by-name head and tail, allowing some control over memory usage and evaluation of contents.

This structure is a good choice when the contents are expensive to calculate and may not all need to be evaluated, at the cost of an overhead when the contents are calculated. Typeclass instances try to defer evaluation of contents, unless it would require a full traversal of the spine, preferring lazy semantics when an evaluation choice is to be made.

Mixed into object Id in the package object scalaz.

An immutable wrapper for arrays

Indexed sequences, based on scalaz.FingerTree

The measure is the count of the preceding elements, provided by UnitReducer((e: Int) => 1).

A monad transformer stack yielding (R, S1) => F[(W, A, S2)].

Inject type class as described in "Data types a la carte" (Swierstra 2008).

Given Injective[Foo]: If type Foo[A] = Foo[B] then A ~ B

This represents an assertion that is used by other code that requires this condition.

Invariant parent of Decidable and Alternative.

Used for typeclass derivation of products, coproducts and value types.