ZipEdit

So I’ve taken over the editorship of the Haskell Weekly News, a job that would be completely insane without help from automated tools. Putting together an issue requires gathering information from a number of different sources, summarizing and compiling the information into a consistent, standard layout, and finally publishing the issue in several different formats.

Thankfully, along with the editorship I inherited some nice tools built by my predecessors, including, in particular, a utility that generates all the different HWN formats (text, html, and pdf) from one text file in a standard format (essentially, the standard Show representation of a value of type HWN). This makes the task of creating and producing each issue much simpler; I have only to worry about the content, and the formatting is taken care of.

However, there wasn’t anything in the way of automation for the process of gathering material in the first place. Of course, this can’t be completely automated—at some level a human still has to look through lists of emails and blog posts and the like, decide what to include, and summarize it appropriately. But there’s still quite a bit of tedium that can potentially be automated away. So, I set about writing myself some tools, hoping that the upfront investment of time will pay off in the long run.

At the heart of several of these tools is a new library I created called zipedit. It’s far from polished and elegant, and may not even be useful to anyone else, but I think it’s kind of cute. The idea is simple: given some sort of list, we want to be able to create a text interface which allows the user to ‘edit’ the list by moving back and forth within it and modifying, deleting, or inserting elements. It’s called ‘zipedit’ because, of course, it uses a list zipper to keep track of the list context.

What does this have to do with collecting material for the HWN? Well, here’s a motivating example: using this library, I wrote a little utility that gets the RSS feed from Planet Haskell, parses out the relevant information, and presents each item to me one-by-one. For each item I can choose whether I would like it to be included in the HWN. But since I am really editing a list of RSS items, I can move backwards as well as forwards through the items, change my mind, and so on. When I am finally done, those items which I chose to be included are output in a format appropriate for pasting into the issue I am editing. The great thing is that the zipedit library deals with all the icky IO bits—the actual utility just specifies an appropriate (pure, functional) configuration. Here are some relevant bits of code from the utility:

data FlaggedItem = FI { item :: RSSItem
                      , use  :: Bool
                      }

mkItem :: RSSItem -> FlaggedItem
mkItem r = FI r False

yes :: FlaggedItem -> FlaggedItem
yes (FI r _) = FI r True

no :: FlaggedItem -> FlaggedItem
no (FI r _) = FI r False

ec :: EditorConf FlaggedItem
ec = EC { display = maybe "" (showItem 30)
        , prompt  = maybe "" (\fi -> (if use fi then "\n(Y/n)" else "\n(y/N)") ++ "? ")
        , actions = [ ('y', Seq [Modify yes, Fwd])
                    , (’n', Seq [Modify no, Fwd])
                    , (’p', Output (showItem 100))
                    ]
                    ++ stdActions
        }

main = do
  RSSFeed rss <- (fromJust . parseFeedString) `fmap` openURL url
  let items = map mkItem . rssItems . rssChannel $ rss
  ml <- edit ec items
  case ml of
    Nothing     -> return ()
    Just items’ -> do
      f <- openFile “blogs.wiki” WriteMode
      hPutStr f . intercalate “,\n\n” . map (fmt.item) . filter use $ items’
      hClose f

I’ve left out a few things that aren’t important for this discussion (such as the code that formats the RSS items for output); the full source code can be obtained from the darcs repository. The important part to note is the definition of ec, which gets passed to the edit function. To define a configuration for a list editor, you just need to specify three things: a display function, which tells the library how to display the elements of the list; a prompt function, which tells it how to display an input prompt; and a mapping from user inputs (single character commands) to actions that should be taken in response. In this case, you can see that I have defined ‘y’ and ‘n’ to mark the current item as used/unused and automatically move to the next item, and the ‘p’ command to print more context. I’ve also used a set of standard commands provided by the zipedit library (things like ‘q’ for canceling, ‘d’ for when you’re done, ‘j’ and ‘k’ for moving forwards and backwards, and so on).

So, what does it look like? Here’s an example of the above utility in action:

[05:02:59 brent@xenophon:~/haskell/hwn]$ ./planethaskell 

Andy Gill: Where is the call to $f4?
In a previous blog, we saw that we have options for which version of core we examine.
We saw that we had a significant dictionary creation attributed cost, beneath unvector2D.
(y/N)? n

Bryan O’Sullivan: Disappointed by Thinkpad X60 thermal problems
Ive had a Lenovo X60 for about 18 months. For almost a year, I was well pleased with
its combination of light weight and decent performance, but then it developed
(y/N)? k

Andy Gill: Where is the call to $f4?
In a previous blog, we saw that we have options for which version of core we examine.
We saw that we had a significant dictionary creation attributed cost, beneath unvector2D.
(y/N)? y

Bryan O’Sullivan: Disappointed by Thinkpad X60 thermal problems
Ive had a Lenovo X60 for about 18 months. For almost a year, I was well pleased with
its combination of light weight and decent performance, but then it developed
(y/N)? n

Russell O’Connor: No-Good Ethical Funds
I do not understand the motivation behind buying ethical funds. They seem like a bad idea.
By my understanding they Do not help ethical companies Do not hinder unethical companies
(y/N)? d

As you can see, I rejected the first item, then changed my mind and went back, selected it, rejected the next item, and then decided that I was done. If you’ve used darcs, you may also realize at this point where I got my inspiration for this little project. =)

Another slightly more sophisticated utility I’ve created is for gathering announcements and discussions from email traffic on various lists. Not only can I select or reject individual posts, but for those I select, I can interactively choose a title, and compose some summary text in my favorite editor (which is initially populated with the text of the post, so I can easily pick and choose sentences, phrases, or links to incorporate into my summary). I’ve even added a nifty feature where it only loads a certain number of posts at a time, and seamlessly fetches more over the network when I get to the end of the list. The source code for this utility (gmane.hs) is also available from the HWN darcs repository.

The latest release of zipedit is available on Hackage; there’s also a darcs repository. As always, comments, questions, and patches welcome! I’d be especially interested to hear if you actually find zipedit useful for something, and if so I imagine I would be very responsive to reasonable feature requests. =)

