CODEWITHSUNDEEP
haskellmonadsmonad-transformers
QuantumWiz
QuantumWiz

Reputation: 287

Is the monad transformer of a monad unique in Haskell?

There have been a couple of questions (e.g. this and this) asking whether every monad in Haskell (other than IO) has a corresponding monad transformer. Now I would like to ask a complementary question. Does every monad have exactly one transformer (or none as in the case of IO) or can it have more than one transformer?

A counterexample would be two monad transformers that would produce monads behaving identically when applied to the identity monad would but would produce differently behaving monads when applied to some other monad. If the answer is that a monad can have more than one transformer I would like to have a Haskell example which is as simple as possible. These don't have to be actually useful transformers (though that would be interesting).

Some of the answers in the linked question seemed to suggest that a monad could have more than one transformer. However, I don't know much category theory beyond the basic definition of a category so I wasn't sure whether they are an answer to this question.

Upvotes: 4

Views: 387

Answers (3)

winitzki
winitzki

Reputation: 3347

There is another example of a monad that has two inequivalent transformers: the "selection" monad.

 type Sel r a = (a -> r) -> a

The monad is not well known but there are papers that mention it. Here is a package that refers to some papers:

https://hackage.haskell.org/package/transformers-0.6.0.4/docs/Control-Monad-Trans-Select.html

That package implements one transformer:

type SelT r m a = (a -> m r) -> m a

But there exists a second transformer:

type Sel2T r m a = (m a -> r ) -> m a

Proving laws for this transformer is more difficult but I have done it.

An advantage of the second transformer is that it is covariant in m, so the hoist function can be defined:

 hoist :: (m a -> n a) -> Sel2T r m a -> Sel2T r n a

The second transformer is "fully featured", has all lifts and "hoist". The first transformer is not fully featured; for example, you cannot define blift :: Sel r a -> SelT r m a. In other words, you cannot embed monadic computations from Sel into SelT, just like you can't do that with the Continuation monad and the Codensity monad.

But with the Sel2T transformer, all lifts exist and you can embed Sel computations into Sel2T.

This example shows a monad with two transformers without using the Codensity construction in any way.

Upvotes: 1

Li-yao Xia
Li-yao Xia

Reputation: 33519

The identity monad has at least two monad transformers: the identity monad transformer and the codensity monad transformer.

newtype IdentityT m a = IdentityT (m a)
newtype Codensity m a = Codensity (forall r. (a -> m r) -> m r)

Indeed, considering Codensity Identity, forall r. (a -> r) -> r is isomorphic to a.

These monad transformers are quite different. One example is that "bracket" can be defined as a monadic action in Codensity:

bracket :: Monad m => m () -> m () -> Codensity m ()
bracket before after = Codensity (\k -> before *> k () *> after)

whereas transposing that signature to IdentityT doesn't make much sense

bracket :: Monad m => m () -> m () -> IdentityT m ()  -- cannot implement the same functionality

Other examples can be found similarly from variants of the continuation/codensity monad, though I don't see a general scheme yet.

The state monad corresponds to the state monad transformer and to the composition of Codensity and ReaderT:

newtype StateT s m a = StateT (s -> m (s, a))
newtype CStateT s m a = CStateT (Codensity (ReaderT s m) a)

The list monad corresponds to at least three monad transformers, not including the wrong one:

newtype ListT m a = ListT (m (Maybe (a, ListT m a)))  -- list-t
newtype LogicT m a = LogicT (forall r. (a -> m r -> m r) -> m r -> m r)  -- logict
newtype MContT m a = MContT (forall r. Monoid r => (a -> m r) -> m r))

The first two can be found respectively in the packages list-t (also in an equivalent form in pipes), and logict.

Upvotes: 1

Daniel Wagner
Daniel Wagner

Reputation: 153172

Here's one idea for a counterexample to uniqueness. We know that in general, monads don't compose... but we also know that if there's an appropriate swap operation, you can compose them[1]! Let's make a class for monads that can swap with themselves.

-- | laws (from [1]):
-- swap . fmap (fmap f) = fmap (fmap f) . swap
-- swap . pure = fmap pure
-- swap . fmap pure = pure
-- fmap join . swap . fmap (join . fmap swap) = join . fmap swap . fmap join . swap
class Monad m => Swap m where
    swap :: m (m a) -> m (m a)

instance Swap Identity where swap = id
instance Swap Maybe where
    swap Nothing = Just Nothing
    swap (Just Nothing) = Nothing
    swap (Just (Just x)) = Just (Just x)

Then we can build a monad transformer that composes a monad with itself, like so:

newtype Twice m a = Twice (m (m a))

Hopefully it should be obvious what pure and (<$>) do. Rather than defining (>>=), I'll define join, as I think it's a bit more obvious what's going on; (>>=) can be derived from it.

instance Swap m => Monad (Twice m) where
    join = id
        . Twice                        -- rewrap newtype
        . fmap join . join . fmap swap -- from [1]
        . runTwice . fmap runTwice     -- unwrap newtype

instance MonadTrans Twice where lift = Twice . pure

I haven't checked that lift obeys the MonadTrans laws for all Swap instances, but I did check them for Identity and Maybe.

Now, we have

IdentityT Identity ~= Identity ~= Twice Identity
IdentityT Maybe    ~= Maybe   !~= Twice Maybe

which shows that IdentityT is not a unique monad transformer for producing Identity.

[1] Composing monads by Mark P. Jones and Luc Duponcheel

Upvotes: 3

Related Questions