### Comonads and reading from the future

I'm too busy reading Bernie Pope and Russell O'Connor's articles in the latest Monad Reader to think about much else right now, so I'm only going to make a brief post. I want to mention something pointed out by Nick Frisby over here. The

Think of it like this: when you use

Here's an example of

In the expression

Note how in this example (1)

That wasn't too brief. But I did cheat by copying and pasting code from an old post. Anyway, back to tinkering with my implementation of

`loeb`function is in fact closely related to`cfix`, the dual of`mfix`for monads, defined by Dave Menendez. (Nick Frisby's statement isn't quite correct but it's interest value outweighs its truthiness.) In fact, I can borrow Russell's language to say that whereas`mfix`sends data back in time,`cfix`and`loeb`read data from the future!Think of it like this: when you use

`cobind`with a comonad you provide some function that distills down a comonadic data structure into a single value and then`cobind`applies this distillation repeatedly at every point in the comonadic structure to give you another comonadic structure. My canonical example is the cellular automaton where you give a rule that defines how to compute each individual cell as a function of the whole grid, and`cobind`applies this throughout an entire input grid to give you back an entire output grid. The functions`cfix`and`loeb`allow you to give rules for each cell where you're allowed to make reference to the entire*output*grid. If you think of the output grid as something in the future that you haven't yet computed, then`cfix`and`loeb`allow you to read from the future.Here's an example of

`cfix`it in use (where I make`[]`a comonad by interpreting it as a kind of one-sided zipper):

> instance Show (x -> a)

> instance Eq (x -> a)

> instance (Num a,Eq a) => Num (x -> a) where

> fromInteger = const . fromInteger

> f + g = \x -> f x + g x

> f * g = \x -> f x * g x

> negate = (negate .)

> abs = (abs .)

> signum = (signum .)

> class Comonad w where

> coreturn :: w a -> a

> cobind :: (w a -> b) -> w a -> w b

> instance Comonad [] where

> coreturn (x:xs) = x

> cobind f [] = []

> cobind f (x:xs) = f (x:xs) : cobind f xs

> cfix :: Comonad d => d (d a -> a) -> a

> cfix d = coreturn d (cobind cfix d)

> ouroboros = [2*head.tail,1+head.tail,17]

> test = cfix ouroboros

In the expression

`test`we can use`head`and`tail`to refer to the sublist to the right of each element from within the list itself. For example, in the subexpression`2*head.tail`the`head.tail`is being applied to`cfix [1+head.tail,17]`.Note how in this example (1)

`loeb`gives you back an entire list, not just one element and (2)`cfix`respects the comonadic structure in the sense that you can only refer to elements to the right of the current one whereas`loeb`lets you refer to the entire output list. I think this helps to make clear the differences and similarities between`cfix`and`loeb`.That wasn't too brief. But I did cheat by copying and pasting code from an old post. Anyway, back to tinkering with my implementation of

`dropWhile`...
## 8 Comments:

Your blog continues to amaze me, and I just wanted to say

thanks. Most of the CompSci jargon is gobbledygook to me, but I really appreciate the effort you're taking to talk about monads and the like.kea,

If you think some of the jargon looks like gobbledygook, you should check out the published papers that some of this stuff comes from :-) It's been hard work trying to make inroads into this stuff over the last two years.

That's a nice contrast you've developed.

My first post was inspired mostly by type signatures. Now that I've looked at your actual definition of loeb :), I readily see the difference you're highlighting. As you pointed out, loeb does not need the comonadic structure. This highlights the big difference: comonadic structure (and thus cfix) caters to relative references [1] whereas loeb allows for absolute references.

In your spreadsheet example, you use !! to get the nth cell in the list. A comonadic approach would allow a cell to refer to "the cell to my left" without needing to know its own cell number. Both features are supported in various ways by spreadsheets: whenever I do a fill-down in Excel, every now and then I'm surprised that the relative references worked how I had intended.

Just a couple of notes: to get cfix to "return a whole list" you can use cobind cfix. Also, to have access to the "entire output list", you can use a more robust comonad (like Uustalu and Vene's LVS) with an absolute access function a la !!.

Thanks for the discussion, that was a nice contrast to appreciate.

[1] - This is why zippers induce comonads; I can talk about neighbors in various directions relative to wherever I'm currently at in the structure.

Forgot to sign! Nick Frisby here again :)

(I guess kotsu=Nick Frisby.)

Of course! cfix and loeb deal with relative and absolute references. I hadn't thought of it that way. It's truly bizarre how fiddling about semi-randomly with types leads to new ways to view concepts that are already well known and considered natural.

I'll have a look at Uustalu and Vene's LVS. Their recent papers have been really interesting.

I've been reading your explorations of comonads -- your explanations using examples of cellular automata and image processing have been very helpful for me to understand them a bit better. In parallel, I've been reading about Haskell attribute grammars. Do comonads address a class of problems well that attribute grammars do not?

One of the issues with monads, even with transformers, is that they "stack" poorly (the result depends on order of composition and each monad's internal implementation detail); do comonads compose better than monads?

geophf,

By coincidence, I've been thinking about stacking comonads for the last couple of days. Not got very far yet. A web search reveals almost no hits on "comonad transformer".

re: your thinking about composing comonads -- excellent, as I've observed that you thinking about classes of problems results in solutions on your blog.

As to attribute grammars for Haskell, have you looked at them? Applied them? Do you see them being useful in these problem domains, or do they address an entirely different class of problems?

Post a Comment

<< Home