113

This is a follow-up to the answer to my previous question.

Suppose I need to map each item a:A of List[A] to b:B with function def f(a:A, leftNeighbors:List[A]): B and generate List[B].

Obviously I cannot just call map on the list but I can use the list zipper. The zipper is a cursor to move around a list. It provides access to the current element (focus) and its neighbors.

Now I can replace my f with def f'(z:Zipper[A]):B = f(z.focus, z.left) and pass this new function f' to cobind method of Zipper[A].

The cobind works like this: it calls that f' with the zipper, then moves the zipper, callsf' with the new "moved" zipper, moves the zipper again and so on, and so on ... until the zipper reaches the end of the list.

Finally, the cobind returns a new zipper of type Zipper[B], which can be transformed to the list and so the problem is solved.

Now note the symmetry between cobind[A](f:Zipper[A] => B):Zipper[B] and bind[A](f:A => List[B]):List[B] That's why List is a Monad and Zipper is a Comonad.

Does it make sense ?

Community
  • 1
  • 1
Michael
  • 41,026
  • 70
  • 193
  • 341
  • 1
    I'm not an expert, but that makes sense to me. I had an epiphany while reading your explanation. Thanks! – acjay Jun 03 '14 at 18:11
  • 7
    Your question is very difficult to answer in the SO format... but you're absolutely correct. Element-focused Zippers are always comonads. – J. Abrahamson Aug 28 '14 at 16:55
  • 1
    This answer might help as well: http://stackoverflow.com/questions/25554062/zipper-comonads-generically – J. Abrahamson Apr 11 '15 at 04:15
  • Thank you. I do not know `Haskell` but I will check it out. – Michael Apr 11 '15 at 04:26
  • 4
    List can be viewed as a comonad just as well (in multiple ways), while a Zipper can be cast as a monad (also in many ways). The difference is in whether you are conceptually focused on "appending" data constructively to a state machine (that's what the Monad interface is about), or "extracting" state from it "deconstructively" (that's what the Comonad does). It is not easy to answer the question, stated as "does this understanding make sense", however. In some sense it does, in another it does not. – KT. Jan 03 '16 at 13:05
  • @KT. Thanks for the comment. Can you give a simple example of using `List` as a `Comonad` ? – Michael Jan 03 '16 at 17:43
  • 3
    To cast something into a comonad you need to provide two operations: 1) Extraction of a value (e.g. it could be the head of the list) and 2) Application of a list-processing operation (e.g. you could apply it in a sliding-window manner along the list or in an element-wise manner or the like, assuming an appropriate unit transform won't change the list). Whether such a way of processing a list makes any sense is a separate issue. Note that a bare comonad interface does not provide neither a way to construct the list nor to traverse it. It only knows how to consume list-aware operations. – KT. Jan 03 '16 at 18:08
  • @KT. Thanks again. Do you know any simple application of such a List Comonad ? I am thinking about `unescaping` of a string (a list of chars), where you need a function `List[Char] => Char`. – Michael Jan 03 '16 at 18:10
  • @Michael, indeed, I guess you could regard an unescaping operation (or more generally, a tokenizer/parser/signal converter) as a list- (or more frequently, stream-) based comonad. The fact that you can do it does not mean this is an example of a proper "application", though. The need to introduce such an abstraction must come from elsewhere and I am not functionally-oriented enough to see it. "Adding more math for the sake of math" is not a reasonable need, in my opinion. – KT. Jan 03 '16 at 18:37
  • @KT. Yes, I agree. The "unescaping" is not the use case one need the `comonad` for. However it would be interesting to find a real "proper" application for that `comonad`... – Michael Jan 03 '16 at 18:43
  • @Michael, check this out: http://www.jucs.org/jucs_11_7/signals_and_comonads/jucs_11_7_1311_1327_vene.pdf The article does focus on streams, because mathematically a stream, being a corecursive type, is a clean model for anything infinite and "co-", while a list, being a recursive type, has an ending which needs to be handled as a special case. But this finiteness issue aside, wherever you see a comonad over a stream, you should be able to convert it into a comonad over a list just as well. ... I need to run now, an army of theoreticians is on to me for speaking dirty heresies. – KT. Jan 03 '16 at 18:55
  • @KT. Thanks a lot for the link. – Michael Jan 03 '16 at 20:23
  • Also I found a lot of useful insights in [these blog posts](http://blog.higher-order.com/blog/2015/06/23/a-scala-comonad-tutorial/) – pagoda_5b Apr 09 '16 at 01:44
  • @Michael This was near the top of Unanswered for me. Would it be in good taste to produce a relatively simple question, then provide most of your original question as the answer? (I.e. restate your question, then answer it yourself.) If you don't want the points for answering it yourself, you could mark it as community wiki. – eenblam Feb 18 '17 at 16:36
  • @J.Abrahamson This would address your concern about SO's format, while also getting it off the Unanswered list. – eenblam Feb 18 '17 at 16:38
  • 2
    @eenblam You are right. I will add an answer and it will get this question off the unanswered list, I hope – Michael Feb 18 '17 at 19:33

1 Answers1

2

As this question is popping up regularly in the top of the "unanswered" list, let me just copy my comment as an answer here - nothing considerably more constructive has appeared since a year ago anyway.

A List can be viewed as a comonad just as well (in multiple ways), while a Zipper can be cast as a monad (also in many ways). The difference is in whether you are conceptually focused on "appending" data constructively to a state machine (that's what the Monad interface is about), or "extracting" state from it "deconstructively" (that's what the Comonad does).

It is not easy to answer the question, stated as "does this understanding make sense", however. In some sense it does, in another it does not.

KT.
  • 10,815
  • 4
  • 47
  • 71