Well I got slightly distracted from my PeCoWriMo project. No particularly good reason – I was just feeling a bit disenchanted with the subject matter and Haskell was annoying me slightly (as usual). Nothing enough to actually derail me on it’s own, but I got to thinking about a problem I’d worked on before and decided to do some more work on it.

And in keeping with the mild irritation with Haskell and the “oh for the love of god anything but more ruby” I decided to do it in another nicer, friendlier language.

Err, that is to say, C.

The problem this is working on is that of finding a minimal feedback arc set in a weighted graph (although I’ve actually posed it as a maximization problem). This boils down to the following problem:

Given N points and a weight function w(x, y) find an enumeration x_1, …, x_N that maximizes sum_{i < j} w(x_i, x_j) The main application I care about is voting, but I'm sure it has other uses. Code is available on github

As previously mentioned, I’m currently writing a little Haskell library. Here are some notes on the API’s many iterations.

Background

The primary feature of this API is building a search index for things in a metric space.

What’s a metric space? It’s essentially points together with a “distance function” d, satisfying the following rules:

1. d(x, y) == 0 iff x == y
2. d(x, y) == d(y, x)
3. d(x, z) <= d(x, y) + d(y, z) [this is called the triangle inequality]

And the main operations we want the search index to be able to support are:

1. Given a metric and a set of points, build an index
2. Given an index I, a point x and a distance e, give me all points y in I such that d(x, y) < e

The question I will be looking at here is what the right design for the metric API is.

Attempt 1: Passing around a distance function

This was pretty straightforward. Metrics are represented as a function with the following type signature:

type Metric a = a -> a -> Double

and Indexes have the signature

data MetricSearchIndex a

You pass such a function in when creating the search index. Done.

Unfortunately, this turns out not to be adequate for my goals.

Why?

Well, one of the things I want to be able to do (I’ve not done it yet) is write a command line interface to this program. In order to do that, I really need to be able to save model files. In order to do that I’d like to use Data.Binary. It’s pleasant to use and produces very clean binary formats that if you had to would be easy to write a manual parser for in whatever language you wanted unlike many other serialization libraries.

But unfortunately it can’t serialize functions. And really that’s not surprising – they’re far too opaque to do anything about.

So, the explicit function passing was out.

Metric type class, take one

The next obvious thing to do is to make Metric a type class with the following signature:

   class Metric a where
      distance :: a -> a -> Double

This worked reasonably well. At some point during it I realised that actually there was another function on metric spaces that was really useful, so I added that and the class became the following:

   class Metric a where
      distance :: a -> a -> Double
      bound :: a -> Double -> Double -> Double
      bound _ = (+)

What's the bound parameter for? Well, remember the triangle inequality? It's pretty useful. In particular it lets us deal with the following case:

Suppose we have a point c and a distance r. We denote the set of points y with distance c y < r as B(c, r). We're then looking for everything in the ball B(x, e). We can completely eliminate anything in B(c, r) if d(x, c) >= r + e.

Why? Because if there were some point y which was in both balls then we would have d(x, c) <= d(x, y) + d(c, y) < r + e by the triangle inequality. So the result of this is that the triangle inequality lets us aggressively prune entire branches of the tree without looking at them. That's the basic idea behind the sort of metric search we're doing. But it turns out that there's an interesting class of metrics which satisfy a much stronger bound: d(x, z) <= max(d(x, y), d(y, z)). These are called ultrametrics. When performing searches on things we know to be ultrametrics we can prune the tree even more aggressively. Rather than having a "isAnUltrametric" boolean function, capturing this property as the bound method seemed more sensible. The rule to be satisfied is then: distance x z <= bound x (distance x y) (distance y z)

What's the x parameter there for? It's a dummy. You need something of type a to dispatch the function on, but its value shouldn't be used. A bit ugly I know...

So, anyway, this type class now largely works. What's wrong with it?

Going back to the command line interface: How I wanted it to work was that it's indexing finite dimensional vectors in an l^p space. I wanted p to be a parameter. This means that it can't be part of the type, so you want one LP type. This means that you then have to attach the value of p to every instance of the type, two vectors need to check whether they're being compared with different values of p, etc. The result is slower, more irritating to work with and has a higher memory footprint. Premature optimisation? Maybe. But when what you're designing is a library it's important to get the performance decisions right. And definitely let's not discount the "more irritating to work with" part.

Metric class, now with multiple parameters

So we're going back to the first version where we passed an explicit metric around. Our two constraints which that didn't satisfy are:

1. We need (in principle) to be able to serialize metrics
2. We need to include the bounds function in it

Metrics need to be able to encode arbitrary functions, so in order to serialize them we're going to effectively have to explicitly defunctionalize and make different metrics be encoded by different types. So this is how we do it with a multiparameter type class:

   class Metric m a where
      distance :: m -> a -> a -> Double
      bound :: m -> Double -> Double -> Double
      bound _ = (+)

This changes the metric search tree to encode the metric type in its type parameter:

data MetricSearchTree m a

What's the problem with this?

Well, it doesn't work. The problem is that because the type "a" does not appear in the bound function it is unable to tell which instance of this type class you are using to get bound. The signature needs to be

   class Metric m a where
      distance :: m -> a -> a -> Double
      bound :: m -> a -> Double -> Double -> Double
      bound _ _ = (+)

This was really irritating to use as well as being aesthetically displeasing, so I dismissed it.

At this point there is a correct fix, which if you're familiar with Haskell you may well have already spotted, but I went with a wrong one at first. Which leads us to

Metric class with an associated type synonym

This uses associated type synonyms to express what the points of the metric space are.

   class Metric m where
      type Point m
      distance :: Point m -> Point m -> Double
      bound :: m -> Double -> Double -> Double
      bound _ = (+)

The metric search trees become parameterized by the metric alone.

data MetricSearchTree m

This was relatively pleasant to use. What was the problem?

Maybe this was me doing it wrong, but I found it almost impossible to write generic code with this.

For context: I have a test suite which is a bunch of quickcheck tests parameterized by the metric and the type of point in the metric space. I need to be able to generate arbitrary lists of points in that metric space, as well as have them implement Eq and Show for testing.

I simply couldn't make this work. Near as I can tell. Writing a type constraint as (Metric m, Arbitrary (Point m)) => fails with "no such type constuctor Point". Letting GHC infer the type results in it being unable to infer the relevant constraints. I struggled for a good 40 minutes or so, with the help of a few people in #haskell (though no one who would admit to knowing the associated types thing very well) before giving up. I think I've since figured out how to do it (you can introduce a type variable and add a constraint that the type variable is equal to the associated type synonym. Maybe. I've not tried it), but the eventual solution was nicer anyway.

So, where to now?

Metric class with a functional dependency

It turns out that there's a feature that's exactly for the sort of problem I ran into earlier. It's not one I'd used before, and I'd got the impression that it was generally recommended that you use associated types instead (I don't know if this is correct), but it turned out to be easy to understand and straightforward to use.

   class Metric m a | m -> a where
      distance :: m -> a -> a -> Double
      bound :: m -> Double -> Double -> Double
      bound _ = (+)

What does this do?

It says "For each type m, only one type a is allowed to have an instance of this". This means that you don't need the a in the signature of bound to deduce the full instance declaration because once you know m there's only one valid instance. It's very much like the associated type but implemented in a way that means you can easily constrain the type.

I've now rewritten all the code to use this version. I'm relatively happy with it: It meets all the requirements I've had so far and isn't especially cumbersome to use. The process of getting here was pretty annoying though.

This is just a quick note to say I have a new blog called Imbibliotech.

This is not a replacement for the current blog – it’s a subject specific blog on the topic of drinking (primarily cocktails and spirits, but also other things including coffee), as I’m doing a bunch of learning and experimenting on that subject which I felt would be better posted elsewhere.

I drink a lot of gin and tonics. Mostly this is a function of the fact that I don’t drink beer, rarely drink wine and, while I like a good cider, am rarely in the mood for it.

That being said, I’ve always really liked the gin and tonic. It’s a nice drink.

When talking with Ryan Alexander over drinks one evening, he reported some experimentation he’d done, trying to find the best gin and tonic combination.

This struck me as a good idea. I must admit, most of the gin and tonics I’ve consumed in my life have been schweppes and bombay sapphire. It’s a perfectly serviceable drink, but surely with better ingredients it could be a better drink?

So I set forth and bought lots of nice gin and some nice tonic water and began to experiment.

As it turned out, what I discovered is that I really like gin without the tonic water. Once you use a decent gin, it has much more possibilities than just drowning out the flavour with quinine and sugar. Don’t get me wrong, I still really like gin and tonics, particularly if you use one of the more spicy gins, but I also really like neat gin, and martinis.

The following are the gins I have tried over the last few weeks:

• Whitley Neill
• Sipsmith
• Tanqueray No. 10
• No 3. London Dry Gin
• Sacred Gin
• Aviation
• Dry Fly Gin

I’d also previously had:

• Hendricks
• Tanqueray export strength
• Bombay sapphire

Of the new ones, the only one I really didn’t like was the Dry Fly. It has weird overtones of whiskey and salt (really. It’s based on a wheat liquor and actually does have added salt). I feel like there might be something it’s good in (I keep meaning to try it in a ruddy mary), but I’ve not found it so far.

The ones I would recommend unreservedly are the Whitley Neill and the Sipsmith. The Whitley Neill is quite mild – don’t use it in a G&T, it will drown, but it’s very nice neat and quite good in a martini. The Sipsmith has a similar flavour to it, but much more of a kick (tastewise – they’re about the same in alcohol content with the Whitley Neill actually fractionally stronger). It seems to be very versatile – it produces good martinis, good gin and tonics and is rather nice neat. If I were drinking the gin neat I’d probably choose the Whitley Neill, but for the other uses the Sipsmith seems nicer to me.

(Side note: As you’re probably noting, this isn’t a proper formal alcohol review. This is more just “This is what I tried, these are what I liked”).

For gin and tonics, the combination I’ve been really liking is the Aviation with Fever Tree tonic water. The Aviation is quite spicy (though less so than the Tanqueray) and so the flavour is easily discernable through the otherwise quite strong tasting Fever Tree.

The Sacred gin is nice, but until today I’d not found anything I really liked it in – it has a bit of an odd flavour neat, and I felt that while it was nice in a G&T it wasn’t really living up to its promise. Today I tried it in a classic martini (about 3 parts gin to 1 part vermouth) with Noilly Prat vermouth, which was excellent. This may be my new favourite Martini (although admittedly I’m not yet a connoisseur of the subject).

All told, this has been a really good learning experience. Gin is much more interesting a drink than I had previously realised, and significantly more versatile.

The only downside is that I now have ten bottles of gin in my flat. Oh well. Bottoms up!

…man that title is a mouthful. I’m not really sure how to better summarise this though.

My friends Dave and Rachel came round for dinner last night. Rachel is vegan, and I haven’t cooked anything vegan in ages, so I was struggling a bit to come up with something. After some googling for inspirational recipes (which this is not an implementation of any of, but they gave me some ideas) and a quick run to whole foods, this is what I came up with.

It needs some refinement in order to turn it into a proper recipe, but it was extremely tasty, so I will totally make this again. A lot of it.

Miso-Sake Quinoa

This is pretty simple to make. You make quinoa as normal, but you add brown rice miso and replace some of the water with sake. The proportions I used were one cup quinoa, one cup water, 3/4 a cup of sake and a very heaping dessert spoon of brown rice miso paste.

This turned out to not be enough liquid. I’m not sure why – it would have been enough if it were water. It might be that the sake evaporates faster, it might be that the salt from the miso slows down the cooking of the quinoa. Either way, I had to keep topping it up with water.

Peanut-Sesame sauce

This contained about equal portions of crunchy peanut butter, boiling water, sesame oil and brown rice vinegar. Mix it all up in a jar and alternately shake vigorously and whisk with a fork until you’ve got a smooth creamy sauce.

The main dish

This requires the sauce and the quinoa as above. Other than that it involved:

• About an inch of stem ginger
• A third of a red cabbage
• 5 medium sized carrots
• Two packages of Taifun almond and sesame smoked tofu
• Vegetable oil for frying
• A bit of salt

The salt is really to help things fry rather than for flavour (this recipe has plenty of salt. Possibly too much, although it doesn’t taste like it’s too salty). Feel free to omit it.

By the way, the Taifun smoked tofu is amazing. If you’ve not tried it, you definitely should. It’s by far my favourite form of tofu I can buy in the shops. I’d recommend it even if you think you don’t like tofu – I’ve fed this to various people who thought that way and they rather enjoyed it. (Disclaimer: Not affiliated with them in any way. I just eat their food).

Then the instructions are simple:

1. roughly julienne the cabbage and carrots
2. chop up the ginger
3. Fry it all until the carrots are starting to turn soft
4. Chop the tofu into roughly cm cubes
5. Add it to the mix and fry until the tofu is reasonably cooked (it can be eaten raw, so this doesn’t need to be very long
6. Add the peanut sauce, stir until thoroughly coated
7. Add the quinoa, mix thoroughly and let it cook for a few more minutes
8. Eat

Conclusions

As Dave put it, “It tastes very fancy”. There are a fair few different flavours in here (ginger, peanut, sesame, miso, sake), which given that I created this recipe more or less ex nihilo could have gone horribly horribly wrong (some flavour combinations which seem like a good idea turn out to really not be). Fortunately it didn’t, and the different flavours turn out to complement each other very well!

The miso-sake quinoa was definitely a win. I’ll make that in other contexts (and hopefully figure out the right proportions to get it to cook properly). If I were serving it on its own rather than as part of a larger dish I would probably reduce the amount of sake (and maybe the amount of miso) slightly, but in this the proportions were just about right.

The peanut sauce is something I’ve made before a few times, but it’s a really nice easy way to make things very tasty. If I weren’t using the miso quinoa I would probably have added soy sauce to it, but this recipe really didn’t need more soy.

Other than that, I’m not sure what I’d do differently other than minor tweaks and figuring out good proportions for things. Maybe experiment with different vegetables, though carrot and cabbage was a surprisingly good base for this.

All in all, this was extremely tasty and I’ll definitely be making it again.