New Haskell diagrams library

For the past week or so I’ve been working on an embedded domain-specific language for rendering simple diagrams with Haskell, and I’m excited to actually release version 0.1 today! You can now find it on Hackage. Version 0.1 is still fairly primitive, and there are a bunch more planned features, but you can already use it to create some pretty pictures. Here are a few examples.

We’ll start with a basic ‘hello world’ type diagram: a two-by-five rectangle, no frills:

module Main where
import Graphics.Rendering.Diagrams

main = renderToPng "hello.png" 100 100 (rect 2 5)

OK, not too exciting, but at least it was easy. Here’s another silly example that shows off a few more available features:

module Main where
import Graphics.Rendering.Diagrams

shapes :: Diagram
shapes = hcat [ fc blue $ circle 10
              , (fc goldenrod . lc green . lw 3 $ poly 5 10)
                ## (fc red . rotate (1/10) $ rect 4 4)
              , fc grey . lw 0 . scaleY 3 $ circle 5
              ]

main = renderToPng “shapes.png” 200 200 shapes

Hopefully, this example is fairly self-explanatory. We can alter the appearance of diagrams by applying functions to them like fc (fill color), lc (line color), lw (line width), rotate, and scaleY. We can superimpose two diagrams with ##. And we can lay out a list of diagrams horizontally with hcat. There are many other combinators along similar lines, with various options for distributing and aligning subdiagrams.

Now for a couple cooler examples. How about a Sierpinski triangle?

module Main where

import Graphics.Rendering.Diagrams
import Graphics.Rendering.Diagrams.Types

import qualified Graphics.Rendering.Cairo as C
import Graphics.Rendering.Diagrams.Shapes (draw)

data EqTri = EqTri  deriving Show
instance ShapeClass EqTri where
  shapeSize _   = (2, sqrt 3)
  renderShape _ = do
    c $ C.moveTo 1 s
    c $ C.lineTo 0 (-s)
    c $ C.lineTo (-1) s
    c $ C.closePath
    draw
   where s = sqrt 3 / 2

sierpinski :: Int -> Diagram
sierpinski 0 = fc black $ lw 0 $
               shape EqTri
sierpinski n = vcatA hcenter [         s
                             ,      s <> s]
  where s = sierpinski (n-1)

main = renderToPng “sierpinski.png” 300 300 (sierpinski 6)

This example illustrates a couple key points. One is that the library is easy to extend with new shapes. The built-in poly function is too general to provide a nice equilateral triangle for use in making a sierpinski triangle (its bounding box is too large, which would lead to ugly spaces in the diagram), so we can define our own shape just by making an instance of ShapeClass, and using the Cairo library to draw a path defining the shape. This is probably not the best way to accomplish this particular task — future versions of the diagrams library will include easier ways — but it’s a nice example of how easy it is to extend the basic library functionality.

The other key point is how much power we get for free from the fact that this is an embedded DSL. We can use the full power of Haskell to define a recursive function for computing sierpinski triangle diagrams.

For a final example, here are some nice Ford circles:

module Main where

import Graphics.Rendering.Diagrams

import Data.Ratio
import System.Random

(<+>) :: Rational -> Rational -> Rational
r1 <+> r2 = (numerator r1 + numerator r2) % (denominator r1 + denominator r2)

