monad-embed

The unimaginatively named monad-embed is a toy functional programming language for experimenting with a new way of using monads. Its goals are to make monadic code less verbose and to encourage programmers to use monads in ways that they normally wouldn't consider. It is not so useful for writing pure code because it breaks referential transparency and laziness, so it cannot replace Haskell, but its concepts might be useful in a Haskell-like language.

An example

plusOrMinus = either [plus] [minus];

quadraticFormula = \ a b c ->
    (negate b `plusOrMinus` sqrt (
        (b `times` b) `minus` (4 `times` a `times` c)
        )) `divide` (2 `times` a);

The main idea

Monads are so useful that Haskell programmers often parameterize their code on an underlying monad. mapM and filterM are map and filter parameterized on a monad. Similarly, monad transformers parameterize a monad on another monad.

monad-embed takes this idea the rest of the way by parameterizing everything on a monad by default. In Haskell, every term has a type of kind *; in monad-embed, every term has a flavor, a monad of kind * -> *, in addition to its type. The reduction of the term is described in terms of the return and (>>=) operations of the term's flavor. The details of the conversion process are here.

For example, here is the definition of the filter function:

filter :: (f :: * -> *, a :: *) => {f} (a -> Bool) -> List a -> List a;
filter = \ pred list -> case list of {
    Nil -> Nil;
    Cons x xs -> case pred x of {
        True -> x `Cons` filter pred xs;
        False -> filter pred xs;
        };
    };

Here, f is flavor of filter. The curly braces "{}" in the type signature of filter indicate its flavor.

The important thing to notice about this definition is that it looks like the Haskell definition of filter. Except for the "{f}" bit (and the fact that monad-embed has ugly syntax and lacks kind inference at the moment), the monad-embed definition of filter is identical to the Haskell definition of filter.

Despite being almost as simple to define as Haskell's filter, monad-embed's filter can do everything that Haskell's filterM can do. For example, here is a function to compute power sets using filter and the list monad (in the form of the ZList monad transformer). This example assumes that you understand how to compute power sets using filterM in Haskell.

powerset :: (g :: * -> *, a :: *) => {g} List a -> List (List a);
powerset = \ list -> lazyToStrictList (unwrap [filter chooseBoth list]);

chooseBoth :: (g :: * -> *, a :: *) => {ZList / g} a -> Bool;
chooseBoth = \ foo -> wrap [ZCons True [ZCons False [ZNil]]];

The function chooseBoth is a predicate that both accepts and rejects each element in the list. This is possible because chooseBoth has flavor ZList / g. (The ZList monad transformer is similar to Haskell's ListT; the / operator indicates the composition of a monad transformer with a monad.) The special function wrap turns the explicit nondeterminism of ZCons True [ZCons False [ZNil]] into implicit nondeterminism so that it can be used with filter. The unwrap does the opposite; it converts the implicly nondeterministic filter chooseBoth list into an explicitly nondeterministic ZList value for powerset to return. See the tutorial for a more in-depth explanation.

This way of defining powerset is effectively equivalent to the filterM definition of powerset that Haskell offers, but it does not require a separate monadic version of filter.

More information

Frequently asked questions

Other resources

There's a thread about monad-embed on reddit here.

Slides from my March 2011 talk about monad-embed at the Bay Area Haskell Users' Group are available here (PDF).

Prototype compiler

There is a working compiler available for monad-embed. It is implemented in 3,000 lines of Haskell code. It converts monad-embed source files into Haskell source files, which can then be compiled using ghc. The source code is available here.