Comonad is just a dual of a monad. Super simple ;-). We could represent monad as a type with a pair of functions

We need return function to convert any value to a monad and bind function to apply a function which returns monad to a monad. Or in different words we have functions like ‘a -> M<’b> and want to compose them with a » operator. To do that we need to use this pattern (bind f) » (bind f2) … And to convert any function ‘a -> ‘b to a function like ‘a -> Monad<’b> we have to use f » return’ so finally we could compose functions

And comonad is inverse type with a pair of function extract and extend

And composition looks like this

We need them when we have to use some additional context in our functions. For example, we could use additional execution context like we do in a reader monad.

And we could represent any non-empty collection with attached index as a comonad. Let’s implement a tiny image processing library as an example. Image(grayscale) will be represented as an 2d array of ints with i and j indexes. But array could be empty, how could we fix that? We could simply return default value when there is nothing to extract. We need two array helper functions:

Some code for image loading.

And a module for our comonad (array with indexes). In a module we have to define our comonad type, extract function which returns a value from the array using current position, extend function which works like a standard array’s mapi function. Also we have to define get function which uses additional, relative to a current position, indexes.

Now it is time for image filters. Usually a filter represented as a function which takes our comonadic value and uses function “get” and/or “extract” to calculate output value of current position based on values from current position and probably additional positions near of current position(neighbors).

Now we could build additional filter by composing existing ones.

And now we could run our code using collection of test images.

Let’s execute it. Oh no it takes too long to execute some filters. What is the problem? After investigation we could find that complexity of extract function is O(1) and complexity of extend function is O(N). So in case of composition “extend extract » extend extract” final complexity is O(N) and this is ok. But in case of “extend (extend extract » extract)” complexity is O(N^2). So if we want to compose our functions we have to remove this complexity growth or prevent extending of extended functions. First way could be done by implementing array as a lazy array.

And yes this way works, there is no fast complexity growth, but in terms of raw performance it is far from ideal. Because there is a lot of duplicate calls to underlying filters. So ideal solution is to use arrays but prevent, somehow, incorrect composition. And this can be done with phantom types.

It is just an additional type variable in generic type, which is used only in type declarations. Usually it is used to add some compile time checks. So let’s add phantom type to our comonad.

A type variable ‘p is a place where we will put our marker types

Raw type will be used to mark comonad with complexity O(1) and Composed marker will be applied to comonads returned by extend function with complexity O(N) and extend function as an input will accept only composed comonad and argument function will be restricted to a funcs which accept only raw comonad.

Now every line in our code where we used incorrect composition will be marked as an error. For example, gaussLaplace will be marked with error: the type Composed doesn’t match the type Raw. Let’s fix it.

Now it works as expected. For example, on my machine contours filter: First version takes a lot of time (x minutes) to execute. Lazy version takes about 16s. Final version takes about 242ms.