farey :: Integer -> [Rational]
farey 0 = [0%1, 1%1]
farey n = insertMediants (farey (n-1))

insertMediants :: [Rational] -> [Rational]
insertMediants [] = []
insertMediants [x] = [x]
insertMediants (x:y:zs) = x : (x <+> y) : insertMediants (y:zs)

fordCircles :: Integer -> [Diagram]
fordCircles n = map toCircle (filter ((<= n) . denominator) $ farey n)

toCircle r = translateX r’ $
             circle (1 / (2 * d’^2))
  where r’ = fromRational r
        d’ = fromIntegral (denominator r)

dia :: [Color] -> Diagram
dia colors = view (0,-1/2) (1,0) $
             unionA hcenter bottom $
             zipWith fc colors (fordCircles 20)

randomColors :: [Double] -> [Color]
randomColors (r:g:b:ds) = rgb r g b : randomColors ds

main :: IO ()
main = do
  g <- newStdGen
  let rs = randoms g
  renderToPng “ford.png” 400 205 (dia $ randomColors rs)

Plans for future versions of the library include:

• text objects
• settable backgrounds and better support for transparency
• support for line join style and dashing
• more primitive shapes: special triangles, ellipses, bezier curves, lines, arrows…
• more layouts: grid, tree, circle…
• constraint-based placement of objects, e.g. to connect diagrams with arrows
• more output modes: ps, svg, pdf
• and more!

If this looks interesting to you, I hope you’ll download the library and play around with it! (Note that it does require the Cairo bindings, which are packaged as part of gtk2hs, which is unfortunately not yet Cabalized.) I would be happy to receive any and all feedback, including feature suggestions, bug reports, and pretty pictures. If you’re interested in contributing code, the darcs repository can be found at http://code.haskell.org/diagrams/.

Enjoy!

List convolutions

On the #haskell IRC channel a week or so ago, cdsmithus asked:

An easy (hopefully) question. I have an infinite list. How do I get a list of ordered pairs of stuff from the first list?

Several people suggested variations on the following theme:

pairs = [(b,a-b) | a <- [0..], b <- [0..a]]

which produces the list pairs = [(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3), (1,2), (2,1), (3,0), ... I'm not sure if this was exactly the solution cdsmithus wanted, but just to humor me, let's suppose it was. =) In a sense, this can be considered a "universal" sort of solution, since given any infinite list xs :: [a], we can get a corresponding list of pairs from xs by evaluating

map (\(a,b) -> (xs!!a, xs!!b)) pairs

But of course this isn’t very efficient, since (xs!!a) is O(a) — the beginning of xs is getting unnecessarily traversed over and over again. So, can we do this in a more “direct” way?

Notice the similarity to power series multiplication: multiplying the general power series and yields

Both are instances of discrete convolution. I immediately thought of Douglas McIlroy’s classic Functional Pearl, Power Series, Power Serious. In it, he exhibits some amazing, simple, elegant Haskell code for computing with power series, treated as infinite (lazy!) lists of coefficients. The part we’re interested in is the definition of lazy power series multiplication:

(f:fs) * (g:gs) = f*g : (f.*gs + g.*fs + (0 : fs*gs))

where x .* ys = map (x*) ys, essentially. This code may seem mysterious, but any confusion is quickly cleared up by the simple algebraic derivation:

So, can we adapt this to compute list convolutions instead of numeric power series convolutions? Sure! We just need to make a few adjustments. First, we’ll replace element-wise multiplication with the tupling operator (,). And instead of addition, we’ll use list concatenation to collect tupled results. Finally, since tupling and concatenation are not commutative like multiplication and addition, we’ll have to be a bit more careful about order. There are a few other minor issues, but I’ll just let the code speak for itself:

import Prelude hiding ((+),(*),(**))
import qualified Prelude as P

(+) = zipWith (++)
x * y = [(x,y)]
x .* ys = map (x*) ys
ys *. x = map (*x) ys

(**) :: [a] -> [b] -> [[(a,b)]]
[]     ** _      = []
_      ** []     = []
(x:xs) ** (y:ys) = x*y : (x .* ys) + ([] : (xs ** ys)) + (xs *. y)

We can test it out in ghci (being sure to pass ghci the -fno-implicit-prelude option so we don’t get conflicts with our definition of (**)):

> take 10 . concat $ [1..] ** ['a'..]
[(1,'a'),(1,'b'),(2,'a'),(1,'c'),(2,'b'),(3,'a'),(1,'d'),(2,'c'),(3,'b'),(4,'a')]
> take 10 . concat $ [0..] ** [0..]
[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]

