A useful construction that works like a "linked list" of t f applied to itself multiple times. That is, it contains t f f, t f (t f f), t f (t f (t f f)), etc, with f occuring zero or more times. It is meant to be the same as MF t.

If t is Monoidal, then it means we can "collapse" this linked list into some final type MF t (rerollMF), and also extract it back into a linked list (unrollMF).

So, a value of type Chain t (I t) f a is one of either:

• I t a

• f a

• t f f a

• t f (t f f) a

• t f (t f (t f f)) a

• .. etc.

Note that this is exactly what an MF t is supposed to be. Using Chain allows us to work with all MF ts in a uniform way, with normal pattern matching and normal constructors.

You can fully "collapse" a Chain t (I t) f into an f with retract, if t is Monoidal; this could be considered a fundamental property of monoidal-ness.

This construction is inspired by http://oleg.fi/gists/posts/2018-02-21-single-free.html

Recursively fold down a Chain. Provide a function on how to handle the "single f case" (nilMF), and how to handle the "combined t f g case", and this will fold the entire Chain t i) f into a single g.

This is a catamorphism.

Recursively build up a Chain. Provide a function that takes some starting seed g and returns either "done" (i) or "continue further" (t f g), and it will create a Chain t i f from a g.

This is an anamorphism.

A type MF t is supposed to represent the successive application of ts to itself. unrollMF makes that successive application explicit, buy converting it to a literal Chain of applications of t to itself.

unrollMF = unfoldChain unconsMF

A type MF t is supposed to represent the successive application of ts to itself. rerollSF takes an explicit Chain of applications of t to itself and rolls it back up into an MF t.

rerollMF = foldChain nilMF consMF

Because t cannot be inferred from the input or output, you should call this with -XTypeApplications:

rerollMF @Comp
    :: Chain Comp Identity f a -> Free f a

A type MF t is supposed to represent the successive application of ts to itself. The type Chain t (I t) f is an actual concrete ADT that contains successive applications of t to itself, and you can pattern match on each layer.

unrollingMF states that the two types are isormorphic. Use unrollMF and rerollMF to convert between the two.

Chain is a monoid with respect to t: we can "combine" them in an associative way. The identity here is anything made with the Done constructor.

Since: 0.1.1.0

A useful construction that works like a "non-empty linked list" of t f applied to itself multiple times. That is, it contains t f f, t f (t f f), t f (t f (t f f)), etc, with f occuring one or more times. It is meant to be the same as SF t.

A Chain1 t f a is explicitly one of:

• f a

• t f f a

• t f (t f f) a

• t f (t f (t f f)) a

• .. etc

Note that this is exactly the description of SF t. And that's "the point": for all instances of Semigroupoidal, Chain1 t is isomorphic to SF t (witnessed by unrollingSF). That's big picture of SF: it's supposed to be a type that consists of all possible self-applications of f to t.

Chain1 gives you a way to work with all SF t in a uniform way. Unlike for SF t f in general, you can always explicitly /pattern match/ on a Chain1 (with its two constructors) and do what you please with it. You can also construct Chain1 using normal constructors and functions.

You can convert in between SF t f and Chain1 t f with unrollSF and rerollSF. You can fully "collapse" a Chain1 t f into an f with retract, if t is Semigroupoidal; this could be considered a fundamental property of semigroupoidal-ness.

See Chain for a version that has an "empty" value.

This construction is inspired by iteratees and machines.

Recursively fold down a Chain1. Provide a function on how to handle the "single f case" (inject), and how to handle the "combined t f g case", and this will fold the entire Chain1 t f into a single g.

This is a catamorphism.

Recursively build up a Chain1. Provide a function that takes some starting seed g and returns either "done" (f) or "continue further" (t f g), and it will create a Chain1 t f from a g.

This is an anamorphism.

A type SF t is supposed to represent the successive application of ts to itself. The type Chain1 t f is an actual concrete ADT that contains successive applications of t to itself, and you can pattern match on each layer.

unrollingSF states that the two types are isormorphic. Use unrollSF and rerollSF to convert between the two.

A type SF t is supposed to represent the successive application of ts to itself. unrollSF makes that successive application explicit, buy converting it to a literal Chain1 of applications of t to itself.

unrollSF = unfoldChain1 matchSF

A type SF t is supposed to represent the successive application of ts to itself. rerollSF takes an explicit Chain1 of applications of t to itself and rolls it back up into an SF t.

rerollSF = foldChain1 inject consSF

Chain1 is a semigroup with respect to t: we can "combine" them in an associative way.

Since: 0.1.1.0

A Chain1 is "one or more linked fs", and a Chain is "zero or more linked fs". So, we can convert from a Chain1 to a Chain that always has at least one f.

The result of this function always is made with More at the top level.

A Chain1 t f is like a non-empty linked list of fs, and a Chain t (I t) f is a possibly-empty linked list of fs. This witnesses the fact that the former is isomorphic to f consed to the latter.

The "forward" function representing splittingChain1. Provided here as a separate function because it does not require Functor f.

A Chain t (I t) f is a linked list of fs, and a Chain1 t f is a non-empty linked list of fs. This witnesses the fact that a Chain t (I t) f is either empty (I t) or non-empty (Chain1 t f).

The "reverse" function representing matchingChain. Provided here as a separate function because it does not require Functor f.