The Functor Combinatorpedia

by Justin Le ♦ Wednesday June 19, 2019

Source ♦ Markdown ♦ LaTeX ♦ Posted in Haskell ♦ Comments

functor-combinators: hackage / github

(Note: This post has been heavily revised to reflect the functor-combinators-0.2 refactoring, as of November 2019. For reference, the original post is available on github.)

(Note 2: The section on contravariant functor combinators was added following the release of functor-combinators-0.3 in August 2020, which added support for contravariant and invariant functor combinators.)

Recently I’ve been very productive what I have been calling the “Functor Combinator” design pattern. It is heavily influenced by ideas like Data types a la Carte and unified free monoidal functors, but the end goal is slightly different in spirit. The goal is to represent schemas, DSL’s, and computations (things like parsers, things to execute, things to consume or produce data) by assembling “self-evident” basic primitives and subjecting them to many different successive transformations and combiners (through combinators, free structures, tensors, and other options). The process of doing so:

Forces you to make explicit decisions about the structure of your computation type as an ADT.
Allows you to retain isolation of fundamental parts of your domain as separate types
Lets you manipulate the structure of your final computation type through normal Haskell techniques like pattern matching. The structure is available throughout the entire process, so you can replace individual components and values within your structure.
Allows you to fully reflect the structure of your final computation through pattern matching and folds, so you can inspect the structure and produce useful summaries.

Like “data types a la carte” and free monad/applicative/alternative designs, these techniques allow you to separate the assembly and inspection of your programs from the “running” of them.¹ However, the main difference is that here we focus not just on products and sums, but many different varied and multi-purpose combinators — a “zoo” of combinators. The fixed point is not the end goal. The actual ADT data types themselves are the goal.

This post is a run-down on the wide variety of such “functor combinators” across the Haskell ecosystem — a functor combinatorpedia. To speak about them all with the same language and vocabulary, this post also serves as an overview of the functor-combinators library, which doesn’t really define these functor combinators, but rather pulls them all together and provides a unified interface for working with them. Most of these types and typeclasses are exported by Data.Functor.Combinator. Of course, the end-goal is to work with these data types themselves directly, so not everything is meant to be doable with these typeclasses; they only serve to unite some common aspects.

Right now I already have some posts about this general design pattern, “Interpreters a la Carte” in Advent of Code 2017 Duet and Applicative Regular Expressions using the Free Alternative, but I do have some posts planned in the future going through projects using this unified interface. In a way, this post also serves as the “introduction to free structures” that I always wanted to write :)

Please refer to the table of contents if you are using this as a reference!

Preface: What is a functor combinator?

A functor combinator takes “functors” (or any other indexed type, k -> Type) and returns a new functor, enhances or mixes them together in some way. That is, they take things of kind k -> Type and themselves return a j -> Type. This lets us build complex functors/indexed types out of simpler “primitive” ones. This includes many some monad transformers, free structures, and tensors.

For example, ReaderT r is a famous one that takes a functor f and enhances it with “access to an r environment” functionality. Another famous one is Free, which takes a functor f and enhances it with “sequential binding” capabilities: it turns f into a Monad.

The main thing that distinguishes these functor combinators from things like monad transformers is that they are “natural on f”: they work on all fs, not just monads, and assume no structure (not even Functor).

Sometimes, we have binary functor combinators, like :+:, which takes two functors f and g and returns a functor that is “either” f or g. Binary functor combinators “mix together” the functionality of different functors in different ways.

Examples

If your final DSL/program/schema is some functor, then functor combinators allow you to construct your final functor by combining simpler “primitive” functors, and take advantage of common functionality.

For example, if you were making a data type/EDSL to describe a command line argument parser, you might have two primitives: data Arg a, for positional arguments parsing a, and data Option a, for --flag non-positional options parsing a. From there, you can choose what structure of command line arguments you want to be able to express.

For instance, a structure that can support multiple arguments and optionally a single Option would be:

type CommandArgs = Ap Arg :*: Lift Option

And a structure that supports multiple named commands on top of that would be:

type CommandArgs = MapF String (Ap Arg :*: Lift Option)

You can mix or match combinators to decide exactly what sort of structures you allow in your DSL.

Now, instead of writing one “giant” runParser :: MapF String (Ap Arg :*: Lift Option) a -> IO a function, you can instead just write parsers for your simple primitives Arg a -> IO a and Option a -> IO a, and then use functor combinator tools to “promote” them to being runnable on a full MapF String (Ap Arg :*: Lift Option) without any extra work.

Common Functionality

Most of these functor combinators allow us to “swap out” the underlying functor, retaining all of the “enhanced” structure. We abstract over all of these using hmap for single-argument functor combinators (“enhancers”) and hbimap for two-argument functor combinators (“mixers”).

class HFunctor t where
    -- | Swap out underlying functor for a single-argument functor combinator
    hmap
        :: (forall x. f x -> g x)
        -> t f a
        -> t g a

class HBifunctor t where
    -- | Swap out underlying functors for a two-argument functor combinator
    hbimap
        :: (forall x. f x -> h x)
        -> (forall x. g x -> j x)
        -> t f g a
        -> t h j a

However, for this post, the concept of a “natural transformation” between f and g — a function of type forall x. f x -> g x, is given a type synonym:

type f ~> g = forall x. f x -> g x

Then the type signatures of hmap and hbimap become:

class HFunctor t where
    hmap
        :: f ~> g
        -> t f ~> t g

class HBifunctor t where
    hbimap
        :: f ~> h
        -> g ~> j
        -> t f g ~> t h j

What does it mean exactly when we say that hmap and hbimap “preserve the enhanced structure”? Well, for example, the type newtype ListF f a = ListF [f a] is essentially a list of f as. hmap will swap out and replace each f a, but it must preserve the relative order between each of the original f as. It must also preserve the length of the list. It’s a complete “in-place swap”. This is formalizing by requiring hmap id == id and hbimap id id == id.

You can also always “lift” a functor value into its transformed type. We abstract over this by using inject (for single-argument functors) and inL and inR (for two-argument functors):

-- single argument functor combinators
inject :: f ~> t f

-- two-argument functor combinators
inL :: MonoidIn t i f
    => f ~> t f g

inR :: MonoidIn t i g
    => g ~> t f g

Finally, in order to use any functor combinators, you have to interpret them into some target context. The choice of combinator imposes some constraints on the target context. We abstract over this using interpret and binterpret:

class Interpret t f where
    -- | Interpret unary functor combinator
    interpret
        :: g ~> f             -- ^ interpreting function
        -> t g ~> f

class SemigroupIn t i f where
    -- | Interpret binary functor combinator
    binterpret
        :: g ~> f             -- ^ interpreting function on g
        -> h ~> f             -- ^ interpreting function on h
        -> t g h ~> f

Having the typeclass Interpret (and SemigroupIn) take both t and f means that there are certain limits on what sort of f you can interpret into.

One nice consequence of this approach is that for many such schemas/functors you build, there might be many useful target functors. For example, if you build a command line argument parser schema, you might want to run it in Const String to build up a “help message”, or you might want to run it in Parser to parse the actual arguments or run pure tests, or you might want to run it in IO to do interactive parsing.

For some concrete examples of these functor combinators and their constraints:

instance Monad f => Interpret Free f

interpret @Free
    :: Monad g
    => (g ~> f)
    -> Free g a
    -> f a

instance SemigroupIn (:+:) V1 f

binterpret @(:+:)
    :: (g ~> f)
    -> (h ~> f)
    -> (g :+: h) a
    -> f a

We see that interpret lets you “run” a Free in any monad f, and binterpret lets you “run” a function over both branches of an g :+: h to produce an f.

From these, we can also build a lot of useful utility functions (like retract, biretract, getI, biget, etc.) for convenience in actually working on them. These are provided in functor-combinators.

Without further ado, let’s dive into the zoo of functor combinators!

Two-Argument

Binary functor combinators “mix together” two functors/indexed types in different ways.

We can finally interpret (or “run”) these into some target context (like Parser, or IO), provided the target satisfies some constraints.

For the most part, binary functor combinators t are instances of both Associative t and Tensor t i. Every t is associated with i, which is the “identity” functor that leaves f unchanged: t f i is the same as f, and t i f is the same as f as well.

For example, we have Comp, which is functor composition:

newtype Comp f g a = Comp (f (g a))

We have an instance Associative Comp and Tensor Comp Identity, because Comp f Identity (composing any functor with Identity, f (Identity a)) is just the same as f a (the original functor); also, Comp Identity f (or Identity (f a)) is the same as f a.

From there, some functors support being “merged” (interpreted, or collapsed) from a binary functor combinator, or being able to be injected “into” a binary functor combinator. Those functors f have instances SemigroupIn t f and MonoidIn t i f. If a functor f is SemigroupIn t f, we can interpret out of it:

binterpret
    :: SemigroupIn t f
    => (g ~> f)
    -> (h ~> f)
    -> (t g h ~> f)

biretract
    :: SemigroupIn t f
    => t f f ~> f

And if a functor f is MonoidIn t i f, we can “inject” into it:

pureT
    :: MonoidIn t i f
    => i ~> f

inL :: MonoidIn t i g
    => f ~> t f g

inR :: MonoidIn t i f
    => g ~> t f g

A more detailed run-down is available in the docs for Data.Functor.Combinator.

One interesting property of these is that for tensors, if we have a binary functor combinator *, we can represent a type f | f * f | f * f * f | f * f * f * f | ... (“repeatedly apply to something multiple times”), which essentially forms a linked list along that functor combinator. This is like a linked list with t as the “cons” operation, so we call this ListBy t. We can also make a “non-empty variant”, NonEmptyBy t, which contains “at least one f”.

For example, the type that is either a, f a, f (f a), f (f (f a)), etc. is Free f a, so that type ListBy Comp = Free. The type that is either f a, f (f a), f (f (f a)), etc. (at least one layer of f) is Free1 f a, so type NonEmptyBy Comp = Free1.

functor-combinators provides functions like toListBy :: t f f ~> ListBy t f to abstract over “converting” back and forth between t f f a and linked list version ListBy t f a (for example, between Comp f f a and Free f a).

:+: / Sum

Origin: GHC.Generics (for :+:) / Data.Functor.Sum (for Sum)
Mixing Strategy: “Either-or”: provide either case, and user has to handle both possibilities. Basically higher-order Either.
```
data (f :+: g) a
    = L1 (f a)
    | R1 (g a)

data Sum f g a
    = InL (f a)
    | InR (g a)
```
It can be useful for situations where you can validly use one or the other in your schema or functor. For example, if you are describing an HTTP request, we could have data GET a describing a GET request and data POST a describing a POST request; (GET :+: POST) a would be a functor that describes either a GET or POST request.

The person who creates the f :+: g decides which one to give, and the person who consumes/interprets/runs the f :+: g must provide a way of handling both
```
binterpret @(:+:)
    :: (g ~> f)
    -> (h ~> f)
    -> (g :+: h) a
    -> f a
```
binterpret becomes analogous to either from Data.Either
Identity
```
instance Tensor (:+:) V1

-- | Data type with no inhabitants
data V1 a
```
f :+: V1 is equivalent to just f, because you can never have a value of the right branch.

Monoids

instance SemigroupIn (:+:) f
instance MonoidIn    (:+:) V1 f

binterpret @(:+:)
    :: (g ~> f)
    -> (h ~> f)
    -> (g :+: h) a
    -> f a

inL   @(:+:) :: f     ~> f :+: g
inR   @(:+:) :: g     ~> f :+: g
pureT @(:+:) :: V1 ~> h

All haskell functors are monoids in :+:. You can call binterpret, inL, inR, etc. with anything.

However, note that pureT is effectively impossible to call, because no values of type V1 a exist.

List type

type NonEmptyBy (:+:) = Step
type ListBy     (:+:) = Step

Step is the result of an infinite application of :+: to the same value:

type Step f = f :+: f :+: f :+: f :+: f :+: f :+: ... etc.

-- actual implementation
data Step f a = Step
  { stepPos :: Natural
  , stepVal :: f a
  }

The correspondence is:

L1 x           <=> Step 0 x
R1 (L1 y)      <=> Step 1 y
R1 (R1 (L1 z)) <=> Step 2 z
-- etc.

It’s not a particularly useful type, but it can be useful if you want to provide an f a alongside “which position” it is on the infinite list.

:*: / Product

Origin: GHC.Generics (for :*:) / Data.Functor.Product (for Product)
Mixing Strategy: “Both, separately”: provide values from both functors, and the user can choose which one they want to use. Basically a higher-order tuple.
```
data (f :*: g) a = f a :*: g a

data Product f g a = Pair (f a) (g a)
```
It can be useful for situations where your schema/functor must be specified using both functors, but the interpreter can choose to use only one or the other (or both).
```
prodOutL :: (f :*: g) ~> f
prodOutL (x :*: _) = x

prodOutR :: (f :*: g) ~> g
prodOutR (_ :*: y) = y
```

Identity

instance Tensor (:*:) Proxy

-- | Data type with only a single constructor and no information
data Proxy a = Proxy

f :*: Proxy is equivalent to just f, because the left hand side doesn’t add anything extra to the pair.

Monoids

instance Alt  f => SemigroupIn (:*:) f
instance Plus f => MonoidIn    (:*:) Proxy f

binterpret @(:*:)
    :: Alt f
    => g ~> f
    -> h ~> f
    -> (g :*: h) ~> f

inL   @(:*:) :: Plus g => f     ~> f :*: g
inR   @(:*:) :: Plus f => g     ~> f :*: g
pureT @(:*:) :: Plus h => Proxy ~> h

Alt, from Data.Functor.Alt in semigroupoids, can be thought of a “higher-kinded semigroup”: it’s like Alternative, but with no Applicative constraint and no identity:

class Alt f where
    (<!>) :: f a -> f a -> f a

It is used to combine the results in both branches of the :*:.

To introduce an “empty” branch, we need Plus (in Data.Functor.Plus), which is like a higher-kinded Monoid, or Alternative with no Applicative:

class Alt f => Plus f where
    zero :: f a

List type
```
type NonEmptyBy (:*:) = NonEmptyF
type ListBy     (:*:) = ListF
```
ListF f a is a “list of f as”. It represents the possibility of having Proxy (zero items), x :: f a (one item), x :*: y (two items), x :*: y :*: z (three items), etc.

It’s basically an ordered collection of f as :*:d with each other.
```
Proxy         <=> ListF []
x             <=> ListF [x]
x :*: y       <=> ListF [x,y]
x :*: y :*: z <=> ListF [x,y,z]
-- etc.
```
It is useful if you want to define a schema where you can offer multiple options for the f a, and the interpreter/consumer can freely pick any one that they want to use.

NonEmptyF is the version of ListF that has “at least one f a”.

See the information later on ListF alone (in the single-argument functor combinator section) for more information on usage and utility.

Day

Origin: Data.Functor.Day
Mixing Strategy: “Both, together forever”: provide values from both functors, and the user must also use both.

It can be useful for situations where your schema/functor must be specified using both functors, and the user must also use both.
```
binterpret @Day
    :: Apply f          -- superclass of Applicative
    => (g ~> f)
    -> (h ~> f)
    -> Day g h ~> f
```
Unlike for :*:, you always have to interpret both functor values in order to interpret a Day. It’s a “full mixing”.

The mechanism for this is interesting in and of itself. Looking at the definition of the data type:
```
data Day f g a = forall x y. Day (f x) (g y) (x -> y -> a)
```
We see that because x and y are “hidden” from the external world, we can’t directly use them without applying the “joining” function x -> y -> a. Due to how existential types work, we can’t get anything out of it that “contains” x or y. Because of this, using the joining function requires both f x and g y. If we only use f x, we can only get, at best,f (y -> a); if we only use g y, we can only get, at best, g (x -> a). In order to fully eliminate both existential variables, we need to get the x and y from both f x and g y, as if the two values held separate halves of the key.
Identity
```
instance Tensor Day Identity
```
Day f Identity is equivalent to just f, because Identity adds no extra effects or structure.

Monoids

instance Apply       f => SemigroupIn Day f
instance Applicative f => MonoidIn    Day Identity f

binterpret @Day
    :: Apply f
    => (g ~> f)
    -> (h ~> f)
    -> Day g h ~> f

inL   @Day :: Applicative g => f        ~> Day f g
inR   @Day :: Applicative f => g        ~> Day f g
pureT @Day :: Applicative h => Identity ~> h

Apply, from Data.Functor.Apply in semigroupoids, is “Applicative without pure”; it only has <*> (called <.>).

pureT is essentially pure :: Applicative h => a -> h a.