Cool! Now, there’s just one issue left: this code is still rather slow, because of the way it uses list concatenation repeatedly to accumulate results; in fact, I suspect that it ends up being not much better, speed-wise, than the naive code we looked at first which generates numeric tuples and then indexes into the lists! Taking the first one million elements of concat $ [1..] ** [1..], multiplying each pair, and summing the results takes around 16 seconds on my machine.

We can easily fix this up by using “difference lists” instead of normal lists: we represent a list xs by the function (xs++). Then list concatenation is just function composition — O(1) instead of O(n). Kenn Knowles wrote about this representation recently, and Don Stewart has written the dlist package implementing it. We don’t require a whole fancy package just for this application, however; the changes are easy enough to make:

import Prelude hiding ((+),(*),(**))
import qualified Prelude as P

type List a = [a] -> [a]

fromList :: [a] -> List a
fromList = (++)

toList :: List a -> [a]
toList = ($[])

singleton :: a -> List a
singleton = (:)

empty :: List a
empty = id

(+) = zipWith (.)
x * y = singleton (x,y)
x .* ys = map (x*) ys
ys *. x = map (*x) ys

(**) :: [a] -> [b] -> [List (a,b)]
[]     ** _      = []
_      ** []     = []
(x:xs) ** (y:ys) = x*y : (x .* ys) + (empty : (xs ** ys)) + (xs *. y)

Ah, much better. This code only takes 0.6 seconds on my machine to compute the same result with the first one million elements of concat . map toList $ [1..] ** [1..].

Collecting unstructured information with the monoid of partial knowledge

In my last post, I described what I’m calling the “monoid of partial knowledge”, a way of creating a monoid over sets of elements from a preorder, which is a generalization of the familiar monoid over a set with a total order and a smallest element.

There’s actually one situation where a special case of this monoid is commonly used in Haskell. Suppose you have a record type which contains several fields, and you would like to parse some input to create a value of this type. The problem is that the input is not very nice: the bits of input which designate values for various fields are not in any particular order; some occur more than once; some might even be missing. How to deal with this?

One common solution is to wrap the type of each field in the record with Maybe, and create a Monoid instance which allows you to combine two partial records into one (hopefully less partial) record. Using this framework, you can just parse each bit of input into a mostly-blank record, with one (or more) fields filled in, then combine all the records (with mconcat) into one summary record. For example:

import Data.Monoid
import Control.Monad  -- for the MonadPlus instance of Maybe

data Record = R { name  :: Maybe String,
                  age   :: Maybe Int }
  deriving (Eq, Show)

instance Monoid Record where
  mempty = R Nothing Nothing
  mappend r1 r2 = R { name = name r1 `mplus` name r2
                    , age  = age r1  `mplus` age r2
                    }

The mplus function, from the MonadPlus instance for Maybe, simply takes the first Just value that it finds. This is nice and simple, and works just great:

> mempty :: Record
R {name = Nothing, age = Nothing}
> mconcat [mempty { name = Just "Brent" }]
R {name = Just “Brent”, age = Nothing}
> mconcat [mempty { name = Just "Brent" }, mempty { age = Just 26 }]
R {name = Just “Brent”, age = Just 26}
> mconcat [mempty { name = Just "Brent" }, mempty { age = Just 26 }, mempty { age = Just 23 }]
R {name = Just “Brent”, age = Just 26}

Note how the appending is left-biased, because mplus is left-biased: after seeing the first age, all subsequent ages are ignored.

Now, really what we’re doing here is using the monoid (as in my previous post) induced by the preorder which says that any name is any other name, and any age is any other age, and names and ages can’t be compared!

Some code is in order. First, we create a class for preorders, and a newtype to contain sets of elements (there’s already a Monoid instance for Set, so we need a newtype to give a different semantics). Then we translate the specification from my previous post directly into a Monoid instance.

import qualified Data.Set as S

-- laws:
-- if x == y, then x <~ y
-- if x <~ y  and y <~ z, then x <~ z
class (Eq p) => Preorder p where
  (<~) :: p -> p -> Bool

newtype PStar p = PStar { unPStar :: (S.Set p) }
  deriving Show

instance (Preorder p, Ord p) => Monoid (PStar p) where
  mempty      = PStar S.empty
  mappend (PStar ss) (PStar ts) = PStar $
    S.filter (\s -> all (\t -> s == t || t <~ s || not (s <~ t)) $ S.toList ts) ss
    `S.union`
    S.filter (\t -> all (\s -> s == t || not (t <~ s)) $ S.toList ss) ts

