Comonads: what are they and what can you do with them?
Melbourne Haskell Users GroupDavid Overton

29 May 2014

Table of Contents

1 Motivation
2 Theory
3 Examples
4 Applications
5 Other Considerations
6 Further ReadingMotivation• Monads are an abstract concept from category theory, have turned out to be

surprisingly useful in functional programming.
• Category theory also says that there exists a dual concept called comonads. Can

they be useful too?
• Intuition:• Monads abstract the notion of effectful computation of a value.
• Comonads abstract the notion of a value in a context.
• “Whenever you see large datastructures pieced together from lots of small but

similar computations there’s a good chance that we’re dealing with a comonad.”—Dan Piponi

Table of Contents

1 Motivation
2 Theory
3 Examples
4 Applications
5 Other Considerations
6 Further ReadingWhat is a Comonad?

• A comonad is just a comonoid in the category of endofunctors. . .
• A comonad is the category theoretic dual of a monad.
• A comonad is a monad with the “arrows” reversed.

What is a Comonad?
Both monads and comonads are functors. (Functor is its own dual.)class Functor f wherefmap :: (a → b) → (f a → f b)class Functor m ⇒ Monad m wherereturn :: a → m abind :: (a → m b) → (m a → m b)
join :: m (m a) → m ajoin = bind id
bind f = fmap f ◦ join(>>=) :: m a → (a → m b) → m b(>>=) = flip bindclass Functor w ⇒ Comonad w whereextract :: w a → aextend :: (w b → a) → (w b → w a)
duplicate :: w a → w (w a)duplicate = extend id
extend f = fmap f ◦ duplicate(=>>) :: w b → (w b → a) → w a(=>>) = flip extend

Intuition• Monadic values are typically produced in effectful computations:a → m b• Comonadic values are typically consumed in context-sensitive computations:w a → b

Monad/comonad laws

Monad laws
Left identity
Right identify
Associativity

return ◦ bind fbind returnbind f ◦ bind g=f= id= bind (f ◦ bind g)

Comonad laws
Left identity
Right identity
Associativity

extract ◦ extend f
extend extract
extend f ◦ extend g=f= id= extend (f ◦ extend g)

Table of Contents

1 Motivation
2 Theory
3 Examples
4 Applications
5 Other Considerations
6 Further Reading

Example: reader/writer duality-- Reader monadinstance Monad ((→) e) wherereturn = const
bind f r = λc → f (r c) c-- CoReader (a.k.a. Env) comonadinstance Comonad ((,) e) whereextract = snd
extend f w = (fst w, f w)-- Writer monadinstance Monoid e ⇒ Monad ((,) e)
where
return = ((,) mempty)
bind f (c, a) = (c ♦ c’, a’)where (c’, a’) = f a-- CoWriter (a.k.a. Traced) comonadinstance Monoid e ⇒ Comonad ((→) e)
where
extract m = m mempty
extend f m = λc →f (λc’ → m (c ♦ c’))

Example: state
newtype State s a = State { runState :: s → (a, s) }instance Monad (State s) wherereturn a = State $ λs → (a, s)bind f (State g) = State $ λs →let (a, s’) = g s
in runState (f a) s’data Store s a = Store (s → a) s -- a.k.a. ‘‘Costate’’instance Comonad (Store s) whereextract (Store f s) = f s
extend f (Store g s) = Store (f ◦ Store g) s

One definition of Lens:
type Lens s a = a → Store s a

Hence the statement that lenses are “the coalgebras of the costate comonad”.

