The Functor Combinatorpedia

SourceMarkdownLaTeXPosted in HaskellComments


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.)

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:

  1. Forces you to make explicit decisions about the structure of your computation type as an ADT.
  2. Allows you to retain isolation of fundamental parts of your domain as separate types
  3. 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.
  4. 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.1 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.

  1. :+:: Provide either, be ready for both.
  2. :*:: Provide both, be ready for either.
  3. Day: Provide both, be ready for both.
  4. 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!

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]twitter, 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.


  1. 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.↩︎

Comments powered by Disqus