Building up Zippers from Distributive, Representable, and Cofree
We're going to take a look at an alternative way to define a Zipper Comonad | |
over a data type. Typically one would define a Zipper Comonad by defining a new | |
datatype which represents the Zipper; then implementing `duplicate` and | |
`extract` for it. `extract` is typically straightforward to write, but I've had | |
some serious trouble writing `duplicate` for some more complex data-types like | |
trees. | |
We're looking at a different way of building a zipper, The advantages of this | |
method are that we can build it up out of smaller instances piece by piece. | |
Each piece is a easier to write, and we also gain several utility functions | |
from the Typeclasses we'll be implementing along the way! It's not terribly | |
practical, but it's a fun experiment. | |
This post is a literate haskell file, so that means you can load it up directly | |
in GHC and play around with it! Let's get started. | |
First we'll need a few language extensions, In case you're wondering; TypeFamilies | |
is used by the `Representable`. | |
> {-# language DeriveFunctor #-} | |
> {-# language TypeFamilies #-} | |
> {-# language InstanceSigs #-} | |
We're going to be writing a Zipper into a list. In case you're unfamiliar, a | |
zipper is essentially a 'view' into a structure which is focused on a single | |
element. We'll call our focused view into a list a 'Tape' | |
> module Tape where | |
Go ahead and import everything we'll need: | |
> -- http://hackage.haskell.org/package/comonad-5/docs/Control-Comonad.html#t:Comonad | |
> import Control.Comonad | |
> -- http://hackage.haskell.org/package/free-4.12.4/docs/Control-Comonad-Cofree.html | |
> import Control.Comonad.Cofree | |
> -- https://hackage.haskell.org/package/distributive-0.5.0.2/docs/Data-Distributive.html#t:Distributive | |
> import Data.Distributive | |
> -- https://hackage.haskell.org/package/adjunctions-4.3/docs/Data-Functor-Rep.html#t:Representable | |
> import Data.Functor.Rep | |
> -- https://hackage.haskell.org/package/containers-0.5.10.2/docs/Data-Sequence.html | |
> import qualified Data.Sequence as S | |
> -- https://hackage.haskell.org/package/base-4.9.1.0/docs/Data-List-NonEmpty.html | |
> import qualified Data.List.NonEmpty as NE | |
Great! At this point one would typically define their zipper data type, which | |
for lists would look like: `data Tape a = Tape [a] a [a]`, This represents the | |
idea of having a single element of the list 'under focus' with other elements | |
to the left and right. | |
We're trying something different, we're going to define TWO types. One type | |
which represents all of the POSSIBLE movements, and one which represents a | |
CHOICE of a specific movement. | |
First we'll define the possible movements in our tape using the PRODUCT tape | |
`TPossible`, we'll have a slot in our structure for both leftward and rightward | |
movements: | |
> data TPossible a = TPossible | |
> { leftward :: a | |
> , rightward :: a | |
> } deriving (Show, Eq, Functor) | |
We're deriving Functor here too, that'll come in handy later. | |
Next we represent a choice of direction as a SUM type, i.e. we can choose to go | |
either LEFT or RIGHT at any given focus in the list. | |
> data TChoice = L | R | |
> deriving (Show, Eq) | |
Notice that each piece contains a different piece of the information we need, | |
a value in TPossible knows what's to the left or right, a value in TChoice knows | |
which way to move, but not what's there. This sort of relationship shows us that TPossible | |
is a `Representable Functor`. | |
Let's talk about what that means. | |
A Representable Functor is any functor from which you can | |
extract elements by giving it an index. That is; it's any functor that you can describe completely | |
using a function from an index to a value. Given `Index -> a` you can build up an `f a` if you have a relationship | |
between `Index` and `f`! | |
In our case we have such a relationship; and if we have a function | |
`TChoice -> a` we could build up a `TPossible a` by calling the function for | |
the leftward and rightward slots using `L` and `R` respectively. | |
But we're getting a bit ahead of ourselves; we'll need to build up a | |
Distributive Instance first, it's a pre-requisite for the Representable class, and in fact every instance of | |
Representable is also Distributive; If we like we can actually just implement Representative and use `distributeRep` | |
from `Data.Functor.Rep` as your implementation of Distributive, but we'll do it the long way here. | |
Distributive can seem strange if you haven't worked with it before, it's the | |
dual of Traversable; Traversable can pull out other Applicative Effects from | |
within its structure, and so Distributive can pull its own structure from any | |
functor to the outside. You can define an instance by implementing either | |
`distribute` or `collect`. | |
Here're the signatures: | |
```haskell | |
distribute :: Functor f => f (g a) -> g (f a) | |
collect :: Functor f => (a -> g b) -> f a -> g (f b) | |
``` | |
Let's see a few examples to solidify the idea: | |
distribute :: [Identity a] -> Identity [a] | |
distribute :: [Bool -> a] -> (Bool -> [a]) | |
distribute :: [TPossible a] -> TPossible [a] | |
The list here could be ANY functor, I just used lists because it's something | |
most people are familiar with. In many cases sequence and distribute are | |
interchangeable since a lot of types have reasonableApplicative instances, but | |
it's important to note that `distribute` pulls a distributive functor OUT from | |
any wrapping functor while `sequence` from Data.Traversable pushes a | |
traversable INTO a wrapping Applicative. | |
A good intuition for determining whether a functor is distributive is to ask | |
whether values of that functor (f a) always have the same number of elements of | |
'a'. If they do, and they don't have extra information aside from their | |
structure, then it's probably distributive. Note that this means that we | |
actually can't define Distributive for finite-length lists, give it a try if | |
you don't believe me! | |
We've got exactly two slots in EVERY TPossible so we can implement distribute | |
by creating an outer TPossible where the left slot is the functor containing | |
all the left values and likewise for the right slot. | |
> instance Distributive TPossible where | |
> distribute :: Functor f => f (TPossible a) -> TPossible (f a) | |
> distribute fga = TPossible (fmap leftward fga) (fmap rightward fga) | |
Now that's out of the way, let's get back to Representable! Remembering our | |
previous definition 'TPossible' is Representable because it has exactly two | |
slots, a left and a right which can be indexed by TChoice! | |
We need 3 things for an instance of Representable: | |
- A type which represents our index (called Rep) | |
- `index` which pulls out the value at a given index. | |
- `tabulate` which builds up an object from a function. | |
> instance Representable TPossible where | |
> type Rep TPossible = TChoice | |
> | |
> index :: TPossible a -> TChoice -> a | |
> index (TPossible l _) L = l | |
> index (TPossible _ r) R = r | |
> | |
> tabulate :: (TChoice -> a) -> TPossible a | |
> tabulate describe = TPossible (describe L) (describe R) | |
We're moving along quick! We've got the necessary tools to index into our | |
TPossible structure, which we can use to follow a 'path' through the zipper to | |
find an element, but currently we only have a way to represent a single choice | |
of direction at once. We can say we want to move right using 'R', but then | |
we're stuck! Similarly with TPossible we have places to store the value to the | |
left and right, but can't check the value at the current position! We can solve | |
the problem by wrapping our TPossible in Cofree! | |
Cofree allows us to promote a functor that we have into a Comonad by ensuring | |
we always have an element in focus and that we have a way to move around | |
amongst possible options while still maintaining a focus. It does this by | |
using an infinitely recursive structure which wraps around a given functor (in | |
our case TPossible). Let's build up a few of these structures by combining | |
TPossible with Cofree! (:<) is the Cofree constructor and has the following | |
structure `a :< f (Cofree f a)`. | |
Lucky for us, if we have a Representable instance for a functor f, we get | |
Representable of Cofree f for free! We can cheat a little and use our | |
Representable class to build up the data structure for us by simply providing a | |
describe function to 'tabulate' which returns the value we want to appear at any | |
given index. Remember, the index we chose for TPossible is TChoice. The index for | |
Cofree TPossible is a Sequence of TChoice! | |
Let's build our first actual 'Tape' using tabulate with our Cofree | |
Representable instance! Here's an infinite number-line going out in both directions from our focus: | |
> relativePosition :: S.Seq TChoice -> Int | |
> relativePosition = sum . fmap valOf | |
> where | |
> valOf L = (-1) | |
> valOf R = 1 | |
> numberLine :: Cofree TPossible Int | |
> numberLine = tabulate relativePosition | |
Kinda weird to look at eh? Effectively we're saying that if we move left the | |
position is 1 less than whatever we were at before, and moving right adds | |
one to the previous total. You could also write a recursive version of | |
`describe` which calculates the result by pulling each index off of the | |
sequence and returns the result! Let's look at another example where we want | |
a zipper into a finite list! | |
We'll define a function which 'projects' a list into an infinite Cofree; | |
we define the behaviour such that moving left 'off the edge' just leaves you at the | |
leftmost element and similar with the right. I'm going to re-use our previous helper | |
'relativePosition' here, but this time I'll use it to index into a list! We'll | |
put some checks in place to ensure we never get an index which is out of bounds, | |
if we're given an out of bounds index we'll just give the first or last element | |
respectively; i.e. the zipper will never 'fall off the end' | |
> project :: NE.NonEmpty a -> Cofree TPossible a | |
> project l = tabulate describe | |
> where | |
> describe = (l NE.!!) . foldl go 0 | |
> maxIndex = length l - 1 | |
> minIndex = 0 | |
> go n L = max minIndex (n - 1) | |
> go n R = min maxIndex (n + 1) | |
> elems :: NE.NonEmpty String | |
> elems = "one" NE.:| ["two", "three"] | |
Now we can write a sequence of directions to form a path and see where we end up! | |
Remember, the zipper 'sticks' to the ends if we try and go off! | |
> path :: S.Seq TChoice | |
> path = S.fromList [R, R, R, R, L] | |
Now we can `index (project elems) path` to get "two"! | |
All this talk and we still haven't mentioned Comonad yet! Well lucky us; | |
the 'free' package describes an instance of Comonad for all `(Functor | |
f => Cofree f a)`! So our `(Cofree TPossible a)` is a Comonad over a | |
for free! Remember that a Comonad instance gives us access to `extend`, | |
`extract` and `duplicate` functions. You can see their types in | |
[Control.Comonad](https://hackage.haskell.org/package/comonad-5/docs/Control-Co | |
monad.html#t:Comonad). | |
We already have a way to extract an element at a given position via 'index', but don't | |
really have a way to move our zipper WITHOUT extracting; don't fret though, we can | |
describe this behaviour in terms of our new Comonad instance by using extend! | |
> moveTo :: S.Seq TChoice -> Cofree TPossible a -> Cofree TPossible a | |
> moveTo ind = extend (\cfr -> index cfr ind) | |
Great! Extend works by duplicating the Comonad meaning we'll have a (Cofree | |
TPossible (Cofree TPossible a)), then it fmaps over the duplicated parts with | |
the given function. The function 'move' will move the element in each slot | |
of the Cofree over by a given amount, which is the same result as 'scanning' our | |
Tape over to a given position. | |
Cool stuff! I hope you've learned a little about Distributive, Representable, | |
Comonads, Cofree, and zippers! If you have any questions find me on twitter | |
@chrislpenner | |
Cheers! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment