Haskell: Indexed Recursion Schemes

Finding your way back after a recursive descent into madness

Indexing schemes

Today, we are going on a deep dive to show how recursion schemes may be extended by the addition of indexing. Last time, we defined over 30 related functions, and this time we're making indexed variants of all of them, so at least 30 more, plus any supporting functions we might need. It could be a descent into a labyrinth of madness - but don't worry, we will be smart as Theseus, with our own version of Ariadne's golden thread. No matter how deep we go, indices will guide us on our way back.

In a previous article, we developed version 0.0.1 of a birecursion-schemes package, focused on 5 core recursive functions: cata, ana, hylo, iso, and trans, plus their -M monadic variants. For each, we then derived their birecursive bi- and direcursive di- variants. This library has been updated to 0.0.2 following along with today's article.

As we go exploring, we are going to do our best to provide examples to illustrate things, so you should get comfortable and have a snack handy - it's going to be a long one.

As always, we start by asking questions.

What's in an index?

That which we call a rose, by any other index would smell as sweet.

• William Shakespeare, almost

So what exactly is an index? As always, etymology is our first resort. The word 'index' (plural 'indices') has its origins in latin, and its meaning remains largely unchanged: literally 'forefinger' as in your index or pointer finger, but also abstractly as 'sign' or 'pointer' or 'indicator'. It is derived from the verb 'indico': prefix 'in-', meaning 'towards', followed by 'dico', meaning 'to point out, make known, set apart'. Note the relationship between 'indices' and 'indico' and 'indicate'

Taken all together, an 'index' is a thing that points you in the right direction to where something can be made known: it guides you in a traversal of knowledge (that's quite the clue as to what we're going to be getting into). This is largely the same as its modern usage, even for niche-specific variants, a bit of linguistic preservation. We have been using indices for millenia to look up more specific data, from catalogues in roman libraries, to the the modern dewey decimal system, and now we are going to use indices to find our way within data structures.

Now, we could just say that an index tells us how to access a element of that data structure, and be done with it - but that isn't the whole story. You see, indexing can be a muddy affair if we are not precise with our terminology - sometimes you have an index like with Vector, other times a key as in Map, still other times a path like Json.

These terms all have colloquial use, but we're going to have to precisely define them - taking into account things like that an index may point to a child of the same type in a recursive structure, or it may point to content of a different type in a container - and that recursive containers have both children and content? It all seems to depend on how and what you are using indexing for - a change of perspective results in a change of emphasis, after all. Given that we're going to be mixing indexing with recursion, it's going to to pay off to be precise, otherwise we're going to get lost in the labyrinth.

Another concern is that sometimes the index is obviously related to the shape of the data structure - a Vector is indexed by integers that tell you exactly where each element is - but other times, the index is not obviously related to the shape of the data structure at all, and instead it functions more as an arbitrary label - a Map k is seemingly indexed by whatever you want. We have, seemingly in contention, two different perspectives of what an index is, and our explanation has to handle both.

This last point is interesting enough that it marks our starting point, and by clarifying that last point, we may begin our descent. Our first step is to split the concept of an index into two different groups - structural indices, and profunctoral keys.

Structural indices

Sometimes an index tells you exactly where to go.

In this case, an index is in some sense 'a reduction of the rest of the data structure' - sufficient instructions as to navigate quickly and efficiently to the desired value. The book is the fifth from the right, on the top shelf of the third row. We will call this the 'structural' perspective of indices.

It is not an alien concept, with Connor McBride having written the rather relevant The Derivative of a Regular Type is its Type of One-Hole Contexts. This term 'one-hole context' is an elegant way to refer to 'the rest of the data structure', and so we will adopt the terminology for that reason.

A structural index could be considered the minimal / forgetful 'one-hole context' , with all extraneous data not leading to the hole removed / replaced by () - aka Free StructureF () where everything not on 'the path' is implicitly (). The resulting structure is a spine or path that goes all the way from the hole back up to the top of the original data structure, and contains just enough information to navigate back down to it. I haven't made such lovely graphs as the one-hole-context paper yet, so you'll have to imagine tracing a line from the hole back to the top of the data structure, and clipping off everything else.

The most clear example is the simple List indexed by Nat.

data List elem = Nil  | Cons elem (List elem)
data Nat       = Zero | Succ      Nat

-- The index of 'c' is SSZ = 2
abc = Cons 'a'  (Cons 'b'  (Cons 'c' Nil))
--    Cons ()   (Cons ()   Nil)
--    Succ      (Succ      Zero)

We can clearly see that a Nat is a List that has forgotten every element before the one that we are indexing, but also every child list after. This explains why Nat is isomorphic to [()], and why Succ (Succ Zero) == [Unit,Unit]. Note that we should be able to define such an index for just about any sensible sum of products type.

However, we caution the reader to observe carefully that the derivation is not always so simple - for instance, Zero does not correspond to Nil but rather to the singular elem position within Cons. Some data structures have multiple functor content points. Take, for instance, a Bilist which contains two elements per Bicons.

Note that rather than explicitly fill with (), we'll just ignore whatever's there with a blank _ since it's a little easier on the eyes.

data Bit = Zit | Bit -- NOTE: Bit = Biunit aka Bool

data Binat = Bizero Bit | Bisucc Binat

data Bilist a = Binil | Bicons a a (Bilist a)

-- The index of 'c' is SZ(0), and the index of 'd' is SZ(1).
abcdef = Bicons 'a' 'b' (Bicons 'c' 'd' (Bicons 'e' 'f' Binil))
--       Bicons _   _   (Bicons 'c' _   _)      -- 'c'
--       Bisucc         (Bizero Zit)            -- SZ(0)
--       Bicons _   _   (Bicons _ 'd'   _)      -- 'd'
--       Bisucc         (Bizero   Bit)          -- SZ(1)

Another pitfall is multiple points of recursion - this also affects how we derive our structural index:

data Dir = Left | Right -- NOTE: Dir == Bit

data Tree a = Tip | Node a (Tree a) (Tree a)