List type
```
type NonEmptyBy Day = Ap1
type ListBy     Day = Ap
```
Ap f a is a bunch of f xs Dayd with each other. It is either:
- a (zero fs)
- f a (one f)
- Day f f a (two fs)
- Day f (Day f f) a (three fs)
- .. etc.
Like ListF this is very useful if you want your schema to provide a “bag” of f as and your interpreter must use all of them.

For example, if we have a schema for a command line argument parser, each f may represent a command line option. To interpret it, we must look at all command line options.

Ap1 is a version with “at least one” f a.

See the information later on Ap alone (in the single-argument functor combinator section) for more information on usage and utility.

Comp

Origin: Control.Monad.Freer.Church. Note that an equivalent type is also found in GHC.Generics and Data.Functor.Compose, but they are incompatible with the HBifunctor typeclass because they require the second input to have a Functor instance.
Mixing Strategy: “Both, together, sequentially” : provide values from both functors; the user must use both, and in order.
```
newtype Comp f g a = Comp (f (g a))
```
It can be useful for situations where your schema/functor must be specified using both functors, and the user must use both, but also enforcing that they must use both in the given order: that is, for a Comp f g, they interpret f before they interpret g.
```
binterpret @Comp
    :: Bind f          -- superclass of Monad
    => (g ~> f)
    -> (h ~> f)
    -> Comp g h ~> f
```
Unlike for :*:, you always have to interpret both functor values. And, unlike for Day, you must interpret both functor values in that order.
Identity
```
instance Tensor Comp Identity
```
Comp f Identity is equivalent to just f, because Identity adds no extra effects or structure.
Monoids
```
instance Bind  f => SemigroupIn Comp f
instance Monad f => MonoidIn    Comp Identity f

binterpret @Comp
    :: Bind f
    => (g ~> f)
    -> (h ~> f)
    -> Comp g h ~> f

inL   @Comp :: Monad g => f        ~> Comp f g
inR   @Comp :: Monad f => g        ~> Comp f g
pureT @Comp :: Monad h => Identity ~> h
```
Bind, from [Data.Functor.Bind][] in semigroupoids, is “Monad without return”; it only has >>= (called >>-).

Somewhat serendipitously, the constraint associated with monoids in Comp is none other than the infamous Monad.

This might sound familiar to your ears — it’s the realization of the joke that “monads are monoids in the category of (endo)functors”. The idea is that we can make a tensor like Comp over functors, and that “monoids in” that tensor correspond exactly to Monad instances. A part of the joke that we can now also see is that monads aren’t the only monoids in the category of endofunctors: they’re just the ones that you get when you tensor over Comp. But we see now that if you use Day as your tensor, then “monoids in the category of functors over Day” are actually Applicative instances! And that the monoids over :*: are Alt instances, etc.

Theory aside, hopefully this insight also gives you some insight on the nature of Monad as an abstraction: it’s a way to “interpret” in and out of Comp, which enforces an ordering in interpretation :)
List type
```
type NonEmptyBy Day = Free1
type LIstBy     Day = Free
```
Free f a is a bunch of f xs composed with each other. It is either:
- a (zero fs)
- f a (one f)
- f (f a) (two fs)
- f (f (f a)) (three fs)
- .. etc.
Free is very useful because it allows you to specify that your schema can have many fs, sequenced one after the other, in which the choice of “the next f” is allowed to depend on the result of “the previous f”.

For example, in an interactive “wizard” sort of schema, we can have a functor representing a dialog box with its result type:
```
data Dialog a
```
We can then represent our wizard using Free Dialog a — an ordered sequence of dialog boxes, where the choice of the next box can depend on result of the previous box.

Free1 is a version with “at least one” f a.

See the information later on Free alone (in the single-argument functor combinator section) for more information on usage and utility.

Aside

Let us pause for a brief aside to compare and contrast the hierarchy of the above functor combinators, as there is an interesting progression we can draw from them.

:+:: Provide either, be ready for both.
:*:: Provide both, be ready for either.
Day: Provide both, be ready for both.
Comp: Provide both, be ready for both (in order).

These1

Origin: Data.Functor.These.
Mixing Strategy: “Either-or, or both”: provide either (or both) cases, and user has to handle both possibilities. An “inclusive either”
```
data These1 f g a
    = This1  (f a)
    | That1        (g a)
    | These1 (f a) (g a)
```
This can be useful for situations where your schema/functor can be specified using one functor or another, or even both. See description on :+: for examples.

The person who creates the These1 f g decides which one to give, and the person who consumes/interprets/runs the f :+: g must provide a way of handling both situations.
```
binterpret @These
    :: Alt f
    => (g ~> f)
    -> (h ~> f)
    -> These g h a
    -> f a
```
You can also pattern match on the These1 directly to be more explicit with how you handle each of the tree cases.
Identity
```
instance Tensor These V1
```
These1 f V1 is equivalent to just f, because it means the That1 and These1 branches will be impossible to construct, and you are left with only the This1 branch.

Monoids

instance Alt f => SemigroupIn These1 f
instance Alt f => MonoidIn    These1 V1 f

binterpret @These
    :: Alt f
    => (g ~> f)
    -> (h ~> f)
    -> These g h ~> f

inL   @These1 :: Alt g => f  ~> Comp f g
inR   @These1 :: Alt f => g  ~> Comp f g
pureT @These1 :: Alt h => V1 ~> h

You need at least Alt to be able to interpret out of a These1, because you need to be able to handle the case where you have both f and g, and need to combine the result. However, you never need a full Plus because we always have at least one value to use.

List type
```
type ListBy These1 = Steps
```
Steps, the list type, is the result of an infinite application of These1 to the same value:
```
type Steps f = f `These1` f `These1` f `These1` f `These1` ... etc.

-- actual implementation
newtype Steps f a = Steps (NEMap Natural (f a))
                -- NEMap is a non-empty Map
```
It essentially represents an infinite sparse array of f as, where an f a might exist at many different positions, with gaps here and there. There is always at least one f a.

Like Step, it’s not particularly useful, but it can be used in situations where you want a giant infinite sparse array of f as, each at a given position, with many gaps between them.

I’ve skipped over the the “non-empty” version, which is ComposeT Flagged Steps; it requires an extra boolean “flag” because of some of the quirks of nonemptiness. I feel it is even less useful than Steps.

LeftF / RightF

Origin: Data.HBifunctor
Mixing Strategy: “Ignore the left” / “ignore the right”.
```
data LeftF  f g a = LeftF  { runLeftF  :: f a }

data RightF f g a = RightF { runRightF :: g a }
```
You can think of LeftF as “:+: without the Right case, R1”, or RightF as “:+: without the Left case, L1”. RightF can be considered a higher-order version of Tagged, which “tags” a value with some type-level information.

This can be useful if you want the second (or first) argument to be ignored, and only be used maybe at the type level.

For example, RightF IgnoreMe MyFunctor is equivalent to just MyFunctor, but you might want to use IgnoreMe as a phantom type to help limit what values can be used for what functions.
Identity

Unlike the previous functor combinators, these three are only Associative, not Tensor: this is because there is no functor i such that LeftF i g is equal to g, for all g, and no functor i such that RightF f i is equal to f, for all f.
Constraints
```
instance SemigroupIn LeftF  f
instance SemigroupIn RightF f
```
Interpreting out of either of these is unconstrained, and can be done in any context.
List type
```
type NonEmptyBy LeftF = Flagged
```
For LeftF, the non-empty list type is Flagged, which is the f a tupled with a Bool. See the information on Flagged for more details. This can be useful as a type that marks if an f is made with inject/pure and is “pure” (False), or “tainted” (True). The provider of a Flagged can specify “pure or tainted”, and the interpreter can make a decision based on that tag.
```
type NonEmptyBy RightF = Step
```
For RightF, the non-empty list type is Step. See Step and the information on :+: for more details. This can be useful for having a value of f a at “some point”, indexed by a Natural.

Single-Argument

Unary functor combinators usually directly “enhance” a functor with extra capabilities — usually in the form of a typeclass instance, or extra data fields/constructors.

All of these can be “lifted into” with any constraint on f.

class HFunctor t => Inject t where
    inject :: f ~> t f

Inject seems very similar to MonadTrans’s lift; the difference is that inject must be natural on f: it can assume nothing about the structure of f, and must work universally the same. MonadTrans, in contrast, requires Monad f.

Each one can also be “interpreted to” certain functors f:

class Inject t => Interpret t f where
    interpret
        :: g ~> f
        -> t g ~> f