Pretty straightforward! Of course, there are probably more efficient ways to do this, but I don’t care about that at the moment: let’s get some working proof-of-concept code, and worry about efficiency later. Now, one thing you may notice is that our Monoid instance requires an Ord instance for p! “But I thought we only needed a preorder?” I hear you cry. Well, the Ord is just there so that we can use an efficient implementation of Set. In particular, note that the Ord instance need have nothing at all to do with the Preorder instance, and won’t affect the semantics of this Monoid instance in any way. If we wanted, we could do away with the Ord entirely and use lists of unique elements (or something like that) instead of Sets.

So, how do we translate our record example from above into this new framework? Easy, we just create a data type to represent the different kinds of facts we want to represent, along with a convenience method or two, and make it an instance of Preorder:

data Fact = Name String | Age Int
  deriving (Eq,Show,Ord)

fact :: Fact -> PStar Fact
fact f = PStar (S.singleton f)

instance Preorder Fact where
  (Name _) <~ (Name _) = True
  (Age _)  <~ (Age _)  = True
  _        <~ _        = False

Let’s try it!

> mempty :: PStar Fact
PStar {unPStar = fromList []}
> mconcat . map fact $ [Name "Brent"]
PStar {unPStar = fromList [Name "Brent"]}
> mconcat . map fact $ [Name "Brent", Age 26]
PStar {unPStar = fromList [Name "Brent",Age 26]}
> mconcat . map fact $ [Name "Brent", Age 26, Age 23]
PStar {unPStar = fromList [Name "Brent",Age 26]}

Neato! But the really cool thing is all the extra power we get now: we can easily tweak the semantics of the Monoid instance by altering the Preorder instance. For example, suppose we want the first name that we see, but the oldest age. Easy peasy:

instance Preorder Fact where
  (Name _) <~ (Name _) = True
  (Age m)  <~ (Age n)  = m <= n
  _        <~ _        = False

> mconcat . map fact $ [Age 23, Name "Brent"]
PStar {unPStar = fromList [Name "Brent",Age 23]}
> mconcat . map fact $ [Age 23, Name "Brent", Age 24]
PStar {unPStar = fromList [Name "Brent",Age 24]}
> mconcat . map fact $ [Age 23, Name "Brent", Age 24, Name "Joe", Age 26]
PStar {unPStar = fromList [Name "Brent",Age 26]}

Of course, we could have done this with the Record model, but it wouldn’t be terribly elegant. But we’re not done: let’s say we want to remember the oldest age we find, and the first name, unless the age is over 50, in which case we don’t want to remember the name (I admit this is a bit contrived)? That’s not too hard either:

instance Preorder Fact where
  (Name _) <~ (Name _) = True
  (Age m)  <~ (Age n)  = m <= n
  (Name _) <~ (Age n)  = n > 50
  _        <~ _        = False

> mconcat . map fact $ [Name "Brent", Age 26]
PStar {unPStar = fromList [Name "Brent",Age 26]}
> mconcat . map fact $ [Name "Brent", Age 26, Age 45]
PStar {unPStar = fromList [Name "Brent",Age 45]}
> mconcat . map fact $ [Name "Brent", Age 26, Age 45, Age 53]
PStar {unPStar = fromList [Age 53]}

This would have been a huge pain to do with the Record model! Now, this isn’t an unqualified improvement; there are several things we can’t do here. One is if we want to be able to combine facts into larger compound facts: we can do that fairly straightforwardly with the Record-of-Maybes model, but not with the preorder-monoid model. We also can’t easily choose to have some fields be left-biased and some right-biased (the Monoid instance for PStar has left-bias built in!). But it’s certainly an interesting approach.

Now, one thing we do have to be careful of is that our Preorder instances really do define a preorder! For example, at first I tried using in the above Preorder instance instead of , and was confused by the weird results I got. But such a Preorder instance violates transitivity, so no wonder I was getting weird semantics. =) It would be interesting to reformulate this in a dependently typed language like Agda, where creating a Preorder could actually require a proof that it satisfied the preorder axioms.

Thanks to Conal Elliott for some suggestions on making the formulation in the previous post more elegant — we’ll see what comes of it!

An interesting monoid

The other day I was just sort of letting my mind wander, and I came up with an interesting monoid, which I’m calling the “monoid of partial knowledge”. So I thought I’d write about it here, partly just because it’s interesting, and partly to see whether anyone has any pointers to any literature (I’m sure I’m not the first to come up with it).

Recall that a monoid is a set with an associative binary operation and a distinguished element which is the identity for the operation.

Now, given a total order on a set with a smallest element , we get a monoid , where denotes the function which determines the larger of two elements, according to the total order on . is clearly associative, and has identity . Taking a list of elements of and summarizing it via this monoid corresponds to finding the maximum element in the list. If you think of receiving the elements of the list one by one, and applying to each new incoming value and the value of an accumulator (storing the result back into the accumulator, which should obviously be initialized to ), at any given time the value of the accumulator represents the ‘current best’, i.e. the largest element among those received so far.

