The “reader” monad

Question

OK, so the writer monad allows you to write stuff to [usually] some kind of container, and get that container back at the end. In most implementations, the "container" can actually be any monoid.

Now, there is also a "reader" monad. This, you might think, would offer the dual operation - incrementally reading from some kind of container, one item at a time. In fact, this is not the functionality that the usual reader monad provides. (Instead, it merely offers easy access to a semi-global constant.)

To actually write a monad which is dual to the usual writer monad, we would need some kind of structure which is dual to a monoid.

1. Does anybody have any idea what this dual structure might be?
2. Has anybody written this monad? Is there a well-known name for it?

Answer 1

Supply is based on State, which makes it suboptimal for some applications. For example, we might want to make an infinite tree of supplied values (e.g. randoms):

tree :: (Something r) => Supply r (Tree r)
tree = Branch <$> supply <*> sequenceA [tree, tree]

But since Supply is based on State, all the labels will be bottom except for the ones one the leftmost path down the tree.

You need something splittable (like in @PhillipJF's Comonoid). But there is a problem if you try to make this into a Monad:

newtype Supply r a = Supply { runSupply :: r -> a }

instance (Splittable r) => Monad (Supply r) where
    return = Supply . const
    Supply m >>= f = Supply $ \r ->
        let (r',r'') = split r in
        runSupply (f (m r')) r''

Because the monad laws require f >>= return = f, so that means that r'' = r in the definition of (>>=).. But, the monad laws also require that return x >>= f = f x, so r' = r as well. Thus, for Supply to be a monad, split x = (x,x), and thus you've got the regular old Reader back again.

A lot of monads that are used in Haskell aren't real monads -- i.e. they only satisfy the laws up to some equivalence relation. E.g. many nondeterminism monads will give results in a different order if you transform according to the laws. But that's okay, that's still monad enough if you're just wondering whether a particular element appears in the list of outputs, rather than where.

If you allow Supply to be a monad up to some equivalence relation, then you can get nontrivial splits. E.g. value-supply will construct splittable entities which will dole out unique labels from a list in an unspecified order (using unsafe* magic) -- so a supply monad of value supply would be a monad up to permutation of labels. This is all that is needed for many applications. And, in fact, there is a function

runSupply :: (forall r. Eq r => Supply r a) -> a

which abstracts over this equivalence relation to give a well-defined pure interface, because the only thing it allows you to do to labels is to see if they are equal, and that doesn't change if you permute them. If this runSupply is the only observation you allow on Supply, then Supply on a supply of unique labels is a real monad.

Answer 2

I'm not entirely sure of what the dual of a monoid should be, but thinking of dual (probably incorrectly) as the opposite of something (simply on the basis that a Comonad is the dual of a Monad, and has all the same operations but the opposite way round). Rather than basing it on mappend and mempty I would base it on:

fold :: (Foldable f, Monoid m) => f m -> m

If we specialise f to a list here, we get:

fold :: Monoid m => [m] -> m

This seems to me to contain all of the monoid class, in particular.

mempty == fold []
mappend x y == fold [x, y]

So, then I guess the dual of this different monoid class would be:

unfold :: (Comonoid m) => m -> [m]

This is a lot like the monoid factorial class that I have seen on hackage here.

So on this basis, I think the 'reader' monad you describe would be a supply monad. The supply monad is effectively a state transformer of a list of values, so that at any point we can choose to be supplied with an item from the list. In this case, the list would be the result of unfold.supply monad

I should stress, I am no Haskell expert, nor an expert theoretician. But this is what your description made me think of.

Answer 3

The dual of a monoid is a comonoid. Recall that a monoid is defined as (something isomorphic to)

 class Monoid m where
    create :: () -> m
    combine :: (m,m) -> m

with these laws

 combine (create (),x) = x
 combine (x,create ()) = x
 combine (combine (x,y),z) = combine (x,combine (y,z))

thus

 class Comonoid m where
    delete :: m -> ()
    split :: m -> (m,m)

some standard operations are needed

 first :: (a -> b) -> (a,c) -> (b,c)
 second :: (c -> d) -> (a,c) -> (a,d)

 idL :: ((),x) -> x
 idR :: (x,()) -> x

 assoc :: ((x,y),z) -> (x,(y,z))

with laws like

idL $ first delete $ (split x) = x
idR $ second delete $ (split x) = x
assoc $ first split (split x) = second split (split x)

This typeclass looks weird for a reason. It has an instance

instance Comonoid m where
   split x = (x,x)
   delete x = ()

in Haskell, this is the only instance. We can recast reader as the exact dual of writer, but since there is only one instance for comonoid, we get something isomorphic to the standard reader type.

Having all types be comonoids is what makes the category "Cartesian" in "Cartesian Closed Category." "Monoidal Closed Categories" are like CCCs but without this property, and are related to substructural type systems. Part of the appeal of linear logic is the increased symmetry that this is an example of. While, having substructural types allows you to define comonoids with more interesting properties (supporting things like resource management). In fact, this provides a framework for understand the role of copy constructors and destructors in C++ (although C++ does not enforce the important properties because of the existence of pointers).

EDIT: Reader from comonoids

newtype Reader r x = Reader {runReader :: r -> x}
forget :: Comonoid m => (m,a) -> a
forget = idL . first delete

instance Comonoid r => Monad (Reader r) where
   return x = Reader $ \r -> forget (r,x)
   m >>= f = \r -> let (r1,r2) = split r in runReader (f (runReader m r1)) r2

ask :: Comonoid r => Reader r r
ask = Reader id

note that in the above code every variable is used exactly once after binding (so these would all type with linear types). The monad law proofs are trivial, and only require the comonoid laws to work. Hence, Reader really is dual to Writer.