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 ListBy t.

If t is Tensor, then it means we can "collapse" this linked list into some final type ListBy t (reroll), and also extract it back into a linked list (unroll).

So, a value of type Chain t i f a is one of either:

• i 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 ListBy t is supposed to be. Using Chain allows us to work with all ListBy ts in a uniform way, with normal pattern matching and normal constructors.

You can fully "collapse" a Chain t i f into an f with retract, if you have MonoidIn t i f; this could be considered a fundamental property of monoid-ness.

Another way of thinking of this is that Chain t i is the "free MonoidIn t i". Given any functor f, Chain t i f is a monoid in the monoidal category of endofunctors enriched by t. So, Chain Comp Identity is the "free Monad", Chain Day Identity is the "free Applicative", etc. You "lift" from f a to Chain t i f a using inject.

Note: this instance doesn't exist directly because of restrictions in typeclasses, but is implemented as

Tensor t i => MonoidIn (WrapHBF t) (WrapF i) (Chain t i f)

where pureT is Done and biretract is appendChain.

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" (nilLB), 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.

An "effectful" version of foldChain, weaving Applicative effects.

Since: 0.3.6.0

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 ListBy t is supposed to represent the successive application of ts to itself. unroll makes that successive application explicit, buy converting it to a literal Chain of applications of t to itself.

unroll = unfoldChain unconsLB

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

reroll = foldChain nilLB consLB

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

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

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

unrolling states that the two types are isormorphic. Use unroll and reroll 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.

This is essentially biretract, but only requiring Tensor t i: it comes from the fact that Chain1 t i is the "free MonoidIn t i". pureT is Done.

Since: 0.1.1.0

For completeness, an isomorphism between Chain and its two constructors, to match splittingLB.

Since: 0.3.0.0

Convert a tensor value pairing two fs into a two-item Chain. An analogue of toListBy.

Since: 0.3.1.0

Create a singleton chain.

Since: 0.3.0.0

An analogue of unconsLB: match one of the two constructors of a Chain.

Since: 0.3.0.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 NonEmptyBy 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 NonEmptyBy t. And that's "the point": for all instances of Associative, Chain1 t is isomorphic to NonEmptyBy t (witnessed by unrollingNE). That's big picture of NonEmptyBy: 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 NonEmptyBy t in a uniform way. Unlike for NonEmptyBy 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 NonEmptyBy t f and Chain1 t f with unrollNE and rerollNE. You can fully "collapse" a Chain1 t f into an f with retract, if you have SemigroupIn t f; this could be considered a fundamental property of semigroup-ness.

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

Another way of thinking of this is that Chain1 t is the "free SemigroupIn t". Given any functor f, Chain1 t f is a semigroup in the semigroupoidal category of endofunctors enriched by t. So, Chain1 Comp is the "free Bind", Chain1 Day is the "free Apply", etc. You "lift" from f a to Chain1 t f a using inject.

Note: this instance doesn't exist directly because of restrictions in typeclasses, but is implemented as

Associative t => SemigroupIn (WrapHBF t) (Chain1 t f)

where biretract is appendChain1.

You can fully "collapse" a Chain t i f into an f with retract, if you have MonoidIn t i f; this could be considered a fundamental property of monoid-ness.

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.

An "effectful" version of foldChain1, weaving Applicative effects.

Since: 0.3.6.0

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

unrollingNE states that the two types are isormorphic. Use unrollNE and rerollNE to convert between the two.

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

unrollNE = unfoldChain1 matchNE

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

rerollNE = foldChain1 inject consNE

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

This is essentially biretract, but only requiring Associative t: it comes from the fact that Chain1 t is the "free SemigroupIn t".

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.

For completeness, an isomorphism between Chain1 and its two constructors, to match matchNE.

Since: 0.3.0.0

Convert a tensor value pairing two fs into a two-item Chain1. An analogue of toNonEmptyBy.

Since: 0.3.1.0

Create a singleton Chain1.

Since: 0.3.0.0

A Chain1 t f is like a non-empty linked list of fs, and a Chain t i 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 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 f is either empty (i) or non-empty (Chain1 t f).

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