The idea I had was to generalize this from a total order to a preorder. Recall that a preorder is a set equipped with a reflexive, transitive binary relation, often denoted . That is, for any , we have ; and implies . If is also antisymmetric, that is, implies , it is called a partial order, or poset. Then if or for any two elements and , we get a total order, but for a general preorder some pairs of elements may not be comparable — that is, there may be elements and for which neither nor holds.

Let’s think about this. Suppose we are given a preorder with an initial object (an initial object in this context is an element which is all other elements). We’ll initialize an accumulator to , and imagine receiving elements of one at a time. For a concrete example, suppose we are dealing with the preorder (actually also a poset) of positive integers under the divisibility relation, so our accumulator is initialized to 1. Let’s say we receive the integer 4. Clearly, 1 divides 4, so we should replace the 1 in our accumulator with 4. But now suppose we next receive the integer 5. 4 does not divide 5 or vice versa, so what should we do? We would be justified in neither throwing the 5 away nor replacing the 4, since 4 and 5 are not related to each other under the divisibility relation. Somehow we need to keep the 4 and the 5 around.

The solution is that instead of creating a monoid over itself, as we can for sets with a total order, we create a monoid over subsets of . In particular, consider the set of subsets of which do not contain two distinct elements for which . Since we are dealing with subsets of , we can actually drop the restriction that contain an initial object; the empty set will serve as the identity for the monoid.

We then define the monoid operation on two such subsets as

where

and

.

In words, we combine subsets and by forming the set of objects from which are not any others, with the exception of objects where both and ; in this case we keep but not . This introduces a “left bias” to ; there is also an equally valid version with right bias (in particular, ).

Now, let’s show that this really does define a valid monoid. First, we need to show that is closed over . Suppose . Suppose also that are distinct elements of with ; we’ll derive a contradiction. First, we cannot have or by definition of . Now suppose . The fact that together with the definition of imply that we must have , a contradiction. Finally, suppose . Again, by the definition of we must have . But then the fact that , together with the definition of and the facts that and imply that , a contradiction again. Hence contains no such pair of elements.

The fact that the empty set is the identity for is clear. (Incidentally, this is why we require that none of the sets in contain two distinct elements with one the other: if were such a set, we would have .) I leave the associativity of as an exercise for the reader (translation: this post is already getting long, the associativity of seems intuitively obvious to me, and I don’t feel like formalizing it at the moment — perhaps I’ll try writing it up later). I also leave as an interesting exercise the following theorem: if are both finite and nonempty, then is also finite and nonempty.

In our example from before, we could now begin with in our accumulator. After receiving the singleton set , our accumulator would have that singleton set as its new value. Upon receiving , our accumulator would become . Receiving would result in (5 divides 10, so the 5 is discarded); if we later received , we would simply have in our accumulator (both 4 and 10 divide 20).

I like to think of this as the monoid of partial knowledge. If we consider to be a set of facts or beliefs, some better (more reliable, useful, correct, complete, etc.) than others, then elements of correspond to possible sets of beliefs. describes how a set of beliefs changes upon encountering a new set of facts; some of the new facts may supersede and replace old ones, some may not impart any new information, and some may be completely new facts that aren’t related to any currently known.

Now, why can this be thought of as a generalization of the monoid on a totally ordered set? Well, look what happens when we replace in the definitions above with a totally ordered set with relation : first of all, the restriction on (no two elements of a set in should be related by ) means that contains only the empty set and singleton sets, so (ignoring the empty set) is isomorphic to . Now look at the definition of , with replaced by (and replaced by ):

But and are both subsumed by , so we can rewrite this as

.

An analysis of is similar, and it is clear that .

I note in passing that although it might appear shady that I swept that “ignoring the empty set” bit under the rug, everything really does check out: technically, to see a direct generalization of to , we can require that have an initial object and that contains only finite, nonempty sets. Then it requires a bit more work to prove that is closed, but it still goes through. I used the formulation I did since it seems more general and requires less proving.

Anyway, this ended up being longer than I originally anticipated (why does that always happen!? =), so I’ll stop here for now, but next time I’ll give some actual Haskell code (which I think ends up being pretty neat!), and talk about one relatively common design pattern which is actually a special case of this monoid.

FringeDC talk

My FringeDC talk has now been uploaded to Google video! A huge thanks to Conrad Barski, who took the effort to actually record the video and then wrangle it into digital form. Without further ado:

My FringeDC talk

The slides are here if you’d like to follow along.

In general I’m pretty happy with how it turned out. This is one of the first “real” talks I’ve given, though (although I did teach high school for two years), so I definitely learned a lot and have some good ideas for improving the next talk I give.

Comments or questions welcome!

ETA: the Java bug mentioned in the video was just fixed today! w00t!

Call for video cameras!

I’m posting this appeal here, in case anyone who reads it is planning to attend my talk on Saturday but isn’t subscribed to the FringeDC mailing list. I’d really love for my talk to be recorded on video, but so far no one has volunteered. Might you be that generous person…? =)

FringeDC formal meeting, March 22

I’ll be giving a talk about xmonad at next weekend’s FringeDC formal meeting — more details on exactly what I plan to talk about soon. In the meantime, the details are below. Come on out if you’re in the DC area, and if you’re not, I’ll post some slides and (hopefully!) video afterwards. (I’d really love for it to be recorded on video, so if you plan to come and would be able to record it, let me know!)

FringeDC Formal Meeting March 22nd at 1PM- Haskell Spectacular: XMonad, Zippers and More!

FringeDC is a group in Washington DC interested in Fringe Programming Languages (Lisp, Haskell, Erlang, Prolog, etc.)
www.lisperati.com/fringedc.html

Our next meeting features Brent Yorgey, who is well known in the Haskell community and a contributor to XMonad. For those who don’t know, XMonad (a purely functional windows manager) is often lauded (well, by me at least, but others as well :-) as a masterpiece in software engineering. It cleanly marries elegant functional programming code with the ugliest of uglies, the X windows system. Brent will be giving an intro to Haskell and explain the nuts of bolts of extending XMonad. As an opener, Philip Fominykh will be giving an opening presentation on Zippers, an exotic purely functional data structure popular among Haskellers!

The Meeting is will be held on Saturday, March 22nd. It is hosted by Clark&Parsia, a developer of OWL/Semantic Web reasoning software in downtown DC. After the presentation, we’ll grab some food nearby and talk programming languages.

Address:
926 N St NW Rear
Studio #1
Washington DC 20001
Google Map:http://clarkparsia.com/contact

Philadelphia, here we come!

I’ve just accepted an offer of admission to the PhD program in computer science at U Penn! In particular I’ll be working with the PL group. I’m super-excited — especially since I’ve now been out in the “real world” for four years. Not that I was particularly burned out at the end of undergrad, but I didn’t really know exactly what I wanted to do. Well, now I know: I want to go back to school! September is still a long way off… but oh well, I’ll deal. =) Now to find a job for Joyia, and a church, and a place to live…

Patch theory, part II: some basics

(Previous posts here, and here.)

So, let’s talk about patch theory! I should start by saying that I have obviously drawn a lot of ideas and inspiration from darcs, and especially from the wikibook explanation of darcs patch theory, but I do think there might be some nuggets of original contributions here (in subsequent posts at least), but I’m not yet familiar enough with the literature to really say.

In this post I’d like to start off by giving an overview of the basics of patch theory, to lay a foundation for the things I plan to talk about in future posts.

Patches and documents

A patch is essentially a function which takes a document as input and produces another document. A “document” is just any sort of thing that we might wish to modify. In the context of darcs, a “document” is an entire directory tree; in a collaborative editor it would be just a single file.

Note, however, that patches are partial functions: not every patch can be applied to every document! For example, a patch which (to use a darcs example) makes a modification to file X cannot be applied in a context in which there is no file X. As another example, a patch to delete the character ‘z’ from the first position in a file cannot be applied to a file which begins with the character ‘y’. But thinking of patches as partial functions is not a very useful point of view. The main point is that the context of a patch matters—both the context to which it is applied, and the context which it produces. We will write to denote a patch which, when applied to document , produces document . We say that is the domain of , and is its codomain.

Of course, this immediately suggests…

The category of patches

Patches can be most usefully viewed as morphisms in a category with documents as objects. (If you don’t know any category theory, don’t worry: the rest of this post doesn’t particularly depend on any background knowledge.) To wit: given two patches and , we can compose them to form the composite patch , which has the same overall effect as applying first , then . (Of course, there are good arguments for writing this composition in the other order, like —function composition and all that—but this is the way I’ve been writing it, so get used to it. =)

Since patches can be viewed as functions from one document to another, and function composition is associative, patch composition is obviously associative as well. Finally, for every document , we will have a null patch which sends to itself.

Since we’re very interested in the “undo” operation, we also require that every patch must be invertible—that is, for every patch there must be a corresponding patch , such that and . Of course, this also means that .

So, the category of patches is actually a groupoid. A groupoid can be viewed as a set with inverses and a partial binary operation—here, the partiality comes from the fact that not all patches can be composed—but I prefer the category-theoretical view of a groupoid as a category with all morphisms invertible. Because really, who likes partial functions?

(A quick note: I’m playing a little fast and loose with patch equality here; when I say that two patches are equal, what I really mean is that they are observationally equivalent. So technically, the morphisms in the category of patches are equivalence classes of patches; in a particular implementation there may be patches with distinguishable representations which nevertheless have the same effect — that is, they produce the same output document given the same input document.)

Commutation

The other central operation on patches is that of commutation. As a motivating example, let’s consider the problem of undo in a text editor. Suppose, starting from a blank document, you sequentially apply the five patches through . Therefore, the current document state can be described by the composite patch

Now suppose you want to undo your last change. This is easy: since every patch has an inverse, you can just apply to obtain

(In practice, to remember the fact that you performed an undo, and to allow the possibility of redo in the future, an editor would retain the patches and rather than deleting them. But the overall effect is the same.)

Nice. But what if you are using a collaborative editor, and changes and were made by a different user (perhaps you are not even aware of their changes, if they were made in a different part of the document)? You want to undo patch , which is the last change that you made, but simply applying doesn’t work anymore, since cannot be composed with (the codomain of does not match the domain of )!

We need a way to “move” to the end of the patch sequence, like this:

Now we can simply apply the inverse patch to undo.

This process of reordering patches is referred to as commutation. The composite patch commutes to the composite patch (written ) if , and represents “the same change” as , and similarly for and .

Of course, “the same change” is quite vague, but it’s a necessary restriction; just requiring that is not enough, since in that case we could, for example, choose and —obviously not what we want. I’ve wondered whether there is a formal way to pin this down, although I think it might depend on the particular document type being used. However, for now a simple example should suffice.

Suppose Alice and Bob are editing a document together, which contains the word “cap”. First, Alice inserts the letter “m” at position 2 (positions are zero-indexed), to produce the word “camp”; call this patch . Next, Bob inserts the letter “r” at position 1, producing the word “cramp”; call this patch . Now Alice decides that she wishes to undo her change, since “crap” is a much better word than “cramp”. In order to do this, the patches and must first be commuted: we want to find patches and such that adds the letter “r”, adds the letter “m”, and when composed, still sends the document “cap” to the document “cramp”. In this case, it’s not too hard to see that should still insert “r” at position 1, but now should insert “m” at position 3 instead of position 2, since the location in the document where inserted an “m” has been “shifted over” by the patch .

After commuting and , the patch can now be applied to undo Alice’s change.

Now, the big question: does every pair of patches commute? In the case of a version control system like darcs, the answer is definitely “no”. For example, suppose creates file X, and adds some content to file X. There is no way we can meaningfully reorder the two patches—content cannot be added to file X before it has been created! In the case of a collaborative editor, on the other hand, the answer is… maybe? This is one of the central questions I plan to address in later posts.

If the patches and commute, a nice property that we’d like to have hold in all cases is

,

that is, we want the commute operation to be an involution, so applying it twice is the identity. This also has some interesting implications for the theory of a collaborative editor, and it will come up again in later posts, too!

Merging

The other fundamental operation on patches, of course, is merging: taking two patches made to the same document in parallel, and merging them into a sequence of patches that performs both changes. In a version control system, this happens all the time, when two people have the same source and start making changes to it at the same time, and later want to get the other’s changes as well. It happens in a collaborative editor, too, because of network latency. When you start typing something, someone else may have already typed some things that have not yet propagated to you over the network; when you finally receive the propagated changes, they will have to be merged with the changes you have made.

It turns out, however, that merging is really not a fundamental operation at all! It can be implemented very simply in terms of commutation and inverses. Here’s the situation: suppose we have two patches, and , made in parallel to the same document, . We want to find a patch which performs the “same change” as , but which can be composed with .

How can we find ? The key is to note that if we invert , this looks just like the diagram for commuting two patches, but on its side!

In other words, to merge patches and , we first commute to obtain . Then we can simply discard . (Of course, this sounds like wasted computation, but supposing we were to use some sort of lazy language… =) Let’s illustrate this with a simple example. Alice and Bob are at it again; this time, they are editing a document containing the word “hat”. Alice adds the letter “c” to create the word “chat” (patch ). At the same time, Bob adds the letter “s” to create the word “hats” (patch ). Now Alice’s editor gets Bob’s patch, and needs to merge it with Alice’s. Commuting yields , as shown in the diagram, and Alice’s editor applies patch , producing the document “chats”.

Of course, at the same time, Bob’s editor receives Alice’s patch, and performs the dual merge shown below.

This illustrates an obvious and important property that must hold: merging must be symmetric! From the above two diagrams, we must have .

Onward

Alright, enough for today! Next time: some actual Haskell code implementing all of this for a simple document type!