May 8 2008

Did you know that you can actually generate a monad automatically given any endofunctor? This is the free monad of that functor. How do we perform this magic trick? Quite simple, everything follows from this data type:

```data FreeM f a = Return a
| Bind (f (FreeM f a))```

In this, the f parameter is just the functor we are going to build a monad for, and a is the type of the contents of a FreeM value. We've said that the free monad can either contain such a value directly (boring) or it can contain a value of it's own type, but wrapped in the functor f - hmm! As an aside, I'm not sure that Bind is strictly the best name for this constructor, but I like the symmetry.

If you want to build up some intuition about this definition, you can think of it as specifying values that consist of an actual a (in a Return constructor) but nested within a finite number of functor applications.

As another aside, you might like to know that actually Haskell would let you create an infinite stack of functors fairly straightforwardly, since all its data declarations are actually really co-data declarations. Don't do this, though, or you might start having some non-termination issues

Having got this far through the post, you won't be surprised to learn that we can make this definition into a functor itself. Here comes the implementation:

```instance (Functor f) => Functor (FreeM f) where
fmap f (Return a) = Return (f a)
fmap f (Bind fm) = Bind (fmap (fmap f) fm)```

That Bind case looks pretty scary, doesn't it? The leftmost fmap call is that from the functor f that we are making a free monad over, and the rightmost one is actually a recursion back into the fmap we are currently trying to compute, but one functor "lower".

Essentially all we are doing in this definition is fmaping all the way down our tower of functors until we finally reach a nice sane a value in the Return case, which we handle in the obvious way.

So far so good. But we've come all this way and still don't have a monad, even though I promised you one at the start. Well, let's sort that out now! Instead of defining one using the usual Haskell >>= operator, I'm going to use the more category-theoretical join :: Monad m => m (m a) -> m a construction:

```joinFreeM :: Functor f => FreeM f (FreeM f a) -> FreeM f a
joinFreeM (Return a) = a
joinFreeM (Bind fm) = Bind (fmap joinFreeM fm)```

If you think about the type of this operation, what we want to do is stick the pile of functors associated with the outermost FreeM onto the pile of functors associated with the innermost one, to produce one cohesive functor pile. How we go about this is fairly straightforward: in the Return case there are no functor applications on the outermost FreeM so we just give back the inner one. The Bind case simply recurses its way down the whole functor pile, mushing them together in some sense .

That was it. The code to actually declare a Monad instance is entirely boilerplate given that we have a join operation:

```instance (Functor f) => Monad (FreeM f) where
return = Return
m >>= f = joinFreeM ((fmap f) m)```

Pretty neat! But what, pray tell, are these things actually useful for? Well, after I'd implemented my own version of free monads I found that Wouter Swierstra's excellent paper "Data types à la carte" had already publicly demonstrated the same thing (in passing) with his Term data structure, and he has some nice examples. For instance, consider this functor:

```data Zero a = Zero
deriving (Show)

instance Functor Zero where
fmap _ Zero = Zero

zeroTest :: FreeM Zero Int -> FreeM Zero Int
zeroTest my = do
x <- return 5
y <- my
return \$ x + y

-- > zeroTest (return 1)
-- 6
-- > zeroTest (Bind Zero)
-- Zero```

Remind you of anything? It should: it's just the Maybe monad!

```data One a = One a
deriving (Show)

instance Functor One where
fmap f (One a) = One (f a)

oneTest :: FreeM One Int -> FreeM One Int
oneTest my = do
x <- return 5
y <- my
return \$ x + y

-- > oneTest (Return 2)
-- 7
-- > oneTest (Bind \$ One \$ Return 2)
-- One 7
-- > oneTest (Bind \$ One \$ Bind \$ One \$ Return 2)
-- One One 7```

Something like the identity monad: pretty boring! What if we try something a bit more exotic (and not mentioned in Wouter's paper) like the list functor?

```listTest :: FreeM [] Int
listTest = do
x <- Bind [Return 1, Return 2]
y <- Bind [Return 3, Return 4]
return \$ x + y

-- > listTest
-- [[4,5],[5,6]]```

But for want to a call to concat, this looks strikingly similar to the list monad - and all without ever having to define it. Interesting stuff!

I've found that the fun of free monads is that you can play around with any functor you like and get something interesting generated from it. Since they're free, this happens without you typing a single line of non-trivial code, so I encourage you to go and try a few out quickly and see what you can make happen!

May 1 2008

## Fixing File Associations Eaten By Parallels Desktop

I use OS X, and so for those rare cases where I must deign to run a program designed for Windows I make use of my copy of it hosted in Parallels Desktop. Now, Parallels has been generally good to me, but I recently came across the problem documented in this forum thread where its ability to launch Mac applications from Windows caused some basic file associations in Windows-land to stop working. For example, Excel files were listed as "xls_auto_file" by Explorer and double clicking on them only gave me the "Open With" dialog: not very helpful.

The thread does suggest a means of solving the problem, by creating a batch file that re-associates a white-list of some of the possibly affected extensions, like this:

```REM Restores MS Office File Type Associations
assoc .doc=Word.Document.8
assoc .dochtml=wordhtmlfile
assoc .docmhtml=wordmhtmlfile
assoc .docxml=wordxmlfile
assoc .dot=Word.Template.8
assoc .pot=PowerPoint.Template.8
assoc .pps=PowerPoint.SlideShow.8
assoc .ppt=PowerPoint.Show.8
assoc .rtf=Word.RTF.8
assoc .wbk=Word.Backup.8
assoc .xlc=Excel.Chart.8
assoc .xlm=Excel.Macrosheet
assoc .xls=Excel.Sheet.8
assoc .xlt=Excel.Template
assoc .xlw=Excel.Workspace```

However, this felt a bit ad-hoc to me, and in particular some of the extensions that were affected for me were not on the list. Thus, like any good programmer I went off and whipped up a utility designed to undo the damage inflicted on my poor defenseless HKEY_CLASSES_ROOT by Parallels.

Using it is pretty simple: just click "Scan" and then "Fix Selected" repeatedly until the scan finds nothing more of interest. Now, before I give you a download link to the utility, I need to give you the standard disclaimer to which you must agree in order to use it:

This utility is provided on an 'as is' basis, without warranties of any kind, and no warranty, express or implied, is given that the operation of the utility is correct or safe to use. I do not accept any liability for any error or omission. Use of the utility is at your own risk.

Sorry for the legalese but this utility is modifying your registry and hence (though I feel it is highly unlikely) could get something quite, quite wrong. You would be also wise to have a backup of the HKEY_CLASSES_ROOT registry branch to restore in case you aren't happy with the changes made by the utility.

That said, without further ado here is the utility and its source code (C# 3.0), both of which (being of my sole authorship) I release into the public domain. I hope someone else finds it useful!