Example: stream comonaddata Stream a = Cons a (Stream a)instance Functor Stream wherefmap f (Cons x xs) = Cons (f x) (fmap f xs)
instance Comonad Stream where)=x
extract (Cons x
duplicate xs@(Consxs’) = Cons xs (duplicate xs’)
extend f xs@(Consxs’) = Cons (f xs) (extend f xs’)
• extract = head, duplicate = tails.
• extend extends the function f :: Stream a → b by applying it to all tails of
stream to get a new Stream b.
• extend is kind of like fmap, but instead of each call to f having access only to asingle element, it has access to that element and the whole tail of the list fromthat element onwards, i.e. it has access to the element and a context.

Example: list zipper
data Z a = Z [a] a [a]left, right :: Z a → Z aleft (Z (l:ls) a rs) = Z ls l (a:rs)
right (Z ls a (r:rs)) = Z (a:ls) r rs
instance Functor Z wherefmap f (Z l a r) = Z (fmap f l) (f a) (fmap f r)
iterate1 :: (a → a) → a → [a]iterate1 f = tail ◦ iterate f
instance Comonad Z whereextract (Za )=aduplicate z = Z (iterate1 left z) z (iterate1 right z)
extend f z = Z (fmap f $ iterate1 left z) (f z)(fmap f $ iterate1 right z)

Example: list zipper (cont.)• A zipper for a data structure is a transformed structure which gives you a focus

element and a means of stepping around the structure.
• extract returns the focused element.
• duplicate returns a zipper where each element is itself a zipper focused on thecorresponding element in the original zipper.
• extend is kind of like fmap, but instead of having access to just one element, eachcall to f has access to the entire zipper focused at that element. I.e. it has thewhole zipper for context.
• Compare this to the Stream comonad where the context was not the wholestream, but only the tail from the focused element onwards.
• It turns out that every zipper is a comonad.

Example: array with context
data CArray i a = CA (Array i a) i
instance Ix i ⇒ Functor (CArray i) wherefmap f (CA a i) = CA (fmap f a) i
instance Ix i ⇒ Comonad (CArray i) whereextract (CA a i) = a ! iextend f (CA a i) =let es’ = map (λj → (j, f (CA a j))) (indices a)in CA (array (bounds a) es’) i• CArray is basically a zipper for Arrays.
• extract returns the focused element.
• extend provides the entire array as a context.

Table of Contents

1 Motivation
2 Theory
3 Examples
4 Applications
5 Other Considerations
6 Further Reading

Application: 1-D cellular automata – Wolfram’s rules
rule :: Word8 → Z Bool → Boolrule w (Z (a: ) b (c: )) = testBit w (sb 2 a .|. sb 1 b .|. sb 0 c) where
sb n b = if b then bit n else 0
move :: Int → Z a → Z amove i u = iterate (if i < 0 then left else right) u !! abs itoList :: Int → Int → Z a → [a]toList i j u = take (j - i) $ half $ move i u where
half (Zb c) = b : c
testRule :: Word8 → IO ()testRule w = let u = Z (repeat False) True (repeat False)in putStr $ unlines $ take 20 $
map (map (λx → if x then ’#’ else ’ ’) ◦ toList (-20) 20) $iterate (=>> rule w) uApplication: 2-D cellular automata – Conway’s Game of Life

data Z2 a = Z2 (Z (Z a))instance Functor Z2 wherefmap f (Z2 z) = Z2 (fmap (fmap f) z)
instance Comonad Z2 whereextract (Z2 z) = extract (extract z)
duplicate (Z2 z) = fmap Z2 $ Z2 $ roll $ roll z whereroll a = Z (iterate1 (fmap left) a) a (iterate1 (fmap right) a)Application: 2-D cellular automata – Conway’s Game of LifecountNeighbours :: Z2 Bool → Int
countNeighbours (Z2 (Z(Z (n0: ) n1 (n2: ): )(n4: ))(Z (n3: )(Z (n5: ) n6 (n7: ): ))) =length $ filter id [n0, n1, n2, n3, n4, n5, n6, n7]life :: Z2 Bool → Boollife z = (a && (n == 2 | | n == 3))| | (not a && n == 3) wherea = extract z
n = countNeighbours z

Application: image processing
laplace2D :: CArray (Int, Int) Float → Float
laplace2D a = a ? (-1, 0)+ a ? (0, 1)+ a ? (0, -1)+ a ? (1, 0)- 4 ∗ a ? (0, 0)(?) :: (Ix i, Num a, Num i) ⇒ CArray i a → i → a
CA a i ? d = if inRange (bounds a) (i + d) then a ! (i + d) else 0• laplace2D computes the Laplacian at a single context, using the focused element

and its four nearest neighbours.
• extend laplace2D computes the Laplacian for the entire array.
• Output of extend laplace2D can be passed to another operator for furtherprocessing.

Application: Env (CoReader) for saving and reverting to an initial value
type Env e a = (e, a)
ask :: Env e a → e
ask = fst
local :: (e → e’) → Env e a → Env e’ alocal f (e, a) = (f e, a)
initial = (n, n) where n = 0
experiment = fmap (+ 10) initial
result = extract experimentinitialValue = extract (experiment =>> ask)Other applications of comonads• Signal processing: using a stream comonad.
• Functional reactive programming: it has been postulated (e.g. by Dan Piponi,Conal Elliott) that some sort of “causal stream” comonad should work well forFRP, but there don’t yet seem to be any actual implementations of this.
• Gabriel Gonzalez’s three examples of “OO” design patterns:• The Builder pattern: using CoWriter / Traced to build an “object” step-by-step.
• The Iterator pattern: using Stream to keep a history of events in reverse

chronological order.
• The Command pattern: using Store to represent an “object” with internal state.

Table of Contents

1 Motivation
2 Theory
3 Examples
4 Applications
5 Other Considerations
6 Further Reading

Syntactic sugar
At least two different proposals for a comonadic equivalent of do notation forcomonads:• Gonzalez’s method notation – “OOP-like” with this keyword representing theargument of the function passed to extend.
• Orchard & Mycroft’s codo notation – resembles Paterson’s arrow notation.

UnsugaredGonzalez

Orchard & Mycroft

λwa →let wb = extend (λthis → expr1) wa
wc = extend (λthis → expr2) wb
in(λthis → expr3) wc
λwa →let wb = extend func1 wa
wc = extend func2 wb
infunc3 wc

methodwa> expr1
wb> expr2
wc> expr3
methodwa> func1 thiswb> func2 thiswc> func3 thiscodo wa ⇒wb ← λthis → expr1
wc ← λthis → expr2
λthis → expr3
codo wa ⇒wb ← func1
wc ← func2
func3

Comonad transformers-- Monad transformers
class MonadTrans t wherelift :: Monad m ⇒ m a → t m a-- Comonad transformers
class ComonadTrans t where
lower :: Comonad w ⇒ t w a → w a

The comonad package provides a few standard transformers:• EnvT – analogous to ReaderT• StoreT – analogous to StateT• TracedT – analogous to WriterTCofree comonads-- Free monaddata Free f a = Pure a | Free (f (Free f a))
instance Functor f ⇒ Monad (Free f) wherereturn = Purebind f (Pure a) = f abind f (Free r) = Free (fmap (bind f) r)-- Cofree comonaddata Cofree f a = Cofree a (f (Cofree f a))
instance Functor f ⇒ Comonad (Cofree f) whereextract (Cofree a ) = a
extend f w@(Cofreer) = Cofree (f w) (fmap (extend f) r)• Cofree Identity is an infinite stream.
• Cofree Maybe is a non-empty list.
• Cofree [] is a rose tree.

A bit of category theory-- Kleisli category identity and composition (monads)
return :: Monad m ⇒ a → m a(>=>) :: Monad m ⇒ (a → m b) → (b → m c) → (a → m c)
f >=> g = λa → f a >>= g-- Co-Kleisli category identity and composition (comonads)
extract :: Comonad w ⇒ w a → a(=>=) :: Comonad w ⇒ (w a → b) → (w b → c) → (w a → c)f =>= g = λw → f w =>> g• Each monad has a corresponding Kleisli category with morphisms a → m b,
identity return and composition operator (>=>).
• Each comonad has a corresponding Co-Kleisli category with morphisms w a → b,identity extract and composition operator (=>=).

Category laws
Monad laws
Left identity
Right identify
Associativity

return >=> f
f >=> return(f >=> g) >=> h=f=f= f >=> (g >=> h)extract =>= f
f =>= extract(f =>= g) =>= h=f=f= f =>= (g =>= h)Comonad laws
Left identity
Right identify
Associativity

Category laws
Left identity
Right identify
Associativity

id ◦ ff ◦ id(f ◦ g) ◦ h=f=f= f ◦ (g ◦ h)

Table of Contents

1 Motivation
2 Theory
3 Examples
4 Applications
5 Other Considerations
6 Further ReadingFurther reading• http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html• http://blog.sigfpe.com/2008/03/comonadic-arrays.html• http://blog.sigfpe.com/2008/03/transforming-comonad-with-monad.html• http://blog.sigfpe.com/2014/05/cofree-meets-free.html• https://www.fpcomplete.com/user/edwardk/cellular-automata• http://www.jucs.org/jucs_11_7/signals_and_comonads/jucs_11_7_1311_1327_
vene.pdf• http://www.haskellforall.com/2013/02/you-could-have-inventedcomonads.html• http://www.cl.cam.ac.uk/~dao29/publ/codo-notation-orchard-ifl12.pdf• http://conal.net/blog/tag/comonad