An implementation of Clowns to the Left of me, Jokers to the Right (Pearl): Dissecting Data Structures by Conor McBride in PureScript.

This package provides three useful modules:

`Dissect.Class`

`Data.Functor.Polynomial`

`Data.Functor.Polynomial.Variant`

## Installation

Using `spago`

:

```
$ spago install dissect
```

or if not present within the current package set, add it to
`packages.dhall`

:

```
let upstream =
https://github.com/purescript/package-sets/releases/download/psc-0.14.4-20211005/packages.dhall
sha256:2ec351f17be14b3f6421fbba36f4f01d1681e5c7f46e0c981465c4cf222de5be
let overrides ~ {~}
let additions =
{ dissect =
{ dependencies = [ ... ] -- copy dependencies from spago.dhall
, repo = "https://github.com/PureFunctor/purescript-dissect.git"
, version = "<insert-desired-revision-here>"
}
}
in upstream // overrides // additions
```

## Rationale

I originally encountered the paper while looking for a way to ensure stack safety with matryoshka, being briefly mentioned in a comment in matryoshka#9. This eventually led to the creation of ssrs where I derived stack-safe recursion schemes via dissectible data structures based on the tail-recursive catamorphism originally implemented in the paper.

Another use-case I've found is for implementing mutually recursive collections of types which is explored in the paper: Generic programming with fixed points for mutually recursive datatypes. I've implemented a proof of concept in ./test/Universe.purs and it works well in conjunction with recursion schemes provided by ssrs.

## Quick Primer on Dissect

I'm assuming that by coming across this package, you're comfortable working with fixed-point functors from recursion schemes. As such, I won't try to explain everything in-depth, just the concepts that matter.

Essentially, dissections take fixed-point functors and transform them into bifunctors that contain either the base case of a fixed-point data type or its recursive step. To contextualize this, let's say we have the following tree structure:

`data TreeF n = Leaf | Fork n n n`

Since recursion is factored out in this definition and replaced by some
type variable `n`

, we can fill it with anything we want. Likewise, we
can also use the `Mu`

combinator to effectively create a recursive data
type. What we want in a dissection is to be able to represent the steps
on how we're going to deconstruct recursive cases such as `Fork`

.
Let's start by visualizing the essence of dissecting functors:

We say that `TreeF`

essentially has a three seats for `n`

to be
contained in, and that lives under the `Fork`

constructor:

`Fork [ n - n - n ]`

Note that we take no notice to the `Leaf`

constructor as it contains no
seats for `n`

.

The `right`

function allows us to take this data and pluck out an `n`

,
leaving us a hole:

```
> right $ Fork [ n - n - n ]
n, Fork [ () - n - n ]
```

Likewise, it can also take a structure with holes and something to fill it with:

```
> right $ m, Fork [ () - n - n ]
Fork [ m - n - n ]
```

If we repeat this process, we eventually end up plucking out all `n`

and
replacing them with `m`

:

```
> right $ Fork [ m - n - n ]
n, Fork [ m - () - n ]
> right $ m, Fork [ m - () - n ]
Fork [ m - m - n ]
> right $ Fork [ m - m - n ]
n, Fork [ m - m - () ]
> right $ m, Fork [ m - m - () ]
Fork [ m - m - m ]
```

This is, in essence, one way to do a `map`

operation, but with the added
benefit of being able to perform it in a stack-safe manner, as we've
essentially factored out recursion, and we're really only concerned
with plucking out and planting new values into structures.
Unfortunately, its cost is that we must describe this process ourselves
by defining data types that correspond to the intermediate states of
where the hole currently is.

In reality, the `right`

function has the following type:

```
right
∷ ∀ c j
. Either (p j) (Tuple (q c j) c)
→ Either (Tuple j (q c j)) (p c)
```

Its left path describes plucking out a value from some `Functor`

and
returning its dissection paired with its inner value `j`

, or it returns
the same `Functor`

containing some value `c`

; its right path on the
other hand takes a dissection and a value to fill it with, and has the
same return choice as the left path. There also exists the `pluck`

and
`plant`

helper functions for choosing paths more elegantly:

```
pluck ∷ ∀ p q c j. Dissect p q ⇒ p j → Either (Tuple j (q c j)) (p c)
pluck = right <<< Left
plant ∷ ∀ p q c j. Dissect p q ⇒ (q c j) → c → Either (Tuple j (q c j)) (p c)
plant q c = right (Right (Tuple q c))
```

Now, let's start writing actual code:

```
data TreeF n = Leaf
| Fork n n n
derive instance Functor TreeF
data TreeF_2 n m = ForkRR m m
| ForkLR n m
| ForkLL n n
instance Bifunctor TreeF_2 where
bimap f g = case _ of
ForkRR m0 m1 -> ForkRR (g m0) (g m1)
ForkLR n0 m1 -> ForkLR (f n0) (g m1)
ForkLL n0 n1 -> ForkLL (f n0) (f n1)
```

With boilerplate out of the way, we can now write the `Dissect`

instance:

```
instance Dissect TreeF TreeF_2 where
right = case _ of
Left Leaf → Right Leaf
```

First and foremost, it's impossible to dissect the `Leaf`

constructor
as it contains no points of recursion, so we terminate immediately,
however, `Fork`

is much more interesting. Here we can see how its first
element is being plucked out, with the rest of its seats being delegated
to `ForkRR`

.

`Left (Fork m n o) → Left (Tuple m (ForkRR n o))`

Then, we move on to the `Right`

path. In here, we first start by
plucking out yet another seat in `ForkRR`

, delegating the remaining seat
into `ForkLR`

and planting some other value in its place.

```
Right (Tuple w c) → case w of
ForkRR m n → Left (Tuple m (ForkLR c n))
```

For `ForkLR`

, we pluck out another seat yet again, planting a new value
in its place using `ForkLL`

. Likewise, we also carry over the value
we've planted previously in `ForkLR`

.

`ForkLR n m → Left (Tuple m (ForkLL n c))`

Finally, for `ForkLL`

, we start reconstructing `Fork`

but with the
planted values:

`ForkLL n o → Right (Fork n o c)`

You've just written your first `Dissect`

instance!

```
instance Dissect TreeF TreeF_2 where
right = case _ of
Left Leaf → Right Leaf
Left (Fork m n o) → Left (Tuple m (ForkRR n o))
Right (Tuple w c) → case w of
ForkRR m n → Left (Tuple m (ForkLR c n))
ForkLR n m → Left (Tuple m (ForkLL n c))
ForkLL n o → Right (Fork n o c)
```

In conclusion, the `Dissect`

class factors out the recursion in the
traversal of some recursive data structure. Instead of relying on
recursion primitives, we've successfully lifted recursion into a
toolkit for implementing stateful iterative machines.