I've written previously about Löb's theorem and the curious manner in which we can evaluate a list of functions which depend on each other's outputs simultaneously without much fuss, like a shitty one-row spreadsheet.

Today I am going to get inter-dimensional.

Well, two-dimensional. But I am going to ... Excel at it.

1 Imports and blah blah

{-# LANGUAGE DeriveFunctor #-}

import Control.Applicative
import Control.Comonad
import Data.Function (fix)
import Control.Monad

That's right: today we are dealing with comonads. Monads just weren't confusing enough so I turned them upside down and backward.

(NB: given that the definition of fix is fix f = f (fix f) I actually typed nine more characters importing it than just writing it here. Meh.)

Also there's a standard library function whose name I want to use but which is otherwise useless for this exercise:

import Prelude hiding (iterate)

2 Double Löb-el

To recap, by abusing Löb's theorem we were able to write this:

loeb :: (Functor f) => f ( f a -> a ) -> f a
loeb x = fmap (\a -> a (loeb x)) x

What? Here is an example:

test_list :: [[Integer] -> Integer]
test_list = [ \ _ -> 0             -- a constant value
            , \ l -> (l !! 0) + 2  -- 2 + the first item
            , \ l -> (l !! 1) * 2  -- 2 * the second element
            ]

test_list is a list of functions of the type [Integer] -> Integer. Let's see what happens when we apply loeb:

ghci> loeb test_List
[0,2,4]

NB: there is a standard Haskell function, const, which we could have used in place of \ _ -> 0. It takes two arguments, ignores the second one and returns the first. We will use that from now on.

3 Your zipper is undone

So a fixed length list of functions is cool but, and I don't know about you, but when I use Excel it's kind of infinite in all directions.

But how do I represent an infinite list in such a way that I can navigate it, read data from it, and modify its internals? The structure I'll use is often called a list zipper.

data Zipper a = Zipper
    { viewL :: [a]
    , focus :: a
    , viewR :: [a]
    } deriving (Functor, Show)

A list zipper is like a cursor: it has a current focus element and lists of elements on either side of the focus it can navigate to. Accessing or modifying the focus is a constant time operation.

Moving "left" (or "right") amounts to prepending the focus to one list and popping the head off the other one, creating the new focus. These are also constant time operations.

moveL :: Zipper a -> Zipper a
moveL (Zipper (l:ls) c rs) = Zipper ls l (c:rs)

moveR :: Zipper a -> Zipper a
moveR (Zipper ls c (r:rs)) = Zipper (c:ls) r rs

It so happens that a Zipper is an Applicative:

instance Applicative Zipper where
    (Zipper ls c rs) <*> (Zipper ls' c' rs') =
        Zipper (ls <*> ls') (c c') (rs <*> rs')
    pure = Zipper <$> pure <*> id <*> pure

If you don't what Applicative is, skip to the end of this post and then come back.

4 Zippity doo-dah

We have created a zipper to anchor us at a desired location in an infinite list, so to get started using our zipper we'll need to be able to create an infinite list. Voici:

unfold :: (b -> (a, b)) -> b -> [a]
unfold f c =
    let (x, d)  = f c
    in  x:(unfold f d)

unfold is like the opposite of a traditional list fold: instead of iterating over a list and accumulating some result value, we take an initial value and generate a list from it according to some pre-determined rule.

Armed with a means of generating infinite lists according to some rule, we can now seed new zippers with some initial focus value:

seed :: (c -> (a, c)) -- \
     -> (c -> a)      --  \
     -> (c -> (a, c)) --   - Type signatures are so fun!
     -> c             --  /
     -> Zipper a      -- /
seed prev center next =
    Zipper <$> unfold prev <*> center <*> unfold next

Basically, take the fourth argument, unfold two infinite lists with it based on some generating rules, and set it as the focus.

Note the type signature says seed has four values but the function only has three: Zipper <$> unfold prev <*> center <*> unfold next creates a function awaiting the final argument.

5 Back to the future!

It so happens that our Zipper is a comonad. The name comes from the fact that it is the mathematical dual of another concept that already had a name, and mathematicians are kind of predictable that way.

All comonads are functors, in that they provide some kind of computational context for a value. Here's one way of thinking about comonads: a structure is comonadic if we always know how to get a value from it.

A comonad must also allow me to duplicate its values: if I have a comonadic structure containing values of type a, then I can create a structure of structures. This is confusing and mind-bendy to think about so if it doesn't make sense just go with the flow.

The reason, though, is that comonads describe computations where, instead of sequentially moving from state to state reacting to and causing effects like normal imperative programming, we instead are presented with multiple simultaneous future states. We can write a function to transform one of them, abstractly, and this function will be applied to all possible future states.

This is intimately related to the fact that we know for certain we will be able to yank a value out of the comonad: thus, we can borrow against the future.

Thus, a comonad must implement these functions ¹:

extract :: (Comonad w) => w a -> a
-- and
duplicate :: (Comonad w) => w a -> w (w a)

extract is easy: hand back the focus of the Zipper. That's kind of why we have it in the first place.

What about the duplicate function? We know we can create a Zipper by giving a seed value to seed. What if that seed value was a Zipper? What does a Zipper of Zippers look like?

Let's take this shit slow. A Zipper of, say, Int values

z1 = seed (\x -> (x-1,x-1)) (const 0) (\x -> (x+1,x+1))

like this one is focused on some number, and the values to the left and right are modifications defined by some transformation function (in this case, adding or subtracting 1).

So a Zipper of Zippers is focused on one zipper and the left and right neighbors are other zippers. How we want to transform the focus should really just be left up to the user. Hence:

iterate :: (a -> a)
        -> (a -> a)
        -> a
        -> Zipper a
iterate prev next =
    seed (dup . prev) id (dup . next)
    where dup a = (a, a)

Thus, our comonad instance is complete:

instance Comonad Zipper where
    extract = focus
    duplicate = iterate moveL moveR

duplicate creates a Zipper of Zippers where the focus is our original and moving in either direction transforms the focus by moving it.

HEAD ASPLODE

6 Zip it good

Comonads also have a function, extend, which is defined in terms of duplicate:

extend :: (Comonad w) => (w a -> b) -> w a -> w b
extend = fmap f . duplicate

So if we can extract a value of type a and transform it into a b then we can extend the whole comonad to being a comonad of b values.

Another standard function defined on comonads is the fixpoint:

wfix :: Comonad w => w (w a -> a) -> a
wfix w = extract w (extend wfix w)

If I have a comonad containing an extract procedure (or perhaps multiple extraction procedures) I can compute a fixed point of those functions and extract the final value.

I noticed that extend wfix has a very interesting type signature:

evaluate :: (Comonad w) => w (w a -> a) -> w a
evaluate = extend wfix

Intredasting.

Zipper is a comonad. If we have a Zipper of functions which ... evaluate Zippers then ... holy shit.

7 Holy shit

So let's create a Zipper of functions that evaluate Zippers:

zipper_1 :: Zipper (Zipper Int -> Int)
zipper_1 = Zipper (repeat ((*2) . extract . moveR))
            (const 1) (repeat ((+1) . extract . moveL))

The initial focus is 1; as you move left, you double; as you move right, you add 1.

For convenience let's write a function to extract a subsection of a Zipper into a list for viewing:

toList :: Int -> Zipper a -> [a]
toList n (Zipper ls x rs) =
    reverse (take n ls) ++ [x] ++ take n rs

ghci> toList 5 (evaluate zipper-1)
[32,16,8,4,2,1,2,3,4,5,6]

8 Holier Shit

I said we were going interdimensional, and I'm no liar.

We have already shown we can create Zippers of Zippers on-demand, and the result is an infinite list of variations on an initial Zipper.

Let's make this official:

data Cursor a = Cursor (Zipper (Zipper a))

up :: Cursor a -> Cursor a
up (Cursor p) = Cursor (moveL p)

down :: Cursor a -> Cursor a
down (Cursor p) = Cursor (moveR p)

By convention, we'll say that going left on the outer Zipper is going "up," and vice versa. A Cursor is a Functor:

instance Functor Cursor where
    fmap f (Cursor p) = Cursor (fmap (fmap f) p)

Going left and right, though, is a little hairy: we want to shift every single Zipper left or right uniformly. Fortunately, we just defined Cursors as Functors, so we'll just fmap the movements inside the outer Zipper:

left :: Cursor a -> Cursor a
left (Cursor p) = Cursor (fmap moveL p)

right :: Cursor a -> Cursor a
right (Cursor p) = Cursor (fmap moveR p)

A Cursor is also a comonad. extract is just extracting the focus of the focus Zipper. duplicate is a little weirder. We want to generate a Cursor of Cursors. Following from the same trick we used for Zippers:

horizontal :: Cursor a -> Zipper (Cursor a)
horizontal = iterate left right

vertical :: Cursor a -> Zipper (Cursor a)
vertical = iterate up down

We can declare the Cursor a comonad and move on with our lives:

instance Comonad Cursor where
    extract (Cursor p) = extract $ extract p
    duplicate z =
        Cursor $ fmap horizontal $ vertical z

We created the Cursor to allow us to do two-dimensional spreadsheet-esque programming so it'd be nice if I could write some easy-to-read grid of functions and then make a Cursor out of them.

And lo:

makeCursor :: a -> [[a]] -> Cursor a
makeCursor def grid = Cursor $ Zipper (repeat fz) fz rs where
    rs = (map line grid) ++ repeat fz
    dl = repeat def
    fz = Zipper dl def dl
    line l = Zipper dl def (l ++ dl)

Armed and ready, let's create a spreadsheet with default cell values of 0 and two functions in the same column:

sheet1 :: Cursor (Cursor Int -> Int)
sheet1 = makeCursor (const 0)
    [ [ (\c -> 15 + 2 * (extract (left c)))   ]
    , [ (\c -> 1 + (extract (up c)))          ] ]

It would be nice if we could view some subset of our Cursor as a list of lists, analogously to our toList function.

cursorView :: Int -> Cursor a -> [[a]]
cursorView n (Cursor zs) = toList n $ fmap (toList n) zs

Let's run this in ghci:

ghci> let rows = sheet1 & evaluate & cursorView 5
ghci> forM_ rows (putStrLn . show)
[0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,15,0,0,0,0]
[0,0,0,0,0,0,16,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0]

Boom.

The definition of (&) is very simple:

(&) = flip ($)

9 Excursor-sions

For completeness, let's define a way to insert a value at the focus of a Cursor or a Zipper. I made up a simple typeclass for things that can be inserted into so that I wouldn't have to have insertCursor and insertZipper or some other ugly nonsense.

class Insertable i where
    insert :: a -> i a -> i a

instance Insertable Zipper where
    insert x (Zipper l _ r) = Zipper l x r

instance Insertable Cursor where
    insert x (Cursor p) =
        Cursor $ insert newLine p where
            newLine = insert x oldLine
            oldLine = extract p

10 Appendix: Applicative what-now?

An applicative functor is a functor with a little extra power. A functor is a computational context into which you can map transformations. Concrete example: Maybe Int lets me map Int functions into a context where there may not be an actual value. fmap (+1) (Just 1) gives Just 2 even though (+1) knows nothing of Maybe. However, fmap (+1) Nothing gives Nothing.

Applicative functors let you take a function which is already in the context and map it onto contextualized values. A type signature is worth a thousand words:

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b

Example:

ghci> Just (\x y -> x * y) <*> Just 3 <*> Just 4
Just 12

An Applicative must also give you a way of lifting pure values into the functor. Hence:

pure :: (Applicative f) => a -> f a

If your functor can support (<*>) and pure then congratulations, it is also Applicative. There are a number of cases where Applicatives are handy or convenient.