Saturday, February 03, 2007

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 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:

Kea said...

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.

sigfpe said...

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.

kotsu said...

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.

kotsu said...

Forgot to sign! Nick Frisby here again :)

sigfpe said...

(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.

geophf said...

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?

sigfpe said...

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".

geophf said...

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?

Blog Archive