Saturday, February 11, 2012

Using Lawvere theories to combine effects


> import Data.Monoid
> import Data.Functor.Identity
> import Control.Monad.Writer




> class Free a b where
>   leaf :: a -> b

Effects from monoids


And we have:

> instance Monoid (FreeMonoid a) where
>   mempty = FreeMonoid mempty


> e1, e2 :: FreeMonoid Char



> instance Free a [a] where
>       leaf x = [x]

Here's the isomorphism (modulo tree equivalence):

> iso1 :: FreeMonoid a -> [a]
> iso1 (FreeMonoid x) = x

> iso1' :: [a] -> FreeMonoid a
> iso1' [] = FreeMonoid mempty
>                  in FreeMonoid (leaf a `mappend` r)


> test1 = do
>   a <- return 3 `mappend` return 4
>   b <- return 4 `mappend` return 5
>   c <- return 5 `mappend` return 6

Effects form M-sets
We can do exactly the same for -sets.

> class Monoid m => MSet m s where
>       act :: m -> s -> s



m `act` (leaf x)


>   leaf x = return x


> iso2 (FreeMSet x) = x



> test2 :: Writer String Int
> test2 = do
>   act "foo" (return ())
>   a <- return 2
>   act "bar" (return ())
>   b <- return (10*a)
>   return b

Combining effects



>   mempty = FreeMMonoid mempty



Apply mappend horizontally and act vertically to get:
m `act` (x `mappend` y)
Now apply act vertically and then mappend horizontally to get:
The law we want is:


>   mempty = WriterT []


>   leaf x = return x

Here's the isomorphism though we won't use it:

> iso3 (FreeMMonoid x) = x



>            `mappend`


> test3 = do
>   coin1 <- coin
>   coin2 <- coin


What just happened?

M-set with M-set


Monoid with monoid

The compatibility condition




Anonymous said...

I enjoyed reading these posts as well as reading all those old ones again. :)

Am I correct in understanding that having the compatibility conditions (as opposed to none) is in practice always what you want when combining monadic effects? Are there any examples where you'd naturally not want them, or where you'd want ad hoc compatibility conditions?

Tom said...

When you say "Leaf x1 `mappend` (Leaf x2 `mappend` (... mempty))" do you mean (lowercase) "leaf"?

migmit said...


We did? I haven't noticed. At least, I can't see an "instance Monad" anywhere.

Oh, maybe you mean that FreeMMonoid is also a monad? That's obviously true, but your claim that "the result was the same as using a monad transformer" is far from being true. FreeMMonoid is just a special case of a continuation monad (yes, I know, you've tried to hide this "a -> b" extra argument, but you didn't hide it well enough). It's a pretty useful trick, but it's NOT similar to anything like "WriterT w []". And this trick is not for monads only; you can combine pretty much everything in this way.

Also, Lawvere theories? That seems to be a HUGE overkill for that simple trick.

sigfpe said...


I'm a bit confused when you say FreeMMonoid is nothing similar to WriterT w [] when I show that one is essentially the other modulo equivalance with algebra laws. And as the title says, the goal is to combine effects, not monads. It just so happens that for this example there is some overlap with monads. And if you can combine other things this way, that's all well and good. And I've no intention of hiding the connections with continuations. And I'm not sure why Lawvere theories are overkill when the construction of the arrows from a Lawvere theory is, modulo equivalence, a line of Haskell. (What I did omit was the motivation for the definition of compatibility which is a small category diagram.)

migmit said...

It's a very, VERY big modulo. So, as I see it, that's what happened:

1) You've created some "combined monad" (I'll get to that part in a moment).

2) You showed that for any monad that satisfies some properties, there is a very natural map from your combined monad to that one.

3) You've discovered that a WriterT [] monad satisfies said properties.

4) So, you have a map from your combined monad to WriterT []. So far so good.

5) Based on that, you claim that your monad and WriterT [] are essentially the same. Sorry, but I don't buy it. There is just a map from one thing to another, it doesn't make them even remotely similar.

> the goal is to combine effects, not monads.

Well, you've explicitly said that you combined monads.

As for the construction of this "combined monad"... It's just a way to turn everything to anything. Whenever you have some type Foo, and you think "oh, how lovely it would be if it was an instance of class Bar", well, your last resort is to use continuations, defining newtype FooBar = FooBar (forall a. Bar a => (Foo -> a) -> a). Sure, it's a neat trick... but also a kind of admitting defeat, since it's so universal. It's kind of saying "I can't do it properly, but I'll do it anyway". Not that I've never done it myself - of course I did. But it's not justified by mentioning some clever theory (Lawvere theories this time) and then throwing away almost all of it (laws, this time). It feels like... cheating.

sigfpe said...


Maybe I haven't made something clear. I don't care about those FreeX types. They're just intermediate steps in the construction. The thing I want is the quotient. The FreeX types are just ways to construct the sets of arrows we need. But those types are useless for implementing effects without the quotient. I most certainly do admit defeat in the sense that I can't write code to automatically construct the appropriate quotient. But I can do it manually and that's what I illustrated.

I'm not using Lawvere theories to justify anything. I constructed the types for the combined effect by reading a paper on Lawvere theories and finding the closest approximating Haskell code. I then noticed that the construction, for this case, gave the same result as using monad transformers for the two effects. That doesn't necessarily happen every time.

I like this approach because the resulting type was determined uniquely given the two starting effects. Forming the monad transformer requires guesswork and in some sense, even if you make a guess that works for you, there's no definition against which you can check whether the thing you've constructed is in any sense the "right" one. (You can apply the transformer to the identity monad and see if you get back the original monad, but there can be multiple constructions with this property with no principled way of distinguishing between them.)

You can combine any two type classes described by algebraic laws this way. In some sense it's universal, but not all type classes are described by algebraic laws. That's not a trivial observation.

And I'll say again: the code for the FreeX classes is entirely useless. I was simply implementing in Haskell the halfway point in the mathematical construction. I could have left the halfway point entirely as mathematics and left out the FreeX type. But I think Haskell notation is better than the construction used in the mathematics papers. (Eg. compare Andrej's description of the arrows in terms of strings of symbols:

Gabriel Gonzalez said...

I thought that you could verify monad transformers were implemented correctly by checking the monad transformer laws, which are just the functor laws from the lower monad's Kleisli category to the higher monad's Kleisli category.

Joseph Abrahamson said...

@Gabriel Is there any guarantee of uniqueness, though?

Blog Archive