Monad Transformers: Constructive Stack Order

What are Monad Transformers?

Monad Transformers provide a modular solution to combining monads, in which a combined monad can be viewed as an ordered stack of layers -- each layer implements the semantics of a single monad. Here's a small stack:

top:     State
bottom:  Maybe

And here's a bigger one:

top:     State
         Maybe
         Error
         Maybe
         Writer
bottom:  Reader

As I mentioned, the stack is ordered -- and one of the problems that people run into when learning how to use monad transformers is what difference the stack order makes, figuring out what the semantics of a given stack are, and coming up with a stack that meets some given criteria.

Does stack order matter?

Yes! For example, let's compare State/Maybe to Maybe/State using the standard transformers. First, we create a stateful computation that increments the state by 1 -- this shows how many times it's executed -- then we create a computation that runs `inc`, fails, and runs `inc` again:

import Control.Monad.State          (StateT(..), MonadState(..))
import Control.Monad.Trans.Maybe    (MaybeT(..))
import Control.Applicative          (Alternative(..))
import Data.Functor.Identity        (Identity(..))

inc :: (Num s, MonadState s m) => m ()
inc = get >>= (put . (+ 1))

calc :: (Num s, MonadState s m, Alternative m) => m ()
calc = (inc >> empty) <|> inc

Here we create our two stacks, differing only in order, and functions for unwrapping the stacks from all the constructors:

type Type1 s a = StateT s (MaybeT Identity) a
type T
ype2 s a = MaybeT (StateT s Identity) a
run1 :: Int -> Maybe ((), Int)
run1 s = runIdentity $ runMaybeT (runStateT calc s)

run2 :: Int -> (Maybe (), Int)
run2 s = runIdentity $ runStateT (runMaybeT calc) s

And the results?

*Main> run1 32
Just ((),33)

*Main> run2 32
(Just (),34)

Different! Apparently the first example only ran `inc` once, while the second ran it twice -- but why?

Calculating stack order

In order to figure out the underlying types of transformer stacks, we need two things: first, the types of monads to which they are applied:

Maybe         /\  a.  Maybe a
State         /\s a.  s -> (a, s)
List          /\  a.  [] a
Identity      /\  a.  a
Either        /\e a.  Either e a
Reader        /\r a.  r -> a
Writer        /\w a.  (a, w)
Cont          /\r a.  (a -> r) -> r

and second, the types of the transformers. Working from Haskell's mtl monad transformer library, I've pulled out the types:

MaybeT        /\  m a.    m (Maybe a)

StateT        /\s m a.    s -> m (a, s)

ListT         /\  m a.    m [a]

IdentityT     /\  m a.    m a

ErrorT        /\e m a.    m (Either e a)

ReaderT       /\r m a.    r -> m a

WriterT       /\w m a.    m (a, w)

ContT         /\r m a.    (a -> m r) -> m r

Now to start building complicated stacks, there are two approaches that I use. The first I find simpler: starting from simple monads, successively add layers, with the result of each step being a more complicated monad that could be placed in the bottom of a monad transformer stack. In other words, what we're doing is:

1. simple monad, or monad(1)
2. transformer + monad(1) = monad(2)
3. transformer + monad(2) = monad(3)
4. ... etc. ...

And an example using StateT as the transformer and Maybe as the monad:

• Step 1: write down the types that the transformer and monad represent
• transformer: /\s m a. s -> m (a, s)
• monad: /\a. Maybe a
• Step 2: substitute the monad into the transformer type, taking the place of type variable `m`
• /\s m a. s -> Maybe (a, s)
• unbind type variable m, bind all type variables except the last (`a`) from the monad
• /\s a. s -> Maybe (a, s)

Let's also do it the other way around: MaybeT and State:

• Step 1: /\m a. m (Maybe a) and /\s a. s -> (a, s)
• Step 2: /\m a. s -> (Maybe a, s)
• Step 3: /\s a. s -> (Maybe a, s)

So we've built some 2-layer monads which can themselves be passed to transformers. For example, with ErrorT as the transformer and Maybe/State as the monad:

• Step 1: /\e m a. m (Either e a) and /\s a. s -> (Maybe a, s)
• Step 2: /\e m a. s -> (Maybe (Either e a), s)
• Step 3: /\e s a. s -> (Maybe (Either e a), s)

And applying ErrorT to State/Maybe:

• Step 1: /\e m a. m (Either e a) and /\s a. s -> Maybe (a, s)
• Step 2: /\e m a. s -> Maybe (Either e a, s)
• Step 3: /\e s a. s -> Maybe (Either e a, s)

The third step is just to tidy things up, making sure the right type variables are in scope and that unused ones are not in scope. The second approach is to combine a transformer with another transformer to create a two-layer transformer. It works similarly to the first approach, except that the resulting transformer can be placed anywhere in a monad stack, instead of just at the bottom.

Semantic differences from stack order

So why is Maybe/State `s -> (Maybe a, s)` different from State/Maybe `s -> Maybe (a, s)`? In Maybe/State, the state is outside of the Maybe, which means that even if the computation fails, you'll still get a (possibly modified) state output; in State/Maybe, if the computation fails, you won't get a new state.

What this means is that the state in Maybe/State is not subject to Maybe's effects; if you're using Maybe for backtracking, as we were in the examples, any modifications to the state won't be undone by backtracking. Since the state is subject to Maybe's effects in State/Maybe, backtracking did prevent the effect of the first `inc` from being reflected in the final output. It's important to note that both orderings are useful in practice, albeit for different things.

On the other hand, for other combinations the order doesn't matter. Examples are Maybe/Error and State/Writer. I don't know of any rule to figure out which pairs are order-dependent and which aren't, so I'm stuck looking it up on a little table of combinations!

A classy approach to parser combinators

Parser combinators

Parser combinators serve as a great introduction to Functional Programming, and are one of the most-studied topics in the field. Nevertheless, they are a very complex and broad topic, covering concepts such as non-determinism, monads, and higher-order functions.

What people may not get as much exposure to, at least in my experience, is many of the Haskell type classes and their relationship to parsers. As we'll see in this article, the most common and useful combinators are actually parser-specific versions of more widely useful generic operations.

Type classes

The definitions of the type classes used are based on both the standard Haskell classes of the same name (minus the '), and Brent Yorgey's Typeclassopedia. I've added a ' to the end of each of their names to indicate that they're not identical to the standard Haskell classes, and in some cases are quite different. I've also added one type class of my own -- Switch' -- which represents the ability to convert a failing computation into a successful one with a default value, and to convert a successful computation into a failing one. I wasn't able to find a type class providing this functionality on Hoogle.

Parser definition and basic combinators

Following convention, parsers are modeled as functions that operate on token streams, either producing a result paired with the rest of the token stream, or failing. A convenient choice for representing possible failure is the Maybe data type.

newtype Parser t a = Parser { 
        getParser :: [t] -> Maybe ([t], a) 
    }

run :: Parser t a -> [t] -> Maybe ([t], a)
run = getParser

In addition, we'll use these basic parsers repeatedly throughout the examples to build bigger and more exotic parsers:

-- succeeds, consuming one token, as
--   long as input is not empty
getOne :: Parser s s
getOne = Parser (\xs -> case xs of 
                        (y:ys) -> pure (ys, y);
                        _      -> empty)

-- runs the parser, and if it succeeds,
--   checks that its result satisfies a predicate
check :: (a -> Bool) -> Parser s a -> Parser s a
check f p = p >>= \x -> 
  guard (f x) >> 
  pure x

-- consumes one token if the token
--   satisfies a predicate
satisfy :: (a -> Bool) -> Parser a a
satisfy p = check p getOne

-- builds a parser that only
--   matches the given token
literal :: Eq a => a -> Parser a a
literal tok = satisfy (== tok)

Alternation and failure

Alternation and failure are covered by the semigroup and monoid classes, respectively. Semigroups are characterized by an associative, binary, closed operation.

The parser interpretation of semigroups is choice: given two parsers, use the first one if it succeeds, but use the second one if the first fails.

class Semigroup' a where
  (<|>)  :: a -> a -> a

instance Semigroup' (Parser s a) where
  Parser f <|> Parser g = Parser (\xs -> f xs <|> g xs)

This implementation exploits the fact that the Maybe datatype can also form a left-biased semigroup.

Monoids are semigroups whose binary operation has an identity element; for parsers, this means that applying the choice operator to any parser plus the identity parser will always return the result of the first parser, regardless of whether it fails or succeeds. The identity parser always ignores its input and fails:

class Semigroup' a => Monoid' a where
  empty :: a

instance Monoid' (Parser s a) where
  empty = Parser (const Nothing)

Here are some examples:

-- combining two parsers with choice:  succeeds if either parser succeeds
a :: Parser Char Char
a = literal 'a'
b :: Parser Char Char
b = literal 'b'
ab :: Parser Char Char
ab = a <|> b

$ run ab "babcd"
Just ("abcd",'b')
$ run ab "abcd"
Just ("bcd",'a')

-- the empty parser always fails
fail :: Parser Char Char
fail = empty

$ run fail "abcd"
$ Nothing

-- the empty parser is both a right and a left identity
a_ :: Parser Char Char
a_ = a    <|>  fail
_a :: Parser Char Char
_a = fail <|>  a

$ run a_ "abcd"
Just ("bcd",'a')
$ run a_ "babcd"
Nothing
$ run _a "abcd"
Just ("bcd",'a')
$ run _a "babcd"
Nothing

We're not limited to combining two parsers at a time, of course; there is also the 'mconcat' combinator:

mconcat :: Monoid' a => [a] -> a
mconcat = foldr (<|>) empty

$ run (mconcat []) "abcde"
Nothing

digits :: [Parser Char Char]
digits = map literal ['0' .. '9']

$ run (mconcat digits) "4hi!!"
Just ("hi!!", '4')

'mconcat' combines a list of monoids using the binary operation, and the identity element as the base case. This means that using 'mconcat' on an empty list will generate a parser that always fails.

Success

Similarly to the parser that always fails, we have a parser that always succeeds. This is captured by the pointed class, which is the 'pure' part of the Applicative class in the standard Haskell libraries. This class allows you to lift a value into a context; for parsers, we build a parser that always succeeds, with the specified value as its result, and consuming zero tokens.

  
class Pointed' f where
  pure :: a -> f a

instance Pointed' (Parser s) where
  pure a = Parser (\xs -> Just (xs, a))

Examples:

pass :: Parser Integer String
pass = pure "Hello, world!"


$ run pass []
Just ([],"Hello, world!")

$ run pass [1,100,31]
Just ([1,100,31],"Hello, world!")

The parser 'pass' always succeeds, even with empty input; it simply returns its input token stream along with its value.

Mapping and sequencing

It's also useful to have access to a parser's value for further processing; a common use case is building up a parse tree. This concept is captured by the Functor class, which lifts a normal function to a function that operates on the result value of a parser. The parser interpretation is that, given a function and a parser, if the parser succeeds, map the function over its results; whereas if the parser fails, just propagate the failure.

class Functor' f where
  fmap :: (a -> b) -> f a -> f b

instance Functor' (Parser s) where
  -- one 'fmap' for the Maybe, one for the tuple
  fmap f (Parser g) = Parser (fmap (fmap f) . g)

The Applicative class enables not just lifting, but application in which both the function and its arguments are in contexts. It allows parsers to be run in sequence, where the first parser is run, and if it fails, the whole chain fails; if it succeeds, the rest of the token stream is passed to the next parser and its result is collected, and so on. This implementation makes use of the Monad instance of Maybe, although it could also be implemented without such an assumption.

class Functor' f => Applicative' f where
  (<*>) :: f (a -> b) -> f a -> f b

instance Applicative' (Parser s) where
  Parser f <*> Parser x = Parser h
    where
      h xs = f xs >>= \(ys, f') -> 
        x ys >>= \(zs, x') ->
        Just (zs, f' x')

Here are some examples:

one :: Parser Char Char
one = literal '1'
oneInt :: Parser Char Int
oneInt = fmap (\x -> (read :: String -> Int) [x .. '9']) one

$ run oneInt "123"
Just ("23",123456789)

two :: Parser Char Char
two = literal '2'
twelve :: Parser Char (Char, Char)
twelve = pure (,) <*> one <*> two

$ run twelve "123"
Just ("3",('1','2'))

$ run twelve "1123"
Nothing

The first example shows a Char parser ('one') that is converted into an Int parser using 'fmap' and a function of type 'Char -> Int'. The second example applies the '(,)' function within an Applicative parser context, tupling the results of the parsers 'one' and 'two'. The third example shows that parsers run in sequence must all succeed for the entire match to succeed; although the '1' is matched, the '2' cannot be.

The power of Applicative parsers can also be harnessed to create parsers that ignore the results (but not the effects!) of some or all of their parsers:

(*>) :: Parser t a -> Parser t b -> Parser t b
l *> r = fmap (flip const) l <*> r 

(<*) :: Parser t a -> Parser t b -> Parser t a
l <* r = fmap const l <*> r

Both '(*>)' and '(<*)' will only succeed if both of their arguments succeed in sequence; the difference is that '(*>)' only returns the result of the 2nd parser, while '(<*)' only returns the result of the 1st parser. Examples, using the 'one' and 'two' parsers defined above:

$ run (two *> one) "212345"
Just ("2345",'1')

$ run (two <* one) "212345"
Just ("2345",'2')

Combining Applicatives with Semigroups, we can create repeating parsers:

many :: Parser t a -> Parser t [a]
many p = some p <|> pure []

some :: Parser t a -> Parser t [a]
some p = fmap (:) p <*> many p

(note that 'some' and 'many' are mutually recursive). 'many' tries to run its parser as many times as possible, progressively chewing up input; it always succeeds since it's fine with matching 0 times. On the other hand, 'some' matches its parser at least once, failing if it can't match it at all, but other than that is identical to 'many'. Examples (using 'one' from above):

$ run (fmap length $ many one) "111111234"
Just ("234",6)
$ run (many one) "23434593475dkljdfs"
Just ("23434593475dkljdfs","")

$ run (fmap length $ one) "111111234"
Just ("234",6)
$ run (some one) "23434593475dkljdfs"
Nothing

Negations

Oftentimes, parsing conditions are easier to state in the negative than in the positive. For instance, if you were parsing a string, you might look for a double-quote character to open the string, and another double-quote to end the string. Meanwhile, anything that's *not* a double-quote which comes after the opening will be part of the string. To capture this pattern, I created the 'Switch' class:

class Switch' f where
  switch :: f a -> f ()

instance Switch' (Parser s) where
  switch (Parser f) = Parser h
    where h xs = fmap (const (xs, ())) $ switch (f xs)

This converts a failing parser to a successful one and vice versa. Importantly, it consumes no input from the token stream -- it acts as a negative lookahead parser, which allows us to build flexible parsers on top of it. Examples:

not1 :: Parser t b -> Parser t t
not1 p = switch p *> getOne

dq :: Parser Char Char
dq = literal '"'

not_dq :: Parser Char Char
not_dq = not1 dq

dq_string :: Parser Char String
dq_string = dq *> many not_dq <* dq

$ run dq_string "\"no ending double-quote"
Nothing

$ run dq_string "\"I'm a string\"abcxyz"
Just ("abcxyz","I'm a string")

The 'not1' combinator takes a parser as input, runs that parser, and if it succeeds, 'not1' fails; if that parser fails, 'not1' then tries to consume a single token (any token). In other words, it's like saying "I want anything but ".

The 'not_dq' parser matches any character that's not a double-quote; the string parser matches a double-quote followed by any number of non-double-quotes, followed by another double-quote; it throws away the results of both double-quote parsers, only returning the body of the string.

Running many parsers in sequence

Traversable is an interesting type class. It allows you to 'commute' two functors; i.e. if you have '[Maybe Int]', it allows you to create 'Maybe [Int]' (that is, turn a list of 'Maybe Int's into a 'Maybe' list of Ints. This is also useful for parsing, where it allows one to convert a list of parsers into a (single) parser of lists. In this case, we don't need to supply an instance for 'Parser' because the Functor in question is lists:

class Functor' t => Traversable' t where
  commute :: (Pointed' f, Applicative' f) => t (f a) -> f (t a)

Here are some examples (using 'digits' from above):

six_fours :: [Parser Char Char]
six_fours = replicate 6 (literal '4')

$ run (commute digits) "0123456789abcxyz"
Just ("abcxyz","0123456789")

$ run (commute six_fours) "4444449999999"
Just ("9999999","444444")
$ run (commute six_fours) "44444 oops that was only 5 fours"
Nothing

Monads

What parsing article could be complete without mentioning monads? Monads are similar to applicatives, but add the extra ability to have computations depend on the result of previous computations. Here's the class definition and parser implementation:

class (Applicative' m, Pointed' m) => Monad' m where
  join :: m (m a) -> m a 

instance Monad' (Parser s) where
  join (Parser f) = Parser h
    where
      h xs = f xs >>= \(o, Parser g) -> g o  

A good example of putting this extra power to work is this combinator:

twice :: Eq a => Parser a a -> Parser a a
twice p = p >>= \x ->
  literal x

It runs its input parser, and if it succeeds, attempts to match the *same* output a second time. Thus, the second match depends on the results of the first. We can't build such a parser using applicatives (although we can build less general versions by enumerating multiple cases). Here's an example showing how it's different from an Applicative version, using the 'ab' parser from earlier:

ab_twice :: Parser Char Char
ab_twice = twice ab

-- using monads
$ run ab_twice "aa123"
Just ("123",'a')
$ run ab_twice "ab123"
Nothing

-- using applicatives
$ run (pure (,) <*> ab <*> ab) "aa123"
Just ("123",('a','a'))
$ run (pure (,) <*> ab <*> ab) "ab123"
Just ("123",('a','b'))

In the first example, which uses monadic parsing, 'ab_twice' parses the first input and fails on the second. However, the second example -- with applicatives -- successfully parses both inputs. It sees the two parsers as being totally independent of each other and thus isn't able to require that the second one match the same tokens as the first one.

Relationship to BNF grammars, regular expressions, etc.

Of course, all of these useful parsing combinators have also been applied in other parsing approaches, such as grammars and regular expressions. Here's a quick correspondence:

BNF/regex	combinators
|	<|> of semigroups
sequencing	<*> of applicatives
*	many
+	some
grouping	always explicitly grouped

What's next & further reading

There are a few topics that weren't covered in this article. First and foremost, good error detection and reporting is a key component of a parser library that's friendly and easy to use. Second, although I chose to use the Maybe data type to model the results, this could be extended to use any arbitrary monad -- resulting in a much richer set of parsers. Two examples are the list monad, to allow non-deterministic parses, and the state monad, two allow context-dependent parses.

If you're interested in learning more about parsing, Philip Wadler, Graham Hutton, and Doaitse Swierstra have published some excellent papers over the years on the topic; reading their papers was what really helped me to understand parsing. And of course there's also the powerful Parsec tool, a Haskell-based library for parser combinators which illustrates these ideas in a practical context.

A Haskell library for relational algebra

Why Haskell? Why relational algebra?

If you've never heard of Haskell before, and you like programming languages, you might want to check it out. It's a functional, statically-typed, type-inferred, elegant language in the ML family. The most important benefit that I've received from working with Haskell is a much better understanding of the static typing discipline, and the practice of designing a program or a library by figuring out a few concepts, capturing them as types -- either data or functions -- and building the rest of the code around them.

Relational algebra (RA) is a powerful mathematical tool for working with sets and functions on sets. Most common database products implement some flavor of SQL, a practical and standard language which contains many constructs from RA. Using SQL, a programmer can easily accomplish many complex data querying, manipulation, and transformation operations.

Unfortunately, applying RA often necessitates the use of a database. For whatever reason, there seem to be very few 'pure' RA libraries available for common languages. However, there are enormous benefits to be gained from integrating RA, instead of using a database: 1) not coupled to a database product, or its failure modes; 2) one less dependency for a deployed program; 3) code can mix RA with general purpose code, enhancing the effectiveness and efficiency of RA.

This post discusses the basic design and implementation of an RA library in Haskell.

Data model

The basic data types in RA are tuples, fixed-size units of n primitive values, and relations, or unordered sets composed of multiple named n-tuples of the same type. To distinguish RA tuples from Haskell tuples, I'll call them 'rows' for the rest of this post. Here's an example:

(first name: "Matthew", country: "USA", age: 25) <-- a named 3-tuple

a relation:

 first name | country | age   <-- the schema
-----------------------------
 "Matthew"  |  "USA"  |  25   <-- a tuple
  "Jimbo"   | "Spain" |  32   <-- another tuple of the same type
 "Jessica"  |  "USA"  |  27   <-- a third compatible tuple

However, the Haskell data model is a little bit different. Instead of restricting our row representation to just Haskell n-tuples, we'll let *any type* be a row, as long as we can compare any two instances of it for equality and ordering. And instead of using sets, we'll use lists -- Haskell has a large number of functions for working with lists, so it's a lot more convenient to use them than sets (although lists are intrinsically ordered, and do allow duplicates. We can ignore the first problem by never assuming the ordering is meaningful, but the second is more dangerous potentially). So what we have is:

-- the type of a relation:
:: (Eq a, Ord a) => [a]

-- and some examples of relations:
r1 :: Num a => [a]
r1 = [1,2,3]

r2 :: Num a => [(String, a)]
r2 = [("Matt", 1), ("Kevin", 14)]

r3 :: [a]
r3 = [] 

r4 :: [[String]]
r4 = [["abc", "xyz"], ["ghi"], []]

Note how the types of the rows can be almost anything -- numbers, Haskell tuples, polymorphic, or even lists.

Primitive RA operators

Rename: change attribute names, without changing any values. This operator is meaningless in the Haskell version, since it's not restricted to named tuples.

(name: "Matt", total: 32) -> (first name: "Matt", sum: 32)

Projection: apply a function to each tuple in a relation. Unfortunately, this could result in duplicates for either of two reasons: 1) the input contained duplicates, or 2) the mapping function created duplicates. The 2nd case has to be dealt with.

$ project (length . fst) [("Matt", 30), ("Bob", 22), ("Jimbo", 39), ("Sarah", 28)]
[4,3,5]

Row selection: select some rows, discarding the rest; none of the rows are changed.

$ rfilter (\(name, age) -> age >= 30) [("Matt", 30), ("Bob", 22), ("Jimbo", 39), ("Sarah", 28)]
[("Matt",30),("Jimbo",39)]

Cartesian product: combine two relations of size m and n rows respectively, resulting in a relation of size (m * n) rows, where an output row consists of a row from each of the input tables glued together. SQL and RA typically restrict result sets to *flat* tuples; since we've already gotten rid of this restriction, we're free to allow this to produce nested tuples.

$ rproduct "abc" [1..4]
[('a',1),('a',2),('a',3),('a',4),('b',1),('b',2),
 ('b',3),('b',4),('c',1),('c',2),('c',3),('c',4)]

Union: given two relations of the same type with m and n rows respectively, combine them by removing duplicates, resulting in a new relation of the *same* type with no more than (m + n) rows.

$ union [1..10] [5..15]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

Difference: given two relations of the same type, remove all elements found in the second relation from the first relation.

$ difference [1..10] [5..15]
[1,2,3,4]

Here are the Haskell implementations (note that these are by no means as efficient as possible):

project :: Eq b => (a -> b) -> [a] -> [b]
project f = nub . map f

rfilter :: (a -> Bool) -> [a] -> [a]
rfilter = filter
    
rproduct :: [a] -> [b] -> [(a, b)]
rproduct = liftM2 (,)

intersect :: Eq a => [a] -> [a] -> [a]
intersect xs ys = filter (\x -> x `elem` ys) xs

union :: Eq a => [a] -> [a] -> [a]
union xs ys = nub (xs ++ ys)

difference :: Eq a => [a] -> [a] -> [a]
difference r1 r2 = filter (\x -> not $ elem x r2) r1

Extending the library with some useful SQL operators

Inner, outer and left (outer) joins: these combine a cartesian product operation with a filtering operation. Outer joins are augmented inner joins, in that there is one additional result row for each unmatched row on one or both sides. Requires a default value of each row type to combine with the unmatched rows -- we're avoiding 'NULL's (although we could use Just/Nothing instead).

predicate l r = fst l == fst r
left = [(1, "Matt"), (2, "Jackie"), (3, "Gilligan")]
right = [(1, "hammer"), (1, "saw"), (1, "screwdriver"), (3, "boat"), (4, "wrench")]

$ innerJoin predicate left right
[((1,"Matt"),     (1,"hammer")),
 ((1,"Matt"),     (1,"saw")),
 ((1,"Matt"),     (1,"screwdriver")),
 ((3,"Gilligan"), (3,"boat"))]

$ leftJoin predicate (0, "nothing") left right
[((1,"Matt"),     (1,"hammer")),
 ((1,"Matt"),     (1,"saw")),
 ((1,"Matt"),     (1,"screwdriver")),
 ((2,"Jackie"),   (0,"nothing")),    <--- an extra row!!
 ((3,"Gilligan"), (3,"boat"))]

$ outerJoin predicate (0, "nobody") (0, "nothing") left right
[((1,"Matt"),     (1,"hammer")),
 ((1,"Matt"),     (1,"saw")),
 ((1,"Matt"),     (1,"screwdriver")),
 ((2,"Jackie"),   (0,"nothing")),
 ((3,"Gilligan"), (3,"boat")),
 ((0,"nobody"),   (4,"wrench"))]    <--- another extra row!!

Grouping, group processing, and aggregation: it's often useful to separate a relation into groups based on values of certain attribute(s), and then to continue processing with the grouped data.

-- group some words by their length
$ let g1 = groupBy length $ words "this is an article for my blog that I hope is interesting"
[(1,["I"]),       (2,["is","my","an","is"]),
 (3,["for"]),     (4,["hope","that","blog","this"]),
 (7,["article"]), (11,["interesting"])]

-- the first letters of words, in each group
$ groupLift (project head) g1
[(1,"I"), (2,"ima"),
 (3,"f"), (4,"htb"),
 (7,"a"), (11,"i")]

-- the number of words, in each group
$ groupLift length g1
[(1,1), (2,4),
 (3,1), (4,4),
 (7,1), (11,1)]

-- the unique letters, in each group
$ groupLift (nub . concat) g1
[(1,"I"),       (2,"ismyan"),
 (3,"for"),     (4,"hopetablgis"),
 (7,"article"), (11,"intersg")]

-- aggregation ignoring groups
$ aggregate (length . snd) sum g1
12

-- aggregation within groups
$ groupLift (aggregate (ord . head) sum) g1
[(1,73),  (2,416),
 (3,102), (4,434),
 (7,97),  (11,105)]

And the implementations:

innerJoin :: (a -> b -> Bool) -> [a] -> [b] -> [(a, b)]
innerJoin f ls rs = rfilter (uncurry f) (rproduct ls rs)

leftJoin :: forall a b. (a -> b -> Bool) -> b -> [a] -> [b] -> [(a, b)]
leftJoin p null rl rr = concatMap f rl
  where 
    -- go through all the a's 
    --   match each a with all b's
    --   if no matches, match it with the default
    --   otherwise keep all matches
    f :: a -> [(a, b)]
    f a = map ((,) a) $ addNull $ filter (p a) rr
      where
        addNull :: [b] -> [b]
        addNull [] = [null]
        addNull bs = bs

outerJoin :: (Eq a, Eq b) => (a -> b -> Bool) -> a -> b -> [a] -> [b] -> [(a, b)]
outerJoin p anull bnull as bs = union left right
  where 
    left = leftJoin p bnull as bs
    right = project swap $ leftJoin (flip p) anull bs as

groupBy :: (Ord b) => (a -> b) -> [a] -> [(b, [a])]
groupBy f rel = toList grouped
  where
    grouped = foldl f' (fromList []) rel
    f' mp next = addRow (f next) next mp
    -- check whether the key's already in the map:
    -- if it is, stick 'next' on the existing list
    -- if not, create a new, single-element list for that key
    addRow :: Ord k => k -> v -> Map k [v] -> Map k [v]
    addRow k v mp = case lookup k mp of    
                        (Just oldval) -> insert k (v:oldval) mp;  
                        _ -> insert k [v] mp;  

groupLift :: ([a] -> c) -> ([(b, [a])] -> [(b, c)])
groupLift f = map (fmap f)  

aggregate :: (a -> b) -> ([b] -> c) -> [a] -> c
aggregate proj f = f . map proj

Some notes about the design goals of the library

was shooting for flexibility, simplicity, and minimality, not efficiency. thus, it lacks many 'composite operators' that SQL has, for instance: in a SQL join, you both join and project all in one operation. in this library, instead, you'd do the join, then the projection separately ... maybe less efficient, but more expressive and compositional. another example, is that it lacks things like equi-joins that would make joining more efficient; it doesn't have them b/c that's covered by inner joins.

Why is Clojure hard to learn?

I've spent a good deal of time in the last few months using Clojure, and my experiences have been pleasant. As a Lisp dialect, it's automically a very interesting programming language. But even better, it's also a JVM language, and benefits from very tight integration with the JVM and with Java code itself.

However, all is not perfect in the Cloverse. Clojure has a very steep learning curve. While for the masters, it can be a powerful, supple, flexible tool, for the rest of us, it's esoteric, foreign, and opaque.

Why is this?

My belief is that this difficulty is, to a large degree, caused by the natural structure and organization of Clojure code, which is very different from the natural structure and organization of projects in mainstream programming languages. I will differentiate between four models of code organization, and show how Clojure's is hardest for the novice (but not for the master).

language	type system	paradigm	list of methods/functions object supports	methods/functions are typed	interactive access to docs	easy to use REPL
Java	static	object-oriented	yes: compile-time (IDE autocompletion)	yes	yes: IDE feature	no
Python	dynamic	object-oriented	yes: run-time (limited IDE support possible)	no	yes: interactive `help` function	yes
Haskell	static	functional	no	yes	yes (limited)	yes
Clojure	dynamic	function	no	no	yes	yes

Analysis/interpretation

What's missing? Note that with both Haskell and Clojure, since they're not object-oriented, it's not possible to easily find all of the functions that can be invoked on an object. Why? In object-oriented languages, the most useful methods are members of a class or object, and can be found "through" the object; whereas functions are not organized as "belonging" to an object; a function accepting an X could appear in any module or file (and indeed, it may make sense to do so). Although note that methods can be part of other classes (think 'util' or 'helper' classes), and indeed, such an organization can be difficult to grok.

This problem is mitigated to a certain extent in Haskell because functions are statically typed, thus, given the type of an object, all relevant functions can be looked up (check out Hoogle for an example).

There's no common REPL for Java (that I know of); I count this as a major negative for Java, because it makes it much harder to interact with code. However, this is more than offset by the fantastic IDEs, such as Eclipse and NetBeans, that have been created to help manage Java code bases. The key features of these programs are interactive access to lists of applicable methods, documentation, imports, automatic refactoring ...

Clojure enjoys neither Haskell's typing, which provides an important modicum of documentation, nor the luxury of specialized IDEs. Thus it's very difficult to find all the functions that an object supports.

How can this be fixed? I don't know, but I think the key lack is that of access to relevant information from within the programming environment, whether it applicable functions of docs. When someone figures out an effective way to implement this, expect Clojure to become very popular.

Summary

The problem that I believe Clojure is facing, and that likely all languages face in their infancy, is how to lower the barrier to entry, and make it easy for newcomers to effectively learn to use the language. An important aspect of this is how the information contained in function, object, and module documentation is accessed, indexed, and searched by the programmer. Clojure is lacking in this area, and therefore presents difficulties to newcomers.