An important law is that:

interpret id . inject == id

This means that if we inject and immediately interpret out of, we should never lose any information in f. All of the original structure in f must stay intact: functor combinators only ever add structure.

Coyoneda

Origin: Data.Functor.Coyoneda
Enhancement: The ability to map over the parameter; it’s the free Functor.

Can be useful if f is created using a GADT that cannot be given a Functor instance.

For example, here is an indexed type that represents the type of a “form element”, where the type parameter represents the output result of the form element.
```
data FormElem :: Type -> Type where
    FInput    :: FormElem String
    FTextbox  :: FormElem Text
    FCheckbox :: FormElem Bool
    FNumber   :: FormElem Int
```
Then Coyoneda FormElem has a Functor instance. We can now fmap over the result type of the form element; for example, fmap :: (a -> b) -> Coyoneda FormElem a -> Coyoneda FormElem b takes a form element whose result is an a and returns a form element whose result is a b.
Interpret
```
instance Functor f => Interpret Coyoneda f

interpret @Coyoneda
    :: Functor f
    => g ~> f
    -> Coyoneda g ~> f
```
Interpreting out of a Coyoneda f requires the target context to itself be Functor. Usually, the context is an Applicative or Monad, so this is typically always satisfied.

For example, if we want to “run” a Coyoneda FormElem in IO (maybe as an interactive CLI form), this would be interpret :: (forall x. FormElem x -> IO x) -> Coyoneda FormElem a -> IO a.

ListF / NonEmptyF

Origin: Control.Applicative.ListF
Enhancement: The ability to offer multiple options for the interpreter to pick from; ListF is the free Plus, and NonEmptyF is the free Alt.
```
data ListF     f a = ListF     { runListF     :: [f a]          }
data NonEmptyF f a = NonEmptyF { runNonEmptyF :: NonEmpty (f a) }
```
Can be useful if you want to provide the ability when you define your schema to provide multiple f as that the interpreter/consumer can freely pick from.

For example, for a schema specifying a form, you might have multiple ways to enter a name. If you had a Name schema data Name a, then you can represent “many different potential name inputs” schema as ListF Name a.

Because this has a Plus instance, you can use (<!>) :: ListF f a -> ListF f a -> ListF f a to combine multiple option sets, and zero :: ListF f a to provide the “choice that always fails/is unusuable”.

NonEmptyF is a variety of ListF where you always have “at least one f a”. Can be useful if you want to ensure, for your interpreter’s sake, that you always have at least one f a option to pick from. For example, NonEmptyF Name a will always have at least one name schema.

This is essentially f :*:d with itself multiple times; ListF is the linked list list made by :*:, and NonEmptyF is the non-empty linked list made by :*:.
```
x             <=> ListF [x]     <=> NonEmptyF (x :| [])
x :*: y       <=> ListF [x,y]   <=> NonEmptyF (x :| [y])
x :*: y :*: z <=> ListF [x,y,z] <=> NonEmptyF (x :| [y,z])
```
Interpret
```
instance Plus f => Interpret ListF     f
instance Alt  f => Interpret NonEmptyF f

interpret @ListF
    :: Plus f
    => g ~> f
    -> ListF g ~> f

interpret @NonEmptyF
    :: Alt f
    => g ~> f
    -> NonEmptyF g ~> f
```
Interpreting out of a ListF f requires the target context to be Plus, and interpreting out of a NonEmptyF f requires Alt (because you will never have the empty case). However, you always have the option to directly pattern match on the list and pick an item you want directly, which requires no constraint.

Ap / Ap1

Origin: Control.Applicative.Free / Data.Functor.Apply.Free
Enhancement: The ability to provide multiple fs that the interpreter must consume all of; Ap is the free Applicative, and Ap1 is the free Apply.

While ListF may be considered “multiple options offered”, Ap can be considered “multiple actions all required”. The interpreter must consume/interpret all of the multiple fs in order to interpret an Ap.

For example, for a form schema, you might want to have multiple form elements. If a single form element is data FormElem a, then you can make a multi-form schema with Ap FormElem a. The consumer of the form schema must handle every FormElem provided.

Note that ordering is not enforced: while the consumer must handle each f eventually, they are free to handle it in whatever order they desire. In fact, they could even all be handled in parallel. See Free for a version where ordering is enforced.

Because this has an Applicative instance, you can use (<*>) :: Ap f (a -> b) -> Ap f a -> Ap f b to sequence multiple Ap fs together, and pure :: a -> Ap f a to produce a “no-op” Ap without any fs.

Ap has some utility over Free in that you can pattern match on the constructors directly and look at each individual sequenced f a, for static analysis, before anything is ever run or interpreted.

Structurally, Ap is built like a linked list of f xs, which each link being existentially bound together:
```
data Ap :: (Type -> Type) -> Type -> Type where
    Pure :: a   -> Ap f a
    Ap   :: f a -> Ap f (a -> b) -> Ap f b
```
Pure is like “nil”, and Ap is like “cons”:
```
data List :: Type -> Type where
    Nil  :: List a
    Cons :: a -> List a -> List a
```
The existential type in the Ap branch plays the same role that it does in the definition of Day (see the description of Day for more information).

Ap1 is a variety of Ap where you always have to have “at least one f”. Can be useful if you want to ensure, for example, that your form has at least one element.

Note that this is essentially f Dayd with itself multiple times; Ap is the linked list made by Day and Ap1 is the non-empty linked list made by Day.

Interpret

instance Applicative f => Interpret Ap  f
instance Apply       f => Interpret Ap1 f

interpret @Ap
    :: Applicative f
    => g ~> f
    -> Ap g ~> f

interpret @Ap1
    :: Apply f
    => g ~> f
    -> Ap1 g ~> f

Interpreting out of an Ap f requires the target context to be Applicative, and interpreting out of a Ap1 f requires Apply (because you will never need the pure case).

Alt

Origin: Control.Alternative.Free
Enhancement: A combination of both ListF and Ap: provide a choice (ListF-style) of sequences (Ap-style) of choices of sequences of choices ….; it’s the free Alternative.
```
Alt f ~ ListF (Ap (ListF (Ap (ListF (Ap (...))))
      ~ ListF (Ap (Alt f))
```
This type imbues f with both sequential “must use both” operations (via <*>) and choice-like “can use either” operations (via <|>).

It can be useful for implementing parser schemas, which often involve both sequential and choice-like combinations. If f is a primitive parsing unit, then Alt f represents a non-deterministic parser of a bunch of fs one after the other, with multiple possible results. I wrote an entire article on the usage of this combinator alone to implement a version of regular expressions.

Interpret

instance Alternative f => Interpret Alt f

interpret @Alt
    :: Alternative f
    => g ~> f
    -> Alt g ~> f

Interpreting out of an Alt f requires the target context to be Alternative — it uses <*> for sequencing, and <|> for choice.

Free / Free1

Origin: Control.Monad.Freer.Church, which is a variant of Control.Monad.Free that is compatible with HFunctor.
Enhancement: The ability to provide multiple fs that the interpreter must consume in order, sequentially — the free Monad.

Contrast with Ap, which also sequences multiple fs together, but without any enforced order. It does this by hiding the “next f a” until the previous f a has already been interpreted.

Perhaps more importantly, you can sequence fs in a way where the choice of the next f is allowed to depend on the result of the previous f.

For example, in an interactive “wizard” sort of schema, we can create a functor to represent a dialog box with its result type:
```
data Dialog a
```
We can then construct a type for a wizard:
```
type Wizard = Free Dialog
```
Wizard is now an ordered sequence of dialog boxes, where the choice of the next box can depend on result of the previous box. Contrast to Ap Dialog, where the choice of all dialog boxes must be made in advanced, up-front, before reading any input from the user.

In having this, however, we loose the ability to be able to inspect each f a before interpreting anything.

Because this has a Monad instance, you can use (<*>) :: Free f (a -> b) -> Free f a -> Free f b and (>>=) :: Free f a -> (a -> Free f b) -> Free f b) to sequence multiple Free fs together, and pure :: a -> Free f a to produce a “no-op” Free without any fs.

Free1 is a variety of Free1 where you always have to have “at least one f”. Can be useful if you want to ensure, for example, that your wizard has at least one dialog box.
```
type NonEmptyWizard = Free1 Dialog
```
Note that this is essentially f Compd with itself multiple times; Free is the linked list made by Comp and Free1 is the non-empty linked list made by Comp.

Interpret