data Branch = Leaf | Limb Dir Branch -- NOTE: is just [Dir] or `([Dir], Unit) in disguise

-- The index of 'c' is `[Right]` or `Limb Right Leaf`
treeabc = Node 'a'   (Node 'b' Tip Tip) (Node 'c' Tip Tip)
--        Node _     _                  (Node 'c' _   _)
--        Limb Right                    Leaf

In fact we can see both interacting with a tree that contains both two content points and two recursion points.

data Bitree a = Bitip | Binode a a (Bitree a) (Bitree a)

data Bibranch = Bileaf Bit | Bilimb Dir Bibranch

-- The index of 'c' is `([Left], Zit)` or `Bilimb Left (Bileaf Zit)`
bitreeabcdef = Binode 'a' 'b' (Binode 'c' 'd' Bitip Bitip) (Binode 'e' 'f' Bitip Bitip)
--             Binode _   _   (Binode 'c' _   _     _    ) _
--             Bilimb Left    (Bileaf Zit)

Okay, something is funny - we started with the statement that an index is based on the structure of the original, and yet the index of a Bitree is list-like! In fact, they're all list-like!

It should be obvious now that indices are related to the form data Way path end = End end | Path path (Way path end) - and that the index of List should actually be Way Unit Unit because it only has one recursion point (hence the first Unit) and also only one element slot (hence the second). A Bilist has index Way Unit Bit, a Tree has index Way Dir Unit, and a Bitree has index Way Dir Bit. The Bitree case is especially illuminating because it shows that indexes always have zero or more "branches", followed by exactly one "leaf" - this exactly matches our examples. We can even use Way Void end to index data structures that explicitly aren't recursive!

What gives!? Well, we've traded off "replacing irrelevant data points with blanks" for "counting the number of positions filled with blanks before our data" It just so happens that with List, the two concepts coincide - because it has both one content slot, and one recursion point.

Way is still a reduction of the one-hole context - the rest of the data structure. path is a reduction of the recursive branches taken, and end is a reduction of the final branch containing the indexed value. This means that for our purposes, Way is just a different way of representing Free StructureF () (again, with the constraint that everything off-path is replaced by () or _) - one is efficient in the metric of 'shaped like the original data structure' and the other is efficient in the metric of 'has a compact representation'.

This 'filling blanks' vs 'counting blanks' doesn't matter, because we can always go back and forth. We can always count filled blanks, and having a count always tells us how many blanks to fill, and everything after the indexed element is either truncated or ignored.

NOTE: When it comes to an index for a single selected element, we can either fill blanks, or count blanks and it doesn't matter - but there are cases where it may start to matter for efficiency 'how' we reduce the rest of the data structure to an index. When it comes to distributed data and distributed indices, blanks are filled with proofs instead of (), and the difference between index and data becomes more like 'how much do you know'. There is a lot to think about.

For the majority of the article, we will focus on structural indices, as they form the foundation of today's work, and everything we just discussed will come in handy. But first, let us discuss for a moment the other perspective.

Profunctoral keys

Sometimes an index is a label that helps you search, because anything that you can turn into an label, is also label, and thus an index.

Rather than telling you exactly where something is, this type of index helps narrow it down, often in steps. The book is in the fiction section, between "Green" and "Grishom". Note that while structural indices are concrete, profunctoral keys are abstracted. This allows for indexing collections that involve factors like balancing - a profunctoral key doesn't tell you exactly where the book is, because that information is specific to a given library layout. If the library were to reorganize itself, a structural index would have to change - but a profunctoral key would not have to.

This makes profunctoral keys great for organized piles where you don't always know where things are, but you do know where things aren't - and when you know that 'all other values are somewhere else', you then know that 'if there is any value here, it is the one that I seek'.

We call it profunctoral in reference to:

class Profunctor (f :: * -> * -> *) where
    promap :: (a -> b) -> (c -> d) -> p b c -> p a d -- aka Profunctor.dimap
    premap :: (a -> b) -> p b c -> p a c             -- aka Profunctor.lmap
    postmap :: (b -> c) -> p a b -> p a c            -- aka Profunctor.rmap

Specifically, we can use premap / lmap to change the type of a key in data structures like Map k, eg if you have a f :: k2 -> k you can turn the m :: Map k into a m2 :: Map k2, because you can on-the-fly turn all k2s into ks immediately before using them using m2 = premap f m.

Profunctoral keys often work by offloading some of the organizational logic to a constraint, such Ord, which is why Map requires such a constraint - it is masking that, inside, it turns k into something else to navigate (like an Int). We can even go as far as to use just an Eq constraint - if Ord k => Map k a is an organized pile, then Eq k => AssocList k a is an unorganized pile, and yet you can still, albeit with a loss of efficiency. If a structural index gets its organization factor from the data structure, a profunctoral index gets its organization from the key.

An appropriate example of a profunctoral key might be IntMap, where the true index isn't Int but rather (Min Int, Max Int), because we start at the top with an index of (-Infinity, Infinity) and narrow it down via (min,max) as we descend recursively - our initial "key" gives us one of our bounds, and which branch we take tells us the other. We reduce (min,max) until we have min == max because that is where our value is located. It is only when we consider the entire recursive functor head structure of the IntMap that the index sums up the steps that we took to become an Int.

Profunctoral keys afford a great deal of flexibility and convenience, because they allow you to ignore the precise structure required to reach an element. This in turn mean that the keys can have other desirable properties such as being able to survive edits of a data structure due to the insertion or deletion of other elements, or balancing of the data structure - the same sort of indirection that makes pointers useful in C.

The abstraction of profunctoral keys is not free, however - it must necessarily build off of the structural indices, despite the two seemingly contradictory perspectives. Do not worry - at the end of this article, we will explain this contradiction and reveal how the profunctoral keys have been hidden inside the entire time.

Existing packages

With all of that in mind, we should take a quick look at the existing ecosystem - it will help us decide on how to go about implementing this sort of logic. At this point, we have enough information to more clearly search for existing libraries, modules, and classes - and we find ourselves a scattered but mostly-consistent ecosystem. This could all use a good deal of unification, but for now let us see what we have discovered.

In no particular order, we have:

containers & vector

Several commonly-used modules (such as Map and Vector) have functions specific to their data structures.

Vector.imap :: (Int -> a -> b) -> Vector a -> Vector b 
Map.mapWithKey :: (k -> a -> b) -> Map k a -> Map k b 

If we generalize, we get imap :: (i -> a -> b) -> f a -> f b, which is a function type that we can use in a class definition.

lens

The lens package provides a class for indexed functors, using FunctionalDependencies:

-- lens: Control.Lens.Combinators
class Functor f => FunctorWithIndex i (f :: Type -> Type) | f -> i where
    imap :: (i -> a -> b) -> f a -> f b 

indexed-traversable

The indexed-traversable package has a practically identical definition - unsurprising as it was extracted from lens in the first place.

-- indexed-traversable: Data.Functor.WithIndex
class Functor f => FunctorWithIndex i f | f -> i where
    imap :: (i -> a -> b) -> f a -> f b

Notably, it also contains FoldableWithIndex and TraversableWithIndex - we'll keep these in mind.

keys

The keys package is a package that uses TypeFamilies instead of FunctionalDependencies. However, it is very minimal, and also deprecated.

-- keys: Data.Key
type family Key (f :: * -> *)
class Functor f => Keyed f where
    mapWithKey :: (Key f -> a -> b) -> f a -> f b 

mono-traversable-keys

An honorable mention is mono-traversable-keys, which is keys for monomorphic functors. It is worth noting for inclusion, but for now we're not going to be exploring monomorphic functors, even though they do relate to recursives through a recursive structure being a monomorphic functor where its elements are the same type as itself.

-- mono-traversable-keys: Data.MonoTraversable.Keys
type family MonoKey key 
class MonoFunctor mono => MonoKeyed mono where
    omapWithKey :: (MonoKey mono -> Element mono -> Element mono) -> mono -> mono

base

Another honorable mention is Data.Ix in base. It isn't exactly what we want but we can sense a relation because the class is used for indexing contiguous arrays while still allowing the index type to be abstracted to anything orderable + rangeable.

-- base: Data.Ix
class Ord a => Ix a where
    range :: (a, a) -> [a]
    index :: (a, a) -> a -> Int
    inRange :: (a, a) -> a -> Bool

Remember IntMap secretly operating over (min,max) rather than Int? That notion is expressed here in class form.

adjunctions

Finally, we have a really interesting class found in adjunctions - we really won't get anywhere near this for a while, but nonetheless:

-- adjunctions: Data.Functor.Rep
class Distributive f => Representable f where
    type Rep f :: *
    tabulate :: (Rep f -> a) -> f a
    index :: f a -> Rep f -> a 

We'll find Representable to be the subject of future discussion, but I have not explored the relation deep enough to say anything of depth.

Kleisli arrows of outrageous fortune

Beyond that, there is the paper Kleisli arrows of outrageous fortune by Connor McBride (again) involving Atkey-style indexed / parameterized functor, which will be relevant if we wish to generalize from type-specific indices and paths, to a parametric / type argument index. However, in keeping with 'start simple', we'll get to that when we get to it.

recursion-schemes-ix

Finally there is already technically a library for indexed recursion schemes but it uses singletons and is a bit too abstracted for my taste - remember, we don't want to get lost in the madness, and I'm not even sure that it does everything I need. I'm looking for a solution that provides clarity and more compatibility with the way that existing indexed functor packages work, in order to aid in our exploration of this space.

Indexed functors and foldables

With examples of the existing ecosystem fresh in our minds, we are now going to define our own classes for indexing, based on what we just covered and also the opinions developed during use.

• Our core function will be of the form imap :: (i -> a -> b) -> f a -> f b.

• In keeping with our existing use of type families for Base, we will opt to also use type families for Index instead of functional dependencies.

• We will be providing separate classes for Indexed, IndexedFunctor, IndexedFoldable, and IndexedTraversable

Indexed and indexed

We start with the Index type, and its accompanying class, Indexed which provides the function indexed :: f a -> f (Index f, a), which tuples up content with its index.

type family Index (f :: * -> *)

class Indexed f where
    indexed :: f a -> f (Index f, a)
    default indexed :: (IndexedFunctor f) => f a -> f (Index f, a)
    indexed = imap (,)

All that indexed does is annotate an element with its index - this is rarely the function that we want to use, but it is good to have for the sake of a proper hierarchy.

Note that there is a default implementation for indexed, which relies on our next class, IndexedFunctor. We have opted however to keep the two classes separate, and use Indexed as a superclass for IndexedFunctor.

IndexedFunctor and imap

Our next class, IndexedFunctor, combines both Indexed and Functor to provide the function imap :: (Index f -> a -> b) -> f a -> f b. The difference between imap and fmap is that we now get access to the index of a value while we are mapping.

class (Indexed f, Functor f) => IndexedFunctor f where
    imap :: (Index f -> a -> b) -> f a -> f b
    imap f = fmap (uncurry f) . indexed

Note that imap also has a default implementation - and the default implementations of indexed and imap rely on each other. This means that we must actually implement at least one of them, preferably imap, for reasons that will be explained later.

IndexedFoldable and ifoldMap

Now, you may be asking, why have we declared Indexed and IndexedFunctor separately? It is because the next class, IndexedFoldable, does not rely on Functor. Instead, it combines both Indexed and Foldable to provide the function ifoldMap :: (Monoid m) => (Index f -> a -> m) -> f a -> m . Like imap, with ifoldMap we now get access to the index of a value while we are folding.

class (Indexed f, Foldable f) => IndexedFoldable f where
    ifoldMap :: (Monoid m) => (Index f -> a -> m) -> f a -> m 
    ifoldMap f = foldMap (uncurry f) . indexed

I do not think it is possible to define a default implementation of indexed in terms of ifoldMap (as we did with imap), even if we wanted - we would need fromList or some other way of constructing the specific type, which is not captured by Foldable.

In the name of preserving our immediate sanity, we have opted to leave defining ifoldr and other indexed foldable functions for later, as they are beyond the necessary scope of this already-overburdened article.

IndexedTraversable and itraverse

Finally, to complete the trio, we of course have IndexedTraversable. Just like Functor and Foldable, if something is both an IndexedFunctor and an IndexedFoldable, it should probably also be an IndexedTraversable (and vice versa), even though it only actually requires Indexed and Traversable constraints.

class (Indexed t, Traversable t) => IndexedTraversable t where
    itraverse :: Applicative f => (Index t -> a -> f b) -> t a -> f (t b) 
    itraverse f = traverse (uncurry f) . indexed

NOTE: The class constraints here should possibly be (IndexedFunctor t, IndexedFoldable t, Traversable t) instead - we're still figuring out exactly how weak / strong we want these connections to be.

Ditto on leaving imapM and friends undefined for now.

Notes on default implementations

Note that we can choose to implement indexed, and get imap, ifoldMap, and itraverse for free; however, it is strongly preferred that indexed use the default implemention from imap, and that we implement imap, ifoldMap, and itraverse, in order to only perform one map / traversal of the structure and fuse away the default indexed's inner fmap. We need this fusing not just for efficiency, but also out of concern for the need to avoid fetching the entire data structure to index-map it all at once - this will become more important later.

Time for a break

Go take a break, stretch your legs or something. You've earned it, having survived the theoretical and philosophical discussion. All of the stuff above, is more or less known, but we're about to cross into the unknown, so you'll want your energy.

Indexed recursives

With indexed functors out of the way, it seems now we should try and take the next logical step, and define... indexed recursives? Sure, lets take a stab at that and see what we get. For perspective, remember that the default implementation of imap was fmap (uncurry f) . indexed, so we can work off of that.

For our first attempt, we might be tempted to try and define indexed versions of hylo and friends:

icata :: (Recursive a, Indexed (Base a)) => (Base a (Index (Base a), b) -> b) -> a -> b
icata alg = cata (alg . indexed)

ihylo :: (Indexed f, Functor f) => (f (Index f, b) -> b) -> (a -> f a) -> a -> b
ihylo alg = hylo (alg . indexed)

However, this definition uses indexed rather than imap, which is preferred due to our pattern of extending hylo by adding new capabilities to fmap. We can fuse the indexed into the hylo by implementing it using imap instead of fmap, at the cost of the constraint now requiring IndexedFunctor:

icata :: (Recursive a, IndexedFunctor (Base a)) => (Base a (Index (Base a), b) -> b) -> a -> b
icata alg = ihylo alg project

ihylo :: IndexedFunctor f => (f (Index f, b) -> b) -> (a -> f a) -> a -> b
ihylo alg coalg = h where h = alg . imap (curry (second h)) . coalg

So we have a few functions that seem sensible - but if we take a closer look, and one finds that this lacks our desired symmetry.

Note that the type definition requires a tuple (Index f, b) rather than a curried function such as Index f -> f b -> b - and that the index is entirely absent on the ana / coalg side. Indeed, the notion of an index only matters on the cata / alg side - we could pass an index to the child but it does not matter because it must immediately discard it. Indeed, it seems there is no sensible iana that doesn't just drop them immediately, like this:

iana :: (Corecursive t, Indexed (Base t)) => (a -> Base t (Index (Base t), a)) -> a -> t
iana = hylo embed . fmap (fmap snd)

Something else, with a type definition like (Index (Base t) -> a -> Base t a)) -> Index (Base t) -> a -> t or (Index (Base t) -> a -> Base t (Index (Base t), a)) -> Index (Base t) -> a -> t hardly seems better. Why does it appear that having the index only matters when ascending back up, only after - but not while - we have descended recursively? If we look more closely at those horrid attempts to create a non-trivial iana, the answer is already given - ... -> Index (Base t) -> a -> t.

We would have to provide an index for the top-level - but there is none. An index is about a child's position within a parent, but a top level can have no index, being without a parent, and as we unfold, we must treat each child as a top-level - and thus the entire descent is without indexing. What we have here is not so much a golden thread telling us how to get back, but rather one telling us what the next steps forward could be - and it is only once we have traversed them that they collectively become a part of the way back.

That isn't to say that the icata and ihylo functions aren't useful, merely that they are in fact degenerate or trivial versions of the functions of what we seek, and that we have to keep working to derive what we want.

In particular, icata and ihylo can be used for simple catamorphic hashing of JSON based on its structure, and not just by hashing a JSON-encoded String, as you so often see in naive the crypto space. This can be used to de-duplicate, parallelize, diff, and patch a stream of on-demand JSON fragments, being the most simple variant of a series of functions which we will get into when this article series finishes with the foundations and begins focusing on the practical applications.

Nevertheless, it seems we have only half the story - we are missing something.

Indexed base functors

If we take the time to remember the steps that we took to promote functors to recursives, it gives us a clue as to what we are missing. Index is clearly a functoral concept, but that means it only operates over a single level of a recursive at a time. hylo differentiates itself from fmap by operating over multiple levels, so its indices must also do the same. Our indexed recursives really need to have recursive indices, made out of the indices of the base functors leading back to the top level - a path of sorts.

Pathed recursives

This really should have been obvious from the get-go, what with all of the Index (Base t) going on, but now we can get on with what we were really trying to define in the first place - pathed recursives.

In fact, lets define a few quick alias:

type Path (r :: *) = [Index (Base r)]

type PathedRecursive a = (Recursive a, IndexedFunctor (Base a))
type PathedCorecursive a = (Corecursive a, IndexedFunctor (Base a))

Note that while a functor has an Index, a recursive has a Path, made up of a sequence of base indices. An index and a path are separate but related concepts, because a path directs you along the internal structure of a recursive, while an index points all the way to a functor content slot. It helps to think of a path as potentially ending 'inside' of the data structure, while an index goes 'all the way through', ending 'at the edge or boundary' between the functor and its content. If the functor is itself recursive, then by necessity its indices will contain a path as part of its structure, in some sort of index-path - but that's getting ahead of ourselves.

We have also created the PathedRecursive and PathedCorecursive types by upgrading from a Functor (Base a) constraint (implicit in the Recursive constraint) to an IndexedFunctor (Base a) constraint.

We're defining these as type aliases for now, rather than as type families / classes, but we can always go back and change that - and we might actually need to later when we get into sourced paths, once we solidify things. For the moment, this suffices, so let us proceed to trying to define pathed hylo and friends again, with what we have just newly learned.

Pathed morphisms

Whereas before, we have i- functions to denote indexed-, here we will have p- functions, to denote pathed-, and we will start with pcata since we know it will be meaningful. But how do we promote icata to pcata if we don't even know what the type of pcata is yet?

pcata and pana

Well, what are the changes in our understanding? Well, for one, we want to keep track of the path of indices that we have encountered before and pass that in at every level, rather than the indices of children which we haven't encountered yet. And secondly, it should be compatible with an upgrade from fmap to imap - so vaguely it needs to be like h = alg . imap h . coalg, except we need to pass in a path parameter somewhere.

In other words, for pcata we're actually looking for an algorithm with the form path -> f b -> b, instead of f (index, a) -> a. Having the index inside of the functor (as in f (i, a) -> a) is entirely unnecessary, as we can combine the index into the path immediately before passing that along with the child to the next recursion - meaning that pcata itself also needs an initial path -> argument after the alg argument. Additionally, by symmetry we now have a sensible co-algorithm form for pana - path -> a -> f a - and with this form, the path affects the unfolding in a meaningful way!

Another thing that must be true of our desired set of functions is that, if we ignore the index / path information entirely, it should be the same as plain hylo and friend - that is, hylo alg coalg = phylo (const alg) (const coalg) undefined. This actually tells us enough to implement both pcata and pana in terms of phylo, even though we haven't defined phylo yet!

Thus, we can define pcata and pana as having the same type as cata and ana, but simply having added Path a -> to a few places, and also using const to let project and embed ignore this new parameter when appropriate.

-- cata ::     Recursive t => (          Base t a -> a) ->           t -> a
pcata :: PathedRecursive t => (Path t -> Base t a -> a) -> Path t -> t -> a
pcata alg  = phylo alg (const project)

-- ana ::     Corecursive t => (          a -> Base t a) ->           a -> t
pana :: PathedCorecursive t => (Path t -> a -> Base t a) -> Path t -> a -> t
pana coalg  = phylo (const embed) coalg

phylo

With that in place, we are free to define the type of phylo. We know it must be something similar to pana and pcata, but since we are back to the level of indexed functors we have slightly different constraints - IndexedFunctor f rather than PathedRecursive a or PathedCorecursive a - and so we need use [Index f] rather than Path (since Path is defined as Path r = [Index (Base r)]). Otherwise, we can clearly see our desired function now taking shape:

-- hylo ::      Functor f => (             f b -> b) -> (             a -> f a)              -> a -> b
phylo :: IndexedFunctor f => ([Index f] -> f b -> b) -> ([Index f] -> a -> f a) -> [Index f] -> a -> b
phylo = _

However, the question is now implementing phylo. Compared to hylo, phylo and its alg and coalg each all require an additional parameter. Rather than h = alg . fmap h . coalg, we need something like h p = alg p . imap h p . coalg p, except that clearly doesn't work because imap doesn't take a path argument, and we want to join it with the index anyway which this doesn't do.

We need to join the path p with the index i inside of the imap's argument, like imap (h p) instead of imap h p. A little bit of playing around to join index onto a path, and we get something sensible.

phylo :: IndexedFunctor f => ([Index f] -> f b -> b) -> ([Index f] -> a -> f a) -> [Index f] -> a -> b
phylo   alg coalg = h where h p = alg p . imap (\ i -> h (i:p)) . coalg p
-- hylo alg coalg = h where h   = alg   . fmap         h        . alg

This is actually what we've been after - we have successfully defined a pathed hylomorphism - something that, while we are traversing it, knows where we came from. This is pretty sweet! It is as powerful as hylo, but we also have a nice golden thread to help find our way back out of the labyrinth.

Doing something like using Cofree to annotate a data structure with its path is now trivial!

annotatePaths :: Json -> Cofree JsonF JsonPath
annotatePaths = pcata (:<) []

NOTE: It is worth mentioning that paths are formed in reverse, with the most recent index on top and root at te end - eg, /path/to/file.md yields ["file.md", "to", "path", "/"].

In general, these functions do everything that hylo does, with the addition of its path being available to it - so these are morphisms that know where they are!. This makes it possible to untie a structure, breaking it into shards and fragments that we can collect in a list or dictionary.

type Frag r = Base r (Path r)
type Shard r = (Path r, Frag r) -- Or CofreeF (Base r) (Path r) (Path r)

shatterList :: (Recursive r, IndexedFunctor (Base r), Foldable (Base r)) => r -> [Shard r]
shatterList r = snd $ pcata shatter [] r where
    -- shatter :: Path r -> Base r (Path r, [Shard r]) -> (Path r, [Shard r])
    shatter p fs = (p, (p, fmap fst fs) : concatMap snd fs)

shatterMap :: (Recursive r, IndexedFunctor (Base r), Foldable (Base r)) => r -> Map (Path r) (Frag r)
shatterMap = Map.fromList . shatterList

Reconstituting the original object is trivial, and we can imagine this being useful for turning recursive objects into streams of fragments, allowing you to avoid sending megabytes of of JSON when a few kilobytes would do.

Note that pathed morphisms are also very useful when you want to differentiate identical values that differ only by their position within a data structure. Take for instance the following JSON:

{
    "account" : {
        "balance": 500
    },
    "address" : {
        "streetno" : 500
    }
}

Note that the values of account.balance and address.streetno are both 500 - but they are in a sense different 500's. You might use types to differentiate a bank balance from a street number, but then what if you have two bank accounts? Distinguishing by type is no longer enough. You see, the location of data can be just as important as the type of the data (in fact these notions can be related more strongly if we wish).

Lets say we were cryptographically hashing this data. With simple catamorphic hashing, we might accidentally reveal that the bank account and street number are equivalent, and this is of course very bad. This would happen because we would start at the bottom, and we would see 500 as a base case on two separate occasions, hash it individually twice, and get the same hash value for each both times. This is because when hashing from the bottom up, we of course don't include any of the 'up', and so as far as those two 'different' 500 values go, they are exactly the same. hash(500) is the same everywhere.

Note that this property isn't bad by itself - it turns out that this property enables deduplication, at the cost of revealing similarities between data because thats what deduplication is. So this property can be valuable, especially for public data.

However, with pathed catamorphic hashing, we have a chance to include the path in the hashing. Instead, our base cases for hashing would be, not hash(500) and hash(500), but rather hash(account.balance.500) and hash(address.streetno.500). The inclusion of the path differentiates the two, and makes the resulting hash of each value unique to not just its structural value, but also its location within a larger structure. With this, revealing that account.balance = 500 does not reveal that address.streetno = 500.

So, sometimes location matters, and when it does, 'morphisms that know where they are' are especially useful.

Monadic pathed morphisms

We may now go about defining monadic variants, if we like. Anything that a pathed morphism can do, we can now do monadically. They are of course especially useful if we need to perform IO while traversing our recursive structure. Otherwise, everything we just said for pathed morphisms, just slap a monad on it.

pcataM

pcataM
    :: (PathedRecursive a, IndexedTraversable (Base a), Monad m)
    => (Path a -> Base a b -> m b)
    -> Path a -> a -> m b
pcataM alg  = phyloM alg (const projectM)

We could use pcataM here to simply print every path of a JSON object, from the bottom up while folding:

printJsonPaths :: JsonPath -> Json -> IO ()
printJsonPaths = pcataM (const . print)

panaM

panaM
    :: (PathedCorecursive b, IndexedTraversable (Base b), Monad m)
    => (Path b -> a -> m (Base b a))
    -> Path b -> a -> m b
panaM coalg  = phyloM (const embedM) coalg

We could use panaM to recursively fetch fragments of a JSON object in a way that combines the path with a digest.

fetchJson :: (JsonPath -> Digest -> IO (JsonF Digest)) -> JsonPath -> Digest -> IO Json
fetchJson = panaM

phyloM

phyloM
    :: (Monad m, IndexedTraversable t)
    => ([Index t] -> t b -> m b)
    -> ([Index t] -> a -> m (t a))
    -> [Index t] -> a -> m b
phyloM alg coalg = h where h p = alg p <=< itraverse (\ i -> h (i:p)) <=< coalg p

phyloM is quite exciting because can use the path in the alg and coalg to perform IO while both unfolding (reading the next chunk of data from a file or network) and folding (writing updated chunks out). Given the amount of IO involving relative paths, this function can come in quite handy if you build yourself a FileTree / FileTreeF data structure.

data FileTree = File ByteString | Directory (Map FileName FileTree)
data FileTreeF a = ...

cloneFilesToDisk
    :: (FilePath -> FileTreeF () -> IO ())              -- Write to disk
    -> (FilePath -> Digest -> IO (FileTreeF Digest))    -- Fetch file tree fragment
    -> FilePath -> Digest -> IO ()
cloneFilesToDisk = phyloM

Special pathed morphisms

I suppose we should define p- equivalents for iso and trans, and their monadic -M variants too.

Unsurprisingly, both piso and pisoM are trivial, as ignoring the path argument just makes them equivalent to iso and isoM. However, ptrans and ptransM are not trivial - because the path argument makes it to the natural transformation argument, it is able to have an effect on the resulting structure.

piso

piso :: (Iso s t, IndexedFunctor (Base s)) => Path s -> s -> t
piso   = phylo (const embed) (const project)
-- iso = hylo  (      embed( (      project)

This function is trivial, and equivalent to const iso.

ptrans

ptrans
    :: (PathedRecursive s, Corecursive t)
    => (Path s -> forall a. Base s a -> Base t a)
    -> Path s -> s -> t
-- trans f = hylo  (       embed . f  ) (      project)
ptrans   f = phylo (\ p -> embed . f p) (const project)

This function is non-trivial, because the path may affect the transformation.

pisoM

pisoM :: (Monad m, Iso s t, IndexedTraversable (Base s)) => Path s -> s -> m t
pisoM = phyloM (const embedM) (const projectM)

This function is trivial, and equivalent to const isoM.

ptransM

ptransM
    :: (Monad m, PathedRecursive s, Corecursive t, IndexedTraversable (Base s))
    => (Path s -> forall a. Base s a -> m (Base t a))
    -> Path s -> s -> m t
ptransM f = phyloM (\ p -> embedM <=< f p) (const projectM)

This function is non-trivial, because the path may affect the transformation.

Biindexed bifunctors and bifoldables

Okay, so that wasn't too bad. But this is birecursion-schemes, and so you knew it was coming - biindexed bifunctors. Luckily, this is going to be very easy, because we did all of the hard work to get pathed recursion schemes, we've just got to combine the methods of lifting from recursion to birecursion, with the method of lifting to indexed / pathed recursion. That means we've got two indices now. Oh no! Anyway...

First, we define our index type families.

type family FirstIndex (f :: * -> * -> *) :: *
type family SecondIndex (f :: * -> * -> *) :: *
type Biindex f = Either (FirstIndex f) (SecondIndex f)

Note that forall a . Index (f a) == SecondIndex f since forall a . Functor (f a) => Bifunctor f (assuming the bifunctor-superclass proposal, which we haven't quite yet applied)

What's this Biindex type? Well, since birecursion means that we recurse twice, and so when we are recursing, the resulting path may contain a mix of FirstIndex and SecondIndex depending on whether the recursion went through the First slot or the Second slot at a given level.

Trust me, it'll make more sense as we go on. On with the show!

Biindexed and biindexed

If indexed is just imap (,), then biindexed is just ibimap (,) (,).

class Biindexed f where
    biindexed :: f a b -> f (FirstIndex f, a) (SecondIndex f, b)
    default biindexed :: (BiindexedBifunctor f) => f a b -> f (FirstIndex f, a) (SecondIndex f, b)
    biindexed = ibimap (,) (,)

Again, we have a default implementation in terms of ibimap, but the same thoughts as before regarding fusing still apply.

BiindexedBifunctor and ibimap

If imap f = fmap (uncurry f) . indexed, then ibimap f g = bimap (uncurry f) (uncurry g) . biindexed

class (Biindexed f, Bifunctor f) => BiindexedBifunctor f where
    ibimap :: (FirstIndex f -> a -> b) -> (SecondIndex f -> c -> d) -> f a c -> f b d
    ibimap f g = bimap (uncurry f) (uncurry g) . biindexed

BiindexedBifoldable and ibifoldMap

Now we really are starting to harvest the result of our efforts earlier. We upgrade foldMap (uncurry f) . indexed to bifoldMap (uncurry f) (uncurry g) . biindexed - because we took the time to define IndexedFoldable, we can define BiindexedBifoldable just as easily!

class (Biindexed f, Bifoldable f) => BiindexedBifoldable f where
    ibifoldMap :: (Monoid m) => (FirstIndex f -> a -> m) -> (SecondIndex f -> b -> m) -> f a b -> m
    ibifoldMap f g = bifoldMap (uncurry f) (uncurry g) . biindexed

Our types are beginning to grow unseasonably large, however.

BiindexedBitraversable and ibitraverse

BiindexedBitraversable is again just so much more purely mechanical lifting.

class (Biindexed t, Bitraversable t) => BiindexedBitraversable t where
    ibitraverse
        :: Applicative f
        => (FirstIndex t -> a -> f c)
        -> (SecondIndex t -> b -> f d)
        -> t a b -> f (t c d)
    ibitraverse f g = bitraverse (uncurry f) (uncurry g) . biindexed

As far as I can tell, while indexed-traversable as a package exists, biindexed-bitraversable does not, and we are firmly in novel territory here. However, these are necesary for... are you ready for it? Bipathed birecursion!

Biindexed birecursives

This time, we're going to skip the i- variants entirely, and get straight to the p- pathed variants.

Biindexed bibase bifunctors

Since before we had indexed base functors, now we have biindexed bibase bifunctors. Oh dear, what terribly babbling terminology.

Bipathed birecursives

Just as before, we define our types, this time lifted from both recursive to birecursive and indexed to biindexed.

type Bipath (r :: *) = [Biindex (Bibase r)]

--   PathedRecursive     t = (  Recursive t, IndexedFunctor     (Base t))
type BipathedBirecursive t = (Birecursive t, BiindexedBifunctor (Bibase t))
type BipathedCobirecursive t = (Cobirecursive t, BiindexedBifunctor (Bibase t))

Our golden thread still shows us our way back, however - and it tells us which doors we passed through on the way - the first recursion or the second.

Again, these are just type aliases for now.

Bipathed bimorphisms

NOTE: I am unsure of whether our use of the term 'bimorphism' meets the definition a 'bimorphism' as "A morphism which is both a monomorphism and an epimorphism.". It may clash, or it may turn out to be equivalent, if we squint at it hard enough. I haven't investigated yet.

We're going to get through these bimorphisms real quick, because effectively all that they do is take imap / itraverse and lift to ibimap / ibitraverse, Path to Bipath, etc. Lots of things just get bi- shoved in front. Anything that isnt straightforward will get called out.

pbicata

Just pcata with bi- plastered everywhere.

pbicata                                 --  pcata
    :: (BipathedBirecursive t)          --      :: PathedRecursive t
    => (Bipath t -> Bibase t a a -> a)  --      => (Path t -> Base t a -> a)
    -> Bipath t -> t -> a               --      -> Path t -> t -> a
pbicata alg = pbihylo alg (const biproject)
-- pcata alg = phylo  alg (const   project)

Note that Bibase t a a takes an extra a argument compared to Base t a, because it has a base bifunctor.

pbiana

Just pana with bi- plastered everywhere.

pbiana                                  --  pana
    :: (BipathedCobirecursive t)        --      :: PathedCorecursive t
    => (Bipath t -> a -> Bibase t a a)  --      => (Path t -> a -> Base t a)
    -> Bipath t -> a -> t               --      -> Path t -> a -> t
pbiana coalg = pbihylo (const biembed) coalg
-- pana coalg = phylo  (const   embed) coalg

pbihylo

Remember that Biindex f = Either (FirstIndex f) (SecondIndex f)? This is why!

pbihylo                             --  phylo
    :: (BiindexedBifunctor f)       --      :: IndexedFunctor f 
    => ([Biindex f] -> f b b -> b)  --      => ([Index f] -> f b -> b)
    -> ([Biindex f] -> a -> f a a)  --      -> ([Index f] -> a -> f a)
    -> [Biindex f] -> a -> b        --      -> [Index f] -> a -> b
pbihylo alg coalg = h where
    h p = alg p . ibimap (\ i -> h (Left i : p)) (\ j -> h (Right j : p)) . coalg p
-- phylo
--      = alg p . imap                           (\ i -> h (      i : p))       . coalg p

With fmap to bimap, we just need to pop h into both slots, but with imap to ibimap, we have to deal with that FirstIndex is not necessarily the same as SecondIndex. As a result, instead of just copying (\ i -> h (i : p)) into both recursion slots, we have to differentiate by using Left and Right, as Bipath uses Biindex which contains an Either. Otherwise, we're just doing the same path-combining as with phylo, using Left i : p and Right j : p instead of just i : p.

Can you imagine this without the type-aliases? And yet, we can still clearly see the original hylo hidden inside.

Monadic bipathed bimorphisms

These just lift what just did, to also be monadic. So, ibimap becomes ibitraverse, . becomes <=<, and we add a few -Ms in places. Otherwise, noting of note, just rote.

pbicataM

pbicataM
    :: (Monad m, Birecursive t, BiindexedBifunctor (Bibase t), BiindexedBitraversable (Bibase t))
    => (Bipath t -> Bibase t a a -> m a)
    -> Bipath t -> t -> m a
pbicataM alg = pbihyloM alg (const biprojectM)

pbianaM

pbianaM
    :: (Monad m, Cobirecursive t, BiindexedBifunctor (Bibase t), BiindexedBitraversable (Bibase t))
    => (Bipath t -> a -> m (Bibase t a a))
    -> Bipath t -> a -> m t
pbianaM coalg = pbihyloM (const biembedM) coalg

pbihyloM

pbihyloM
    :: (Monad m, BiindexedBifunctor f, BiindexedBitraversable f)
    => ([Biindex f] -> f b b -> m b)
    -> ([Biindex f] -> a -> m (f a a))
    -> [Biindex f] -> a -> m b
pbihyloM alg coalg = h where
    h p = alg p <=< ibitraverse (\ i -> h (Left i : p)) (\ j -> h (Right j : p)) <=< coalg p

Special bipathed bimorphisms

For completeness, of course.

pbiiso

Trivially const biiso.

pbiiso :: (BipathedBirecursive s, Biiso s t) => Bipath s -> s -> t
pbiiso = pbihylo (const biembed) (const biproject)

pbitrans

Not trivial.

pbitrans
    :: (BipathedBirecursive s, Cobirecursive t)
    => (Bipath s -> forall a b. Bibase s a b -> Bibase t a b) -> Bipath s -> s -> t
pbitrans f = pbihylo (\ p -> biembed . f p) (const biproject)

pbiisoM

Trivially const biisoM.

pbiisoM
    :: (Monad m, BipathedBirecursive s, Biiso s t, BiindexedBitraversable (Bibase s))
    => Bipath s -> s -> m t
pbiisoM = pbihyloM (const biembedM) (const biprojectM)

pbitransM

Not trivial.

pbitransM
    :: (Monad m, BipathedBirecursive s, Cobirecursive t, BiindexedBitraversable (Bibase s))
    => (Bipath s -> forall a b. Bibase s a b -> m (Bibase t a b))
    -> Bipath s -> s -> m t
pbitransM f = pbihyloM (\ p -> biembedM <=< f p) (const biprojectM)

Take another break.

You've just finished getting through not just pathed recursion, but bipathed birecursion! The end of this is in sight, after this, we just have to define what indexing and pathing mean for recursive functors.

Diindexed difunctors and difoldables, diindexed dibase bifunctors

In comparison to Indexed and Pathed, I have not yet created a Diindexed class, nor are there DiindexedDifunctor or DiindexedDifoldable or DiindexedDitraversable classes. You see, a Difunctor is just a Functor and a Recursive, and so it already has an Index from Functor and a Path from Recursive. Its base functor is a base bifunctor, and so Biindexed, BiindexedBifunctor, BiindexedBifoldable, and BiindexedBitraversable are already sufficient.

Dipathed direcursives

At last we arrive here - the summit of an exhausting journey, but also a fundamental building block, the first step in a much larger journey that I wish to take you on. Be proud of reaching this point with me, as it prepares you for things yet to come.

If we have indexed functors and biindexed bifunctors, and pathed recursives and bipathed birecursives, what do we get for difunctors aka recursive functors? Well, they have both an index, being a functor, as well as a path, being a recursive at the same time. In fact, remember that their dibase bifunctor is a base bifunctor that is also a functor for the fixed / recursive functor's content, instead of being a bibase bifunctor that recurses in both slots.

From this we know that a recursive functor's index must be made up of its base bifunctor's (bi)indices. Whereas for bipathed birecursion, our golden thread back could weave back and forth through both base bifunctor slots, now it threads through one base slot repeatedly - the path made up of one slot's indices, pointing repeatedly at more recursive structure - before finally weaving across through the other base slot once to finally point at a functor content element - the tip of the path, a house number on a street address, the last leg of a journey.

NOTE: Why would we bother with this concept? Well, it is in order to chain recursion - our goal is to stack / transform recursive functors, and that means we must do the same with their indices. If we have a compound type f (g (h a)), then we have a compound path (Index h, (Index g, (Index f, ()))), and if they are recursive, the paths must link up too, giving us ( (FirstIndex h, [SecondIndex h]), ((FirstIndex g, [SecondIndex g]), ((FirstIndex f, [SecondIndex f]), ()))). It is easier and clearer however to define it as Way (SecondIndex h) (FirstIndex h, Way (SecondIndex g) ...) and embed inner paths at the end of outer paths.

Let us define some helpful type aliases.

type Diindex (r :: * -> *) = (FirstIndex (Dibase r), [SecondIndex (Dibase r)]) -- NOTE: Should be ~ Index r
type Dipath (r :: * -> *) = [SecondIndex (Dibase r)]                           -- NOTE: Should be ~ Path (r a)

-- NOTE: These constraints often end up adding little, due to incomplete hierarchy
--  Eg, `Direcursive t, BiindexedBitraversable (Dibase t)` is sufficient as compared
--  to `PathedDirecursive t, Bitraversable (Dibase t)` which isn't.
type DipathedDirecursive t = (Direcursive t, BiindexedBifunctor (Dibase t))
type DipathedCodirecursive t = (Codirecursive t, BiindexedBifunctor (Dibase t))

Note that forall a . Path (t a) ~ Dipath t since forall a . Index (t a) ~ SecondIndex t, and that Diindex t ~ Index t too. Also note that (FirstIndex f, [SecondIndex f]) is just Way (SecondIndex f) (FirstIndex f) in reverse - it makes sense because Diindex is just Index, and Index is Way as we discovered early on. At the time we haven't completely solidified this hierarchy, but when we do, these equivalences should be more explicit, and should be enforced similarly to the bifunctor-superclass proposal - it is related after all.

So Dipath is just Path in bifunctor clothing, and Diindex is just Index because a recursive functor is already a functor - but what exactly is Diindex? Whereas Index is ignorant of what lay beneath, Diindex is aware of the internal structure of a recursive functor - it knows that it must take a Path made up of SecondIndex, and cap it off at the end with a FirstIndex, in order to make the Index.

For many recursive functors, there exists only one logical content slot per base constructor - in that case the FirstIndex is equivalent to (), and it can be ignored entirely. For these functors, Dipath f ~ Diindex f, and Index f ~ Path (f a).

data Identity a = Identity a
data List a = Nil | Cons a (List a)
data Tree a = Tip | Tree a (List a) (List a)
data BinTree  a = Leaf a | Node (BinTree a) (BinTree a)

However, for others with multiple content slots per case, FirstIndex actually requires some information to be stored.

--                     v FirstIndex  v SecondIndex
data BilistIx = Bizero Bool | Bisucc () BilistIx    -- Or: Way () Bool
data Bilist a = Binil | Bicons a a (Bilist a)

Bilist requires that SecondIndex BilistF ~ Unit because there is only one possible successor, and it requires that FirstIndex BilistF ~ Bool because each successor skips two content slots, and so the Diindex of a Bilist effectively counts by units of twos until it reaches the end, then uses the Bool to pick one of the two slots.

It is important to understand how sometimes FirstIndex (often) or SecondIndex (rarely) can be implicitly ignored sometimes - it will help you make sense of why sometimes a path is an index, and sometimes it is not.

Dipathed dimorphisms

NOTE: Here we have made up the term 'dimorphism' wholesale, as a cursory search of "category theory" with "dimorphism" yielded nothing of value.

Again, we're going to skip the i- variants entirely, and get straight to it.

pdicata

This is better explained through pdihylo, but we'll define it first.

pdicata
    :: (DipathedDirecursive f)
    => (Diindex f -> a -> b)
    -> (Dipath f -> Dibase f b d -> d)
    -> Dipath f -> f a -> d
pdicata f alg = pdihylo f alg (const diproject)
-- pcata  alg = phylo     alg (const   project)

Also, note that enforcing Functor, Recursive => Direcursive would allow for enforcing (Index f ~ Diindex f, forall a . Path (f a) ~ Dipath f) implicitly, allowing us to define pdicata using Index and Path. See here with those constraints made explicit:

pdicata
    :: (DipathedDirecursive f, Index f ~ Diindex f, Path (f a) ~ Dipath f)
    => (Index f -> a -> b)
    -> (Path (f a) -> Dibase f b d -> d)
    -> Path (f a) -> f a -> d
pdicata f alg = pdihylo f alg (const diproject)
-- pcata  alg = phylo     alg (const   project)

This could be the preferable way of defining this, once we tighten the hierarchy.

pdiana

Ditto everything said for pdicata.

pdiana
    :: (DipathedCodirecursive f)
    => (Diindex f -> a -> b)
    -> (Dipath f -> c -> Dibase f a c)
    -> Dipath f -> c -> f b
pdiana f coalg = pdihylo f (const diembed) coalg
-- pana  coalg = phylo     (const   embed) coalg

pdihylo

If dihylo is hylo plus fmap, then pdihylo is phylo plus imap. This function gives you the power to do one thing going down the branches, a second thing to map the leaves, and a third thing coming back up - all with an index or path to tell you where you are.

pdihylo 
    :: BiindexedBifunctor f
    => ((FirstIndex f, [SecondIndex f]) -> a -> b)
    -> ([SecondIndex f] -> f b d -> d)
    -> ([SecondIndex f] -> c -> f a c)
    -> [SecondIndex f] -> c -> d
pdihylo f alg coalg = h where
    h p = alg p . ibimap (\ i -> f (     i , p)) (\ j -> h (      j : p)) . coalg p
-- phylo
--      = alg p . imap                           (\ i -> h (      i : p)) . coalg p
-- pbihylo
--      = alg p . ibimap (\ i -> h (Left i : p)) (\ j -> h (Right j : p)) . coalg p

Note the correlations and differences with phylo and pbihylo. We have upgraded to a base bifunctor, but because this is direcursion, we aren't upgrading to use Left and Right. Instead, we still copy (\ i -> f (i : p)) into both ibimap slots, but rather than adding Left and Right, we just replace the first slot's : with , to get (\ i -> f (i , p)) , while the second slot gets to stay \ i -> h (i : p) (well, we turned the i to a j but thats purely nomenclative).

Placing the FirstIndex to the left in (FirstIndex f, [SecondIndex f]) plays well with the understanding that the path is reversed, as by reading it from right to left, the FirstIndex forms the tip. /path/to/file.json becomes (file.json, ["to/", "path/", "/"]) (if file-names were considered as FirstIndex to directory-names as SecondIndex).

Note that for recursive functors such that FirstIndex ~ (), then Index f ~ forall a . Path (f a).

What can we do with pdihylo? Well, earlier we defined data FileTree = File | Directory (Map Name FileTree) as an example for phylo, but we could actually free up the filetype and turn FileTree into a recursive functor.

data FileTree a = File a | Directory (Map Name FileTree)
data FileTreeF a r = ...

One can imagine not just drilling down through the filetree, through the content of the file as well, in a single operation, such as FileTree Json with a combined filetree-json-path being made available to every json fragment - or breaking up a filetree-of-json into (filetree-or-json)-fragments, a deepening of the shard shattering that we performed with phylo because everything that we mentioned for phylo carries over to pdihylo.

It is possible to build a di- variant of the earlier shatterList and shatterMap functions, one which continues with shattering the functor content - making it possible to recursively shatter nested recursive functors and gather up all of the pieces. This requires a bit more finesse, so this definition is left for another time. Feel free to try and derive it yourself, however.

Applicative dipathed dimorphisms

Unlike Recursive and Birecursive, with di- we have access to non-trivial applicative variants. These of course are created by using ibitraverse like -M variants, but with . instead of <=<, and using fmap at the front.

Note that as with dihylo and friends, the applicative nature only occurs in the mapping transformation function, and not in the alg or coalg function - the Applicative nature is ignorant of the recursive nature just as much as Functor is. Compare (forall a . Recursive (f a), Functor f) => Difunctor f which understand that it is recursive, and can be broken up into (di)base functors, and so a recursive applicative might be broken up into (di)base applicatives. Concepts like diapplicative or even dimonad (recursive applicatives and monads) are definitely worth looking further into, to explore how the applicative or monadic nature as a whole is constructed from the fragments.

pdicataA

pdicataA
    :: (Applicative f, DipathedDirecursive t, BiindexedBitraversable (Dibase t))
    => (Diindex t -> a -> f b)
    -> (Dipath t -> Dibase t b c -> c)
    -> Dipath t -> t a -> f c
pdicataA f alg = pdihyloA f alg (const diproject)

pdianaA

pdianaA
    :: (Applicative f, DipathedCodirecursive t, BiindexedBitraversable (Dibase t))
    => (Diindex t -> a -> f b)
    -> (Dipath t -> c -> Dibase t a c)
    -> Dipath t -> c -> f (t b)
pdianaA f coalg = pdihyloA f (const diembed) coalg

pdihyloA

pdihyloA
    :: (Applicative f, BiindexedBitraversable t)
    => ((FirstIndex t, [SecondIndex t]) -> a -> f b)
    -> ([SecondIndex t] -> t b d -> d)
    -> ([SecondIndex t] -> c -> t a c)
    -> [SecondIndex t] -> c -> f d
pdihyloA f alg coalg = h where
    h p = fmap (alg p) . ibitraverse (\ i -> f (i,p)) (\ j -> h (j : p)) . coalg p

A minor correction about -A variants

It is worth mentioning, I was in error earlier when I stated that there was no applicative variants for mono- and bi- recursion. This of course is not strictly true, and it turns out that an applicative form is possible if we apply the fmap trick that we used in dihyloA, which is to promote fmap to traverse, while also wrapping alg with fmap before composition.

hyloA :: (Traversable t, Applicative f) => (t b -> b) -> (a -> t a) -> a -> f b
hyloA alg coalg = h where h = fmap alg . traverse h . coalg
-- hylo for comparison:            alg . fmap     h . coalg

It is pretty trivial though - f doesn't get used anywhere except the very end, unlike dihyloA. I would expect cataA* and anaA to be just as trivial. The di- variants are non-trivial even without indexing, because the applicative f does get used in the mapping transformation, which hyloA lacks.

However, the addition of indexing to the mix may make it such that phyloA and similar become non-trivial given that there is now a path with a chance to affect things. It may be worth revisiting in the future.

NOTE: * Not the same as cataA in recursion-schemes, which is not of the form (Base t a -> f a) -> t -> f a) but rather (Base t (f a) -> f a) -> t -> f a .

Monadic dipathed dimorphisms

If you get dipathed dimorphisms, and monadic morphisms, you'll get these.

pdicataM

pdicataM
    :: (Monad m, DipathedDirecursive f, BiindexedBitraversable (Dibase f))
    => (Diindex f -> a -> m b)
    -> (Dipath f -> Dibase f b d -> m d)
    -> Dipath f -> f a -> m d
pdicataM f alg  = pdihyloM f alg (const diprojectM)

pdianaM

pdianaM 
    :: (Monad m, DipathedCodirecursive f, BiindexedBitraversable (Dibase f))
    => (Diindex f -> a -> m b)
    -> (Dipath f -> c -> m (Dibase f a c))
    -> Dipath f -> c -> m (f b)
pdianaM f coalg  = pdihyloM f (const diembedM) coalg

pdihyloM

pdihyloM
    :: (Monad m, BiindexedBitraversable f)
    => ((FirstIndex f, [SecondIndex f]) -> a -> m b)
    -> ([SecondIndex f] -> f b d -> m d)
    -> ([SecondIndex f] -> c -> m (f a c))
    -> [SecondIndex f] -> c -> m d
pdihyloM f alg coalg = h where
    h p = alg p <=< ibitraverse (\ i -> f (i,p)) (\ j -> h (j : p)) <=< coalg p

An elegant weapon for a more civilized age.

Special dipathed dimorphisms

With recursion and birecursion, we found that some of our 'special' morphisms were trivial - variants of iso ended up not using the path at all.

This is not true for the special dipathed morphisms - none of them are trivial due to the use of the index / path in the f mapping transformation argument, and so the path argument may always affect the result. This makes them all worth defining - and we will discover something very interesting.

pdiiso

If you recall from the initial birecursion article, diiso lifts iso :: s -> t to a functor and adds a mapping argument (a -> b) -> s a -> t b. Extending it to be pathed is by now routine.

pdiiso
    :: (Diiso s t, BiindexedBifunctor (Dibase s))
    => (Diindex s -> a -> b)
    -> Dipath s -> s a -> t b
pdiiso f = pdihylo f (const diembed) (const diproject)

pditrans

pditrans
    :: (DipathedDirecursive s, Codirecursive t)
    => (Diindex s -> a -> b)
    -> (forall c . Dipath s -> Dibase s b c -> Dibase t b c)
    -> Dipath s -> s a -> t b
pditrans f g = pdihylo f (\ p -> diembed . g p) (const diproject)

pdiisoA

pdiisoA
    :: (Applicative f, Diiso s t, BiindexedBitraversable (Dibase s))
    => (Diindex s -> a -> f b)
    -> Dipath s -> s a -> f (t b)
pdiisoA f = pdihyloA f (const diembed) (const diproject)

pditransA

pditransA
    :: (Applicative f, DipathedDirecursive s, Codirecursive t, BiindexedBitraversable (Dibase s))
    => (Diindex s -> a -> f b)
    -> (forall c . Dipath s -> Dibase s b c -> Dibase t b c)
    -> Dipath s -> s a -> f (t b)
pditransA f g = pdihyloA f (\ p -> diembed . g p) (const diproject)

pdiisoM

pdiisoM
    :: (Monad m, Diiso s t, BiindexedBitraversable (Dibase s))
    => (Diindex s -> a -> m b)
    -> Dipath s -> s a -> m (t b)
pdiisoM f = pdihyloM f (const diembedM) (const diprojectM)

pditransM

pditransM
    :: (Monad m, DipathedDirecursive s, Codirecursive t, BiindexedBitraversable (Dibase s))
    => (Diindex s -> a -> m b)
    -> (forall c . Dipath s -> Dibase s b c -> m (Dibase t b c))
    -> Dipath s -> s a -> m (t b)
pditransM f g = pdihyloM f (\ p -> diembedM <=< g p) (const diprojectM)

Conclusion

As hard as it is to write about, it is even more difficult to end the writing - but end we must. We have covered enough ground for the day, we went deep into the labyrinth, and now it is time to come back out having discovered some wild things (shatterList and shatterMap especially). As we leave the labyrinth, winding up our golden thread, we arrive back where we started - the origin of our journey. It is time to make camp, and rest by the fire.

We started with asking a few questions, and it is fitting that we will end with answering one accordingly.

The profunctoral perspective

Whatever happened to the profunctoral perspective? I did say that I would get around to it, but we will need to go back to a few functions and give them a closer examination first.

I would now like to remind you of something that we discovered about diiso in the prior article - by restricting s ~ t, we found out that fmap = diiso. Therefore, we ask, what do we get if we restrict pdiiso the same way (and crush down types for readability since Diindex ~ Index and Dipath ~ Path)?

pdiiso_fmap
    :: (DipathedDirecursive f, DipathedCodirecursive f)
    => (Index f -> a -> b)
    -> Path f -> f a -> f b
pdiiso_fmap f = pdihylo f (const diembed) (const diproject)

If you were to say imap, you'd be wrong. Although , the resulting function has type (Index f -> a -> b) -> Path f -> f a -> f b - it has that additional Path f -> argument compared to imap, and so imap f = pdiiso f [].

On the other hand, if you were to say pmap (as a sort of pathed map) you'd be wrong too, because the mapping transformation function f takes an Index f and not a Path f - it is only if FirstIndex (Dibase f) ~ () (meaning the final constructor has a singular functor content slot) that Index f ~ ((), Path f) such that we get Index f ~ Path f by dropping the irrelevant ().

If it is neither imap nor pmap, it is instead both - it is an indexed, pathed map. We've got to remember that it isn't just fmap = diiso, it is recursive fmap = diiso, so it expresses both the functor nature and the recursive nature.

More importantly, it performed some type-changing operation on the path, which sounds like something we've been looking for. At the very end, it goes from Path to Index - but we did that. We did that when we implemented pdihylo. Has our profunctoral indices been hiding right under our noses the entire time?

Lets take a look! phylo concatenates indices Index f into a path [Index f], changing the type. pbihylo concatenates two types of indices FirstIndex f and SecondIndex f into a path of both [Either (SecondIndex f) (FirstIndex f)] - again changing the type. Finally, pdihylo concatenates one type of indices SecondIndex f into a path [SecondIndex f] (changing type once), before capping it with another index FirstIndex f to turn it into an index path (FirstIndex f, [SecondIndex f]) (changing type a second time).

How did we do that?

phylo alg coalg = h where
    h p = alg p . imap (\ i -> h (i : p)) . coalg p
    
pbihylo alg coalg = h where
    h p = alg p . ibimap (\ i -> h (Left i : p)) (\ j -> h (Right j : p)) . coalg p
    
pdihylo f alg coalg = h where
    h p = alg p . ibimap (\ i -> f (i , p)) (\ j -> h (j : p)) . coalg p

Can we abstract this? All we're doing is imap / ibimap with almost the exact same logic - in fact, we can zoom in on the centers of these functions, and pluck out their arguments to see how they are almost identical.

(\ i -> h (i       : p))    -- phylo
(\ i -> h (Left i  : p))    -- bihylo first
(\ j -> h (Right j : p))    -- bihylo second
(\ i -> f (i       , p))    -- dihylo first 
(\ j -> h (j       : p))    -- dihylo second

Really, these are all variations of the same form - we're performing a cons-like operation with the index and path, and we can extract the , and : arguments to get the generalized function:

(\ cons i -> h (i `cons` p))

With this, we can make a slightly different version of imap and ibimap, which we will call imapWith / ibimapWith:

imapWith
    :: (IndexedFunctor f)
    => (Index f -> path -> indexpath)           -- Cons
    -> (indexpath -> a -> b)
    -> path                                     -- Nil
    -> f a -> f b
imapWith cons f p = imap (\ i -> f (cons i p))

ibimapWith
    :: (BiindexedBifunctor f)
    => (FirstIndex f -> path -> findexpath)     -- Left Cons
    -> (SecondIndex f -> path -> sindexpath)    -- Right Cons
    -> (findexpath -> a -> b)
    -> (sindexpath -> c -> d)
    -> path                                     -- Nil
    -> f a c -> f b d
ibimapWith icons jcons f g p = ibimap (\ i -> f (icons i p)) (\ j -> g (jcons j p))

Note that imapWith / ibimapWith now take an additional cons argument(s), but also a path argument - like pdiiso_fmap earlier - except now the types are free. In fact, we have gone from implicitly working with lists (through use of :) to accepting arguments in the form of List's constructors, Nil and Cons. By exposing the cons-like arguments, we allow for the user to determine the actual type of the indices and paths freely! The profunctoral perspective, everybody!

Now, we can redefine phylo / pbihylo / pdihylo in terms of these new functions - and the definitions are much cleaner!

phylo alg coalg = h where
    h p = alg p . imapWith (:) h p . coalg p
pbihylo alg coalg = h where
    h p = alg p . ibimapWith ((:) . Left) ((:) . Right) h p . coalg p
pdihylo f alg coalg = h where
    h p = alg p . ibimapWith (,) (:) h p . coalg p

It seems that imapWith could be the more appropriate definition of an indexed functor, if we want to consider the profunctoral perspective. Even more, although we have defined imapWith using imap, it can go in the other direction trivially using imap f = imapWith const f undefined. However, imap makes for a concise base case, and we will leave it as-is.

The end of the beginning

Our campfire is now embers, and the stars are overhead. Today, we have accomplished a lot, even though the significance of much of it has yet to be felt. Now, it is time to sleep on what we have learned - to digest it and let it become part of our learned self.

For anyone who has made it this far, congratulations - this marks the end of the beginning. All of this has been preparation, a foundation for connecting the many topics that we will be tackling in the days to come.

I hope you'll join me next time we explore the recursiverse, when we discuss sources and sourced morphisms, and the implications of imapWith.

Where to get the code

You can find version 0.0.2 of the birecursion-schemes package here, which corresponds to this article.

---