سؤال

I know what a monad is. I think I have correctly wrapped my mind around what a comonad is. (Or rather, what one is seems simple enough; the tricky part is comprehending what's useful about this...)

My question is: Can something be a monad and a comonad?

I foresee two possible answers:

  • Yes, this is common and widely useful.
  • No, they do such different jobs that there would be no reason to want something to be both.

So, which is it?

هل كانت مفيدة؟

المحلول 2

Yes. Turning some comments into an answer:

newtype Identity a = Identity {runIdenity :: a} deriving Functor
instance Monad Identity where
  return = Identity
  join = runIdentity
instance CoMonad Identity where
  coreturn = runIdentity
  cojoin = Identity

Reader and Writer are exact duals, as shown by

class CoMonoid m where
  comempty :: (m,a) -> a
  comappend :: m -> (m,m)
--every haskell type is a CoMonoid
--that is because CCCs are boring!

instance Monoid a => Monad ((,) a) where
  return x = (mempty,x)
  join (a,(b,x)) = (a <> b, x)
instance CoMonoid a => CoMonad ((,) a) where
  coreturn = comempty
  cojoin = associate . first comappend

instance CoMonoid a => Monad ((->) a) where
  return = flip (curry comempty)
  join f = uncurry f . comappend
instance Monoid a => CoMonad ((->) a)  where
  coreturn f = f mempty
  cojoin f a b = f (a <> b)

نصائح أخرى

The Cofree Comonad yields some data structures that are useful as Monads and Comonads both:

data Cofree f a = a :< f (Cofree f a)

Every Cofree Comonad over an Alternative functor yields a Monad -- see the instance here:

http://hackage.haskell.org/packages/archive/free/3.4.1/doc/html/Control-Comonad-Cofree.html

instance Alternative f => Monad (Cofree f) where
  return x = x :< empty
  (a :< m) >>= k = case k a of
                     b :< n -> b :< (n <|> fmap (>>= k) m)

This gives us, e.g. nonempty lists as Monads and Comonads both (along with nonempty f-branching trees, etc).

Identity is not an alternative, but Cofree Identity yields an infinite stream, and we can in fact give a different monad instance to that stream:

http://hackage.haskell.org/packages/archive/streams/3.1/doc/html/Data-Stream-Infinite.html

data Stream a = a :> Stream a
instance Comonad Stream where
  duplicate = tails
  extend f w = f w :> extend f (tail w)
  extract = head

instance Monad Stream where
  return = repeat
  m >>= f = unfold (\(bs :> bss) -> (head bs, tail <$> bss)) (fmap f m)

(note the functions above are not on lists but instead defined in the streams package).

Similarly the reader arrow is not an alternative, but Cofree ((->) r) yields a Moore machine, and Moore machines also are monads and comonads both:

http://hackage.haskell.org/packages/archive/machines/0.2.3.1/doc/html/Data-Machine-Moore.html

data Moore a b = Moore b (a -> Moore a b)
instance Monad (Moore a) where
  return a = r where r = Moore a (const r)
  Moore a k >>= f = case f a of
    Moore b _ -> Moore b (k >=> f)
  _ >> m = m
instance Comonad (Moore a) where
  extract (Moore b _) = b
  extend f w@(Moore _ g) = Moore (f w) (extend f . g)

So what's the intuition behind all these examples? Well we get the comonadic operations for free. The monadic operations we get are all forms of diagonalization. With alternative we can <|> things together to "smush" the structure, and magic up "empty" things when we run out of structure to smush. This lets us work on finite cases. Lacking alternative we need to have an indefinite amount of structure, so that no matter how many "join" operations (which we can think of as splicing or substitution) that we make, there's always more room to place the spliced elements (like at the Hilbert Hotel: http://www.encyclopediaofmath.org/index.php/Hilbert_infinite_hotel).

Relatedly, every Comonad gives rise to a related Monad (although I consider this more a curiousity):

http://hackage.haskell.org/packages/archive/kan-extensions/3.1.1/doc/html/Control-Monad-Co.html

http://comonad.com/reader/2011/monads-from-comonads/

There are many interesting structures that are both a Monad and a Comonad.

The Identity functor has been pointed out here by several other people, but there are non-trivial examples.

The Writer Monad plays a Reader-like role as a Comonad.

instance Monoid e => Monad ((,) e)
instance Comonad ((,) e)

The Reader Monad plays a Writer-like role as a Comonad.

instance Monad ((->) e)
instance Monoid e => Comonad ((->)e)

Non-empty lists also form both a monad and a comonad and are in fact a special case of a larger construction involving cofree comonads. The Identity case can also be seen as a special case of this.

There are also various Yoneda and Codensity-like constructions based on Kan extensions, that work to transform monads and comonads, although they favor one or the other in terms of operational efficiency.

I also have an adapter that converts an arbitrary comonad into a monad transformer. Sadly the opposite conversion isn't possible in Haskell.

In linear algebra there is a notion of a bialgebra. Ideally if we have something that forms both a Monad and a Comonad and we want to use those operations together without reasoning on a case-by-case basis, one would like to have that return and join are Comonad coalgebras and by extension that extract and duplicate are Monad algebras. If those conditions hold then you can actually reason about code that has both Monad f and Comonad f constraints and mixes the combinators from each without case-by-case reasoning.

It depends on what you consider a "monad" to be. If you ask "is it possible for a type to be an instance of both Monad and Comonad at once?" then, yes. Here's a trivial example.

newtype Id a = Id a

instance Monad Identity where
  return       = Id
  (Id a) >>= f = f a

instance Comonad Identity where
  extract (Id a) = a
  extend f ida = Id (f ida)

If you mean it mathematically, then a monad is a triple (X, return, bind) where X is a type and return and bind follow the types and laws you expect. Similarly, a comonad is (X, extend, extract). I've just demonstrated that the Xs might be the same, but since the types of extend and return or extract and bind are different it's not possible for them to be the same functions. So a mathematical monad can never be a comonad.

Expanding on Hammer's suggestion, it seems simple enough to write a function [x] -> [[x]]. For example,

map (\ x -> [x])

would work just fine. So it looks like lists could form a comonad. Ah, but wait. That handles cojoin, but what about coreturn :: [x] -> x? This, presumably, is why only non-empty lists form a comonad.

This gives us a cobind function with the type ([x] -> x) -> [x] -> [x]. Interestingly, Hoogle knows of no such function. And yet we already have concatMap :: (x -> [x]) -> [x] -> [x]. I'm not seeing an immediate use for the cobind function, but I can imagine one existing.

I'm still trying to wrap my mind around comonad and what it might be useful for. The answers so far have given me something to think about...

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top