instance Monad f => Interpret Free  f
instance Bind  f => Interpret Free1 f

interpret @Free
    :: Monad f
    => g ~> f
    -> Free g ~> f

interpret @Free1
    :: Bind f
    => g ~> f
    -> Free1 g ~> f

Interpreting out of a Free f requires the target context to be Monad, and interpreting out of a Free1 f requires Bind (because you will never need the pure case).

Lift / MaybeApply

Origin: Control.Applicative.Lift / Data.Functor.Apply (the same type)
Enhancement: Make f “optional” in the schema in a way that the interpreter can still work with as if the f was still there; it’s the free Pointed.
```
data Lift f a = Pure  a
              | Other (f a)

newtype MaybeApply f a = MaybeApply { runMaybeApply :: Either a (f a) }
    -- ^ same type, from semigroupoids
```
Can be useful so that an f a is optional for the schema definition, but in a way where the consumer can still continue from it as if they had the f.

It can be used, for example, to turn an required parameter Param a into an optional parameter Lift Param a.

Contrast this to MaybeF: this allows the interpreter to still “continue on” as normal even if the f is not there. However, MaybeF forces the interpreter to abort if the f is not there.

This can be thought of as Identity :+: f.
Interpret
```
instance Pointed f => Interpret Lift f

interpret @Lift
    :: Pointed f
    => g ~> f
    -> Lift g ~> f
```
Interpreting out of a Lift f requires the target context to be Pointed, from Data.Pointed — it uses point :: Pointed f => a -> f a to handle the case where the f is not there.

MaybeF

Origin: Control.Applicative.ListF
Enhancement: Make f “optional” in the schema in a way that the interpreter must fail if the f is not present.
```
newtype MaybeF f a = MaybeF { runMaybeF :: Maybe (f a) }
```
Can be useful so that an f a is optional for the schema definition; if the f is not present, the consumer must abort the current branch, or find some other external way to continue onwards.

Contrast this to Lift, which is an “optional” f that the consumer may continue on from.
Interpret
```
instance Plus f => Interpret MaybeF f

interpret @MaybeF
    :: Plus f
    => g ~> f
    -> MaybeF g ~> f
```
Interpreting out of a Lift f requires the target context to be Plus — it uses zero :: f a to handle the case where the f is not there. Note that this is actually “over-constrained”: we really only need zero, and not all of Plus (which includes <!>). However, there is no common typeclass in Haskell that provides this, so this is the most pragmatic choice.

EnvT

Origin: Control.Comonad.Trans.Env
Enhancement: Provide extra (monoidal) data alongside f a that the interpreter can access. Basically tuples extra e alongside the f a.
```
newtype EnvT e f a = EnvT e (f a)
```
You can use this to basically tuple some extra data alongside an f a. It can be useful if you want to provide extra information that isn’t inside the f for the interpreter use for interpretation.

When using inject :: Monoid e => f a -> EnvT e f a, it uses mempty as the initial e value.

One of my personal favorite uses of EnvT is the flare purescript library, which uses the e as the observed HTML of a form, and the f a as an active way to get information from a form interactively. inject is used to insert an active form element without caring about its HTML representation, and interpret would “run” the active elements to get the results.

This type exists specialized a few times here, as well:
- Step is EnvT (Sum Natural)
- Flagged is EnvT Any

Interpret

instance Interpret (EnvT e) f

interpret @(EnvT e)
    :: g ~> f
    -> EnvT e g ~> f

Interpreting out of EnvT e requires no constraints.

MapF / NEMapF

Origin: Control.Applicative.ListF
Enhancement: Contain multiple f as, each indexed at a specific key.
```
newtype MapF   k f a = MapF   { runMapF :: Map   k (f a) }
newtype NEMapF k f a = NEMapF { runMapF :: NEMap k (f a) }
```
This is very similar in functionality to ListF and NonEmptyF, except instead of “positional” location, each f a exists at a given index. NEMapF k is the “non-empty” variant. You can think of this as a ListF plus EnvT: it’s a “container” of multiple f as, but each one exists with a given “tag” index k.

In usage, like for ListF, the definer provides multiple “labeled” f as, and the interpreter can choose to interpret some or all of them, with access to each labeled.

inject creates a singleton Map at key mempty.

This is very useful in schemas that have sub-schemas indexed at specific keys. For example, in a command line argument parser, if we have a functor that represents a single command:
```
data Command a
```
We can immediately promote it to be a functor representing multiple possible named commands, each at a given string:
```
type Commands = MapF String Command
```
So we can implement “git push” and “git pull” using:
```
push :: Command Action
pull :: Command Action

gitCommands :: Commands Action
gitCOmmands = MapF . M.fromList $
    [ ("push", push)
    , ("pull", pull)
    ]
```
This is also useful for specifying things like routes in a server.

This type exists specialized as Steps, which is NEMapF (Sum Natural).

Interpret

instance Plus f => Interpret (MapF  k) f
instance Alt  f => Interpret (NEMap k) f

interpret @(MapF k)
    :: Plus f
    => g ~> f
    -> MapF g ~> f

interpret @(NEMapF k)
    :: Alt f
    => g ~> f
    -> NEMapF g ~> f

Interpreting out of a MapF k f requires the target context to be Plus, and interpreting out of a NEMapF k f requires Alt (because you will never have the empty case). However, you can directly look up into the Map and pick an item you want directly, which requires no constraint.

ReaderT

Origin: Control.Monad.Trans.Reader
Enhancement: Provide each f a with access to some “environment” r.
```
newtype ReaderT r f a = ReaderT { runReaderT :: r -> f a }
```
ReaderT r is often used to model some form of dependency injection: it allows you to work “assuming” you had an r; later, when you run it, you provide the r. It delays the evaluation of your final result until you provide the missing r.

Another way of looking at it is that it makes your entire functor have values that are parameterized with an r.

For example, if you have a form data type:
```
data FormElem a
```
you can now make a form data type that is parameterized by the current server hostname:
```
type FormElemWithHost = ReaderT HostName FormElem
```
The actual structure of your FormElem is deferred until you provide the HostName.

Note that, unlike ReaderT, most monad transformers from transformers are actually not valid functor combinators under our perspective here, because most of them are not natural on f: they require Functor f, at least, to implement inject or hmap.
Interpret
```
instance MonadReader r f => Interpret (ReaderT r) f

interpret @(ReaderT r)
    :: MonadReader r f
    => g ~> f
    -> ReaderT r g ~> f
```
Interpreting out of a ReaderT r requires requires the target context to be MonadReader r, which means it must have access to ask :: MonadReader r f => f r.

In a way, ReaderT r is the “free” instance of MonadReader r.

Step

Origin: Control.Applicative.Step
Enhancement: Tuples the f a with an extra natural number index.
```
data Step f a = Step { stepPos :: Natural, stepVal :: f a }
```
This is essentially a specialized EnvT: it’s EnvT (Sum Natural).

This is a useful type because it can be seen as equivalent to f :+: f :+: f :+: f :+: f ... forever: it’s an f, but at some index. In Control.Applicative.Step, we have specialized functions stepUp and stepDown, which allows you to “match” on the “first” f in that infinite chain; it will increment and decrement the index relatively to make this work properly.

Interpret

instance Interpret Step f

interpret @Step
    :: g ~> f
    -> Step g ~> f

Interpreting out of Step requires no constraints; we just drop the Natural data.

Steps

Origin: Control.Applicative.Step
Enhancement: The ability to offer multiple indexed options for the interpreter to pick from. Like NonEmptyF, except with each f a existing at an indexed position that the consumer/interpreter can look up or access.
```
newtype Steps f a = Steps { getSteps :: NEMap Natural (f a) }
```
This is like a mix between NonEmptyF and Step: multiple f a options (at least one) for the consumer/interpreter to pick from. Unlike NonEmptyF, each f a exists at an “index” — there might be one at 0, one at 5, one at 100, etc.

Another way of looking at this is like an infinite sparse array of f as: it’s an inifinitely large collection where each spot may potentially have an f a.

Useful for “provide options that the consumer can pick from, index, or access”, like ListF/NonEmptyF.

This type can be seen as an infinite f `These1` f `These1` f `These1` f ..., and along these lines, stepsDown and stepsUp exist inside Control.Applicative.Step analogous to stepUp and stepDown to treat a Steps in this manner.
Interpret
```
instance Alt f => Interpret Steps f

interpret @Steps
    :: Alt f
    => g ~> f
    -> Steps g ~> f
```
Interpreting out of Steps requires an Alt to combine different possibilities. It does not require a full Plus constraint because we never need zero: a Steps f a always has at least one f a.

