MonadTransformer is just a hacky Traversable, right?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
Xanthir
My HERO!!!
Posts: 5213
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

MonadTransformer is just a hacky Traversable, right?

Postby Xanthir » Fri Aug 07, 2015 10:30 pm UTC

So I'm gradually bootstrapping my FP knowledge higher by cross-referencing multiple instances of the same sorts of tutorials. I've built up a good intuition for Monads and Traversables, when I finally return to MonadTransformers.

To my untrained eye, it *looks* like this is just an early/clumsy attempt at introducing the concepts behind Traversable; I know that Traversable is a relatively recent addition to core Haskell. The entire purpose of a MonadTransformer is to provide a variant of certain monads that, when wrapped around arbitrary other monads, can "invert" itself inside of the other monad. So if you have A<B<value>>, and A is a MonadTransformer, it can turn itself into B<A<value>>. This is *precisely* what Traversable's sequence function does, in a more general fashion.

Am I right in this, and MonadTransformer would never exist if Haskell had Traversable early enough?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: MonadTransformer is just a hacky Traversable, right?

Postby benneh » Mon Aug 24, 2015 12:40 pm UTC

A monad is a thing which takes a type and gives you another type. So, using your notation, if "value" is a type and "B" is a monad, then "B<value>" is also a type.
A monad transformer, however, is something entirely different. A monad transformer takes a monad and gives you another monad. So if "B" is a monad and "A" is a monad transformer, then "A<B>" is a monad.
So your first example of "A<B<value>>" should really be something like "<A<B>><value>". Knowing that, you can see that your second example of "B<A<value>>" just doesn't really make any sense.

Do you know what kinds are? If so, that should make this easier to understand.

User avatar
Xanthir
My HERO!!!
Posts: 5213
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: MonadTransformer is just a hacky Traversable, right?

Postby Xanthir » Tue Aug 25, 2015 10:52 am UTC

Yes, I'm well aware of all of that. MonadTransformer is equivalent to the Compose functor; it wraps two monads up into a single one. I'm well aware of types, kinds, and all the rest of this. ^_^

It's just that functors and applicatives compose arbitrarily (thus the existence of the Compose functor and applicative). Monads don't compose arbitrarily. We have an older solution of MonadTransformer, which lets *some* monads compose. We have a newer concept of Traversable, and it seems that traversable monads have the same arbitrary composability, and are easier to typeclass against to boot, because then you don't have to write your functions to ask for a MonadTransformer - you can just write a Compose monad that requires the "inner" one to be Traversable, and then pass the result to anything that wants a monad.

I just haven't seen this sort of thing stated explicitly yet, and I'm wondering if this is because I'm wrong, or if it just hasn't percolated out sufficiently well yet to show up in tutorials. I refuse to believe I'm the first to actually think of it.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: MonadTransformer is just a hacky Traversable, right?

Postby benneh » Tue Aug 25, 2015 7:25 pm UTC

Xanthir wrote:MonadTransformer is equivalent to the Compose functor; it wraps two monads up into a single one.

That's not always the case. For example, the StateT monad transformer has the following definition:

Code: Select all

newtype StateT s m a = StateT { runStateT :: s -> m (a,s) }
Thus "StateT s m a" is not the same as "State s (m a)" or "m (State s a)".

For some monad transformers (e.g. MaybeT) it is the case that the 'transformation' is just composition with the base monad (e.g. Maybe) and putting a monad structure on that composite, but not always.

But even when that is the case, there isn't really anything analogous to Traversable's sequence. For example, MaybeT is defined as follows:

Code: Select all

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }
And the only extra data you get by virtue of it being a monad transformer is lift:

Code: Select all

lift :: m a -> MaybeT m a
So even though MaybeT m a is just the composite m (Maybe a), you don't get any way to translate between m (Maybe a) and Maybe (m a).


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests