How to make Data.Set a monad
Posted by Eric Kidd Thu, 15 Mar 2007 22:29:00 GMT
…and how to fake Lisp macros with Template Haskell
(I wrote this article in response to a comment by sigfpe. You may find it pretty dry reading, unless you want to build domain-specific languages in Haskell. Proceed at your own risk.)
Haskell’s built-in Monad type has some serious limitations. We can fix those limitations using a number of advanced Haskell techniques, including Template Haskell, Haskell’s closest equivalent to Lisp macros.
We can illustrate the limitations of Monad with an example from math. In set theory, we can define a set by specifying how to compute each
element:
{ xy : x ∈ {1,2,4}, y ∈ {1,2,4} }
We can read this as, “the set of all xy, where x is one of {1,2,4}, and y is one of {1,2,4}.” To calculate the answer, we first multiply together all the possible combinations:
1×1=1, 1×2=2, 1×4=4, 2×1=2, 2×2=4, 2×4=8, 4×1=4, 4×2=8, 4×4=16
We then collect up the answers, and—because we’re working with sets–we throw away the duplicates:
{1,2,4,8,16}
Can we do the same thing in Haskell? Well, using Haskell’s list monad, we can write:
But when we run this, Haskell gives us lots of duplicate values:
Our problem: We’re using lists (which can contain duplicate
values) to represent sets (which can’t). Can we fix this by switching to
Haskell’s Data.Set?
Unfortunately, this code fails spectacularly. A Haskell monad is required
to work for any types a and b:
But Data.Set only works for some types. Specifically, it
requires that values of type a can be ordered:
As it turns out, we can make Data.Set into a monad. But be
warned: The solution involves some pretty ugly Haskell abuse.