Flagged

Origin: Control.Applicative.Step
Enhancement: The ability to “tag” a functor value with a True/False boolean value.
```
data Flagged f a = Flagged { flaggedFlag :: Bool, flaggedVal :: f a }
```
This is essentially a specialized EnvT: it’s EnvT Any.

If created with inject or pure, it adds the flag False. This is helpful for helping indicate if the value was created using a “pure” method like inject or pure, or an “impure” method (any other method, including direct construction).

Interpret

instance Interpret Flagged f

interpret @Flagged
    :: g ~> f
    -> Flagged g ~> f

Interpreting out of Flagged requires no constraints; we just drop the boolean flag.

Final

Origin: Data.HFunctor.Final
Enhancement: Final c will lift f into a free structure of any typeclass c; it will give it all of the actions/API of a typeclass for “free”. Final c f is the “free c” over f.
```
data Final c f a
```
In a way, this is the “ultimate free structure”: it can fully replace all other free structures of typeclasses of kind Type -> Type. For example:
```
Coyoneda  ~ Final Functor
ListF     ~ Final Plus
NonEmptyF ~ Final Alt
Ap        ~ Final Applicative
Ap1       ~ Final Apply
Free      ~ Final Monad
Free1     ~ Final Bind
Lift      ~ Final Pointed
IdentityT ~ Final Unconstrained
```
All of these are connections are witnessed by instances of the typeclass FreeOf in Data.HFunctor.Final.

In fact, Final c is often more performant for many operations than the actual concrete free structures.

The main downside is that you cannot directly pattern match on the structure of a Final c the same way you can pattern match on, say, Ap or ListF. However, you can get often around this by using Final Plus for most of your operations, and then interpret inject-ing it into ListF when you want to actually pattern match.

You can also think of this as the “ultimate Interpret”, because with inject you can push f into Final c f, and with interpret you only ever need the c constraint to “run”/interpret this.

So, next time you want to give an f the ability to <*> and pure, you can throw it into Final Applicative: f now gets “sequencing” abilities, and is equivalent to Ap f.

If you want the API of a given typeclass c, you can inject f into Final c, and you get the API of that typeclass for free on f.

Constraint

instance c f => Interpret (Final c) f

interpret @(Final c)
    :: c f
    => g ~> f
    -> Final c g ~> f

Interpreting out of a Final c requires c, since that is the extra context that f is lifted into.

Chain / Chain1

Origin: Data.HFunctor.Chain
Enhancement: Chain t will lift f into a linked list of fs chained by t.
```
-- i is intended to be the identity of t
data Chain t i f a = Done (i a)
                   | More (t f (Chain t i f a))
```
For example, for :*:, Chain (:*:) Proxy f is equivalent to one of:
```
Proxy   <=> Done Proxy                           <=> ListF []
x       <=> More (x :*: Done Proxy)              <=> ListF [x]
x :*: y <=> More (x :*: More (y :*: Done Proxy)) <=> ListF [x,y]
-- etc.
```
For :+:, Chain (:+:) V1 f is equivalent to one of:
```
L1 x           <=> More (L1 x)                         <=> Step 0 x
R1 (L1 y)      <=> More (R1 (More (L1 y)))             <=> Step 1 y
R1 (R1 (L1 z)) <=> More (R1 (More (R1 (More (L1 z))))) <=> Step 2 z
-- etc.
```
This is useful because it provides a nice uniform way to work with all “linked list over tensors”. That’s because the following types are all isomorphic:
```
ListF ~ Chain (:*:)  Proxy
Ap    ~ Chain Day    Identity
Free  ~ Chain Comp   Identity
Step  ~ Chain (:+:)  Void
Steps ~ Chain These1 Void
```
This isomorphism is witnessed by unroll (turn into the Chain) and reroll (convert back from the Chain) in Data.HFunctor.Chain.

We can “fold down” a Chain t (I t) f a into an f a, if t is Monoidal, using interpret id. In fact, this ability could be used as a fundamental property of monoidal nature.

We also have a “non-empty” version, Chain1, for non-empty linked lists over tensors:
```
data Chain1 t f a = Done1 (f a)
                  | More1 (t f (Chain1 t f a))
```
```
NonEmptyF ~ Chain1 (:*:)
Ap1       ~ Chain1 Day
Free1     ~ Chain1 Comp
Step      ~ Chain1 (:+:)
Steps     ~ Chain1 These1
EnvT Any  ~ Chain1 LeftF
Step      ~ Chain1 RightF
```
We can “fold down” a Chain1 t f a into an f a, if t is Semigroupoidal, using interpret id. In fact, this ability could be used as a fundamental property of semigroupoidal nature.

Using ListF, Ap, Free, Step, Steps, etc. can sometimes feel very different, but with Chain you get a uniform interface to pattern match on (and construct) all of them in the same way.

Using NonEmptyF, Ap1, Free1, Step, Flagged, etc. can sometimes feel very different, but with Chain1 you get a uniform interface to pattern match on (and construct) all of them in the same way.

Universally, we can concatenate linked chains, with:
```
appendChain
    :: Tensor t i
    => t (Chain t i f) (Chain t i f) ~> Chain t i f

appendChain1
    :: Associative t
    => t (Chain1 t f) (Chain1 t f) ~> Chain1 t f
```
These operations are associative, and this property is gained from the tensor nature of t.

The construction of Chain is inspired by Oleg Grenrus’s blog post, and the construction of Chain1 is inspired by implementations of finite automata and iteratees.

Interpret

instance MonoidIn    t i f => Interpret (Chain  t i) f
instance SemigroupIn t   f => Interpret (Chain1 t  ) f

interpret @(Chain t i)
    :: MonoidIn t i f
    => g ~> f
    -> Chain t i g ~> f

interpret @(Chain1 t)
    :: SemigroupIn t f
    => g ~> f
    -> Chain1 t g ~> f

Interpreting out of a Chain requires only that f is a monoid in t. Interpreting out of a Chain1 requires only that f is a semigroup in t.

For example, we have:

instance Plus f => Interpret (Chain  (:*:) Proxy) f
instance Alt  f => Interpret (Chain1 (:*:)      ) f

interpret @(Chain (:*:) Proxy)
    :: Plus f
    => g ~> f
    -> Chain (:*:) Proxy g ~> f

interpret @(Chain1 (:*:))
    :: Alt f
    => g ~> f
    -> Chain1 (:*:) f ~> f

instance Applicative f => Interpret (Chain  Day Identity) f
instance Apply       f => Interpret (Chain1 Day         ) f

instance Monad f => Interpret (Chain  Comp Identity) f
instance Bind  f => Interpret (Chain1 Comp         ) f

IdentityT

Origin: Data.Functor.Identity
Enhancement: None whatsoever; it adds no extra structure to f, and IdentityT f is the same as f; it’s the “free Unconstrained”
```
data IdentityT f a = IdentityT { runIdentityT :: f a }
```
This isn’t too useful on its own, but it can be useful to give to the functor combinator combinators as a no-op functor combinator. It can also be used to signify “no structure”, or as a placeholder until you figure out what sort of structure you want to have.

In that sense, it can be thought of as a “ListF with always one item”, a “MaybeF that’s always Just”’, an “Ap with always one sequenced item”, a “Free with always exactly one layer of effects”, etc.

Constraint

instance Interpret IdentityT f

interpret @IdentityT
    :: g ~> f
    -> IdentityT g ~> f

Interpreting out of IdentityT requires no constraints — it basically does nothing.

ProxyF / ConstF

Origin: Data.HFunctor
Enhancement: “Black holes” — they completely forget all the structure of f, and are impossible to interpret out of. Impossible“.
```
data ProxyF f a = ProxyF
data ConstF e f a = ConstF e
```
ProxyF is essentially ConstF ().

These are both valid functor combinators in that you can inject into them, and interpret id . inject == id is technically true (the best kind of true).

You can use them if you want your schema to be impossible to interpret, as a placeholder or to signify that one branch is uninterpretable. In this sense, this is like a “ListF that is always empty” or a “MaybeF that is always Nothing”.

Because of this, they aren’t too useful on their own — they’re more useful in the context of swapping out and combining or manipulating with other functor combinators or using with functor combinator combinators.
Interpret

