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

Xanthir
My HERO!!!
Posts: 5311
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

MonadTransformer is just a hacky Traversable, right?

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.

(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: MonadTransformer is just a hacky Traversable, right?

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.
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.

Xanthir
My HERO!!!
Posts: 5311
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

Re: MonadTransformer is just a hacky Traversable, right?

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)))

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

Re: MonadTransformer is just a hacky Traversable, right?

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).