You’re not going to have any luck here — you cannot interpret out of these, unfortunately!

Contravariant Functor Combinators

Addendum: Post functor-combinators-0.3.0.0

Most of the above functor combinators have been “covariant” ones: an t f a represents some “producer” or “generator” of as. Many of them require a Functor constraint on f interpret out of. However, there exist many useful contravariant ones too, where t f a represents a “consumer” of as; many of these require a Contravariant constraint on f to interpret out of. These can be useful as the building blocks of consumers like serializers.

I’ve included them all in a separate section because you to either be looking for one or the other, and also because there are much less contravariant combinators than covariant ones in the Haskell ecosystem.

Also note that many of the functor combinators in the previous sections are compatible with both covariant and contravariant functors, like:

:+:/Sum
LeftF/RightF
EnvT
Step
Flagged
Final
Chain
IdentityT

The following functor combinators in the previous section are also compatible with both, but their instances in functor-combinator are designed around covariant usage. However, some of them have contravariant twins that are otherwise identical except for the fact that their instances are instead designed around contravariant usage.

:*:/Product (contravariant version: the contravariant Day)
These1
ListF/NonEmptyF (contravariant versions: Div and Div1)
MaybeF

This section was added following the release of functor-combinators-0.3.0.0, which added in support for contravariant and invariant functor combinators.

Contravariant Day

Origin: Data.Functor.Contravariant.Day
Mixing Strategy: “Both, together”: provide two consumers that are each meant to consume one part of the input.
```
data Day f g a = forall x y. Day (f x) (g y) (a -> (x, y))
```
This type is essentially equivalent to :*:/Product if f is Contravariant, so it is useful in every situation where :*: would be useful. It can be thought of as simply a version of :*: that signals to the reader that it is meant to be used contravariantly (as a consumer) and not covariantly (as a producer).

Like for :*:, it has the distinguishing property (if f is Contravariant) of allowing you to use either the f or the g, as you please.
```
dayOutL :: Contravariant f => Day f g ~> f
dayOutL (Day x _ f) = contramap (fst . f) x

dayOutR :: Contravariant g => Day f g ~> g
dayOutR (Day _ y f) = contramap (snd . f) y
```
In practice, however, I like to think of it as storing an f and a g that can each handle a separate “part” of an a. For example, the illustrative helper function
```
day :: f a -> g b -> Day f g (a, b)
day x y = Day x y id
```
allows you to couple an f a consumer of a with a g b consumer of b to produce a consumer of (a, b) that does its job by handing the a to x, and the b to y.
Identity
```
instance Tensor Day Proxy
```
Since this type is essentially (:*:), it has the same identity.
```
day Proxy :: g b -> Day Proxy g (a, b)
```
is the Day that would “ignore” the a part and simply pass the b to g.

Monoids

instance Divise    f => SemigroupIn Day f
instance Divisible f => MonoidIn    Day Proxy f

binterpret @Day
    :: Divise f
    => g ~> f
    -> h ~> f
    -> Day g h ~> f

inL   @(:*:) :: Divisible g => f     ~> Day f g
inR   @(:*:) :: Divisible f => g     ~> Day f g
pureT @(:*:) :: Divisible h => Proxy ~> h

Divise from Data.Functor.Contravariant.Divise can be thought of some version the “contravariant Alt”: it gives you a way to merge two f as into a single one in a way that represents having both the items consume the input as they choose. The usual way of doing this is by providing a splitting function to choose to give some part of the input to one argument, and some part to another:

class Contravariant f => Divise f where
    divise :: (a -> (b, c)) -> f b -> f c -> f a
                  -- ^ what to give to the 'f b'
                     -- ^ what to give to the 'f c'

Divisible from Data.Functor.Contravariant.Divisible, adds an identity that will ignore anything it is given: conquer.

class Divise f => Divisible f where
    conquer :: f a

(note: like with Applicative and Apply, the actual version requires only Contravariant f; Divise isn’t an actual superclass, even though it should be.)

List type

Basically,
```
type NonEmptyBy Day = NonEmptyF
type ListBy     Day = ListF
```
Because the contravariant Day is equivalent to :*: for contravariant inputs, they have the exact same “list type”. However, in the functor-combinators library, each list type can only have a single Interpret instance, so instead the list types are defined to be a separate (identical) type with a different name:
```
type NonEmptyBy Day = Div1
type ListBy     Day = Div
```
Like for Day, it’s something that can be used instead of :*: to mentally signify how the type is meant to be used. You can think of Div f a as a chain of fs, where the a is distributed over each f, but the intent of its usage is that each f is meant to consume a different part of that a.

See the information later on Div alone for more information on usage and utility.

Div is the possibly-empty version, and Div1 is the nonempty version.

Night

Origin: Data.Functor.Contravariant.Night
Mixing Strategy: “One or the other, but chosen at consumption-time”: provide two consumers to handle input, but the choice of which consumer to use is made at consumption time.
```
data Night f g a = forall x y. Night (f x) (g y) (a -> Either x y)
```
This one represents delegation: Night f g a contains f and g that could process some form of the a, but which of the two is chosen to depends on the value of a itself.

This can be thought of as representing sharding between f and g. Some discriminator determins which of f or g is better suited to consume the input, and picks which single one to use based on that.

The illustrative helper function can make this clear:
```
night :: f a -> g b -> Night f g (Either a b)
night x y = Night x y id
```
allows you to couple an f a consumer of a with a g b consumer of b to produce a consumer of Either a b that does its job by using the f if given a Left input, and using the g if given a b input.

This is technically still a day convolution (mathematically), but it uses Either instead of the typical (,) we use in Haskell. So it’s like the opposite of a usual Haskell Day — it’s Night :)
Identity
```
instance Tensor Night Not

-- | Data type that proves @a@ cannot exist
newtype Not a = Not { refute :: a -> Void }
```
If Night f g assigns input to either f or g, then a functor that “cannot be chosen”/“cannot be used” would force the choice to the other side.

That is, Night f Not must necessarily pass its input to f, as you cannot pass anything to a Not, since it only accepts passing in uninhabited types.

Monoids

instance Decide   f => SemigroupIn Night f
instance Conclude f => MonoidIn    Night Not f

binterpret @Night
    :: Decide f
    => g ~> f
    -> h ~> f
    -> Night g h ~> f

inL   @Night :: Conclude g => f   ~> Night f g
inR   @Night :: Conclude f => g   ~> Night f g
pureT @Night :: Conclude h => Not ~> h

Decide from Data.Functor.Contravariant.Decide can be thought of as a deterministic sharding typeclass: You can combine two consumers along with a decision function on which consumer to use.

class Contravariant f => Decide f where
    decide :: (a -> Either b c) -> f b -> f c -> f a
                        -- ^ use the f b
                          -- ^ use the f c

Conclude from Data.Functor.Contravariant.Conclude, adds support for specifying an f that cannot be chosen by the decision function when used with decide.

class Decide f => Conclude f where
    conclude :: (a -> Void) -> f a

List type
```
type NonEmptyBy Night = Dec1
type ListBy     Night = Dec
```
Dec f and Dec1 f represent a bunch of fs Night’d with each other — you can think of Dec f was the sharding over many different fs (or even none), and Dec1 f as the sharding over at least one f.

See the later section on Dec for more information.

Contravariant Coyoneda

Origin: Data.Functor.Contravariant.Coyoneda
Enhancement: The ability to contravariantly map over the parameter; it’s the free Contravariant.

Can be useful if f is created using a GADT that cannot be given a Contravariant instance.

For example, here is an indexed type that represents the type of a “prettyprinter”, where the type parameter represents the type that is being pretty-printed output result of the form element.
```
data PrettyPrim :: Type -> Type where
    PPString  :: PrettyPrim String
    PPInt     :: PrettyPrim Int
    PPBool    :: PrettyPrim Bool
```
Then Coyoneda PrettyPrim has a Contravariant instance. We can now contramap over the input type of the pretty-printer; for example, contramap :: (a -> b) -> Coyoneda PrettyPrim b -> Coyoneda PrettyPrim a takes a prettyprinter of bs and turns it into a prettyprinter of as.
Interpret
```
instance Contravariant f => Interpret Coyoneda f

interpret @Coyoneda
    :: Contravariant f
    => g ~> f
    -> Coyoneda g ~> f
```
Interpreting out of a Coyoneda f requires the target context to itself be Contravariant. For example, if we want to “run” a Coyoneda PrettyPrim in Op String (Op String a is a function from a to String), this would be interpret :: (forall x. PrettyPrim x -> Op String x) -> Coyoneda PrettyPrim a -> Op String a.

Div / Div1

Origin: Data.Functor.Contravariant.Divisible.Free
Enhancement: The ability to provide multiple fs to each consume a part of the overall input.

If f x is a consumer of xs, then Div f a is a consumer of as that does its job by splitting a across /all/ fs, forking them out in parallel. Often times, in practice, this will utilized by giving each f a separate part of the a to consume.

For example, let’s say you had a type Socket a which represents some IO channel or socket that is expecting to receive as. A Div Socket b would be a collection of sockets that expects a single b overall, but each individual Socket inside that Div is given some part of the overall b.

Another common usage is to combine serializers by assigning each serializer f to one part of an overall input.

Structurally, Div and Div1 are basically lists of contravariant coyonedas:
```
newtype Div  f a = Div  { unDiv  :: [Coyoneda f a]          }
newtype Div1 f a = Div1 { unDiv1 :: NonEmpty (Coyoneda f a) }
```
This could be implemented as simply a normal [f a] and NonEmpty (f a) (and so making them identical to ListF). For the most part, you could use the two interchangely, except in the case where you need to Interpret out of them: ListF requires a Plus constraint, and Div requires a Divisible constraint. The Coyoneda is also necessary for compatibility with the version of the contravariant Day convolution provided by kan-extensions.

Div1 is a variety of Div where you always have to have “at least one f”. Can be useful if you want to ensure, for example, that at least one socket will be handling the input (and it won’t be lost into the air).

Interpret

instance Divisible f => Interpret Div  f
instance Divise    f => Interpret Div1 f

interpret @Div
    :: Divisible f
    => g ~> f
    -> Div g ~> f

interpret @Div1
    :: Divise f
    => g ~> f
    -> Div1 g ~> f

Interpreting out of an Div f requires the target context to be Divisible, and interpreting out of a Div1 f requires Divise (because you will never need the empty case).

Dec / Dec1

Origin: Data.Functor.Contravariant.Divisible.Free
Enhancement: The ability to provide multiple fs, one of which will be chosen to consume the overall input.

If f x is a consumer of xs, then Dec f a is a consumer of as that does its job by choosing a single one of those fs to handle that consumption, based on what a is received.

Contrast this with Div, where the multiple f actions are all used to consume the input. Dec only uses one single f action to consume the input, chosen at consumption time.

For example, let’s say you had a type Socket a which represents some IO channel or socket that is expecting to receive as. A Dec Socket b would be a collection of sockets that expects a single b overall, and will pick exactly one of those Sockets to handle that b.

In this sense, you can sort of think of Dec as a “sharding” of fs: each f handles a different possible categorization of the input.

Another common usage is to combine serializers by assigning each serializer f to one possible form of possible input.

Structurally, Dec is built like a linked list of f xs, which each link being existentially bound together:
```
data Dec :: (Type -> Type) -> Type -> Type where
    Lose   :: (a -> Void) -> Dec f a
    Choose :: f x -> Dec f y -> (a -> Either x y) -> Dec f a
```
This is more or less the same construction as for Ap: see information on Ap for a deeper explanation on how or why this works.

Dec1 is a variety of Dec where you always have to have “at least one f”. Can be useful if you want to ensure, for example, that there always exists at least one f that can handle the job.

Interpret

instance Conclude f => Interpret Dec  f
instance Decide   f => Interpret Dec1 f

interpret @Dec
    :: Conclude f
    => g ~> f
    -> Dec g ~> f

interpret @Dec1
    :: Decide f
    => g ~> f
    -> Dec1 g ~> f

Interpreting out of an Dec f requires the target context to be Conclude, and interpreting out of a Dec1 f requires Decide (because you will never need the rejecting case).

Combinator Combinators

There exist higher-order functor combinator combinators that take functor combinators and return new ones, too. We can talk about a uniform interface for them, but they aren’t very common, so it is probably not worth the extra abstraction.

ComposeT

Origin: Control.Monad.Trans.Compose
Enhancement: Compose enhancements from two different functor combinators
```
newtype ComposeT s t f a = ComposeT { getComposeT :: s (t f) a }
```
Can be useful if you want to layer or nest functor combinators to get both enhancements as a single functor combinator*.

Usually really only useful in the context of other abstractions that expect functor combinators, since this is the best way to turn two functor combinators into a third one.

Interpret

instance (Interpret s f, Interpret t f) => Interpret (ComposeT s t) f

interpret @(ComposeT s t)
    :: (Interpret s f, Interpret t f)
    => g ~> f
    -> ComposeT s t g ~> f

Interpreting out of these requires the constraints on both layers.

HLift

Origin: Data.HFunctor
Enhancement: HLift t f lets f exist either unchanged, or with the structure of t.
```
data HLift t f a
    = HPure  (f a)
    | HOther (t f a)
```
Can be useful if you want to “conditionally enhance” f. Either f can be enhanced by t, or it can exist in its pure “newly-injected” form.

If t is Identity, we get EnvT Any, or f :+: f: the “pure or impure” combinator.

Interpret

instance Interpret t f => Interpret (HLift t) f

interpret @(HLift t)
    :: Interpret t f
    => g ~> f
    -> HLift t g ~> f

Interpreting out of these requires the constraint on t, to handle the HOther case.

HFree

Origin: Data.HFunctor
Enhancement: HFree t f lets f exist either unchanged, or with multiple nested enhancements by t.
```
data HFree t f a
    = HReturn (f a)
    | HJoin   (t (HFree t f) a)
```
It is related to HLift, but lets you lift over arbitrary many compositions of t, enhancing f multiple times. This essentially creates a “tree” of t branches.

One particularly useful functor combinator to use is MapF. In our earlier examples, if we have
```
data Command a
```
to represent the structure of a single command line argument parser, we can use
```
type Commands = MapF String Command
```
to represent multiple potential named commands, each under a different String argument. With HFree, we can also use:
```
type CommandTree = HFree (MapF String) Command
```
to represent nested named commands, where each nested sub-command is descended on by a String key.

For another example, HFree IdentityT is essentially Step.
Interpret
```
instance Interpret t f => Interpret (HFree t) f

interpret @(HFree t)
    :: Interpre t f
    => g ~> f
    -> HFree t g ~> f
```
Interpreting out of these requires the constraint on t, to handle the HJoin case.

However, it is probably usually more useful to directly pattern match on HReturn and HJoin and handle the recursion explicitly.

Alternatively, we can also define a recursive folding function (provided in Data.HFunctor) to recursively fold down each branch:
```
foldHFree
    :: HFunctor t
    => (g ~> f)
    -> (t g ~> f)
    -> HFree t g ~> f
```
This can be useful because it allows you to distinguish between the different branches, and also requires no constraint on g.

Applied to the CommandTree example, this becomes:
```
foldHFree @(MapF String) @Command
    :: Command ~> f
    -> MapF String ~> f
    -> CommandTree ~> f
```

Closing Comments

As I discover more interesting or useful functor combinators (or as the abstractions in functor-combinators change), I will continue to update this post. And, in the upcoming weeks and months I plan to present specific programs I have written (and simple examples of usage) that will help show this design pattern in use within a real program.

For now, I hope you can appreciate this as a reference to help guide your exploration of unique “a la carte” (yet not fixed-point-centric) approach to building your programs! You can jump right into using these tools to build your program today by importing Data.Functor.Combinator or wherever they can be found.

I’d be excited to hear about what programs you are able to write, so please do let me know! You can leave a comment, find me on twitter at @mstk, or find me on freenode irc idling on #haskell as jle` if you want to share, or have any questions.

Special Thanks

I am very humbled to be supported by an amazing community, who make it possible for me to devote time to researching and writing these posts. Very special thanks to my supporter at the “Amazing” level on patreon, Josh Vera! :)

Also a special thanks to Koz Ross, who helped proofread this post as a draft.

On the surface, this functor combinator design pattern might look like it fills a similar space to effects systems and libraries like mtl, polysemy, freer-simple, or fused-effects. However, this design pattern actually exists on a different level.

Functor combinator design patterns can be used to help build the structure of the data types and schemas that define your program/DSL. Once you build these nice structures, you then interpret them into some target context. This “target context” is the realm that libraries like mtl and polysemy can fill; functor combinators serve to help you define a structure for your program before you interpret it into whatever Applicative or Monad or effects system you end up using.↩︎