Luke Randall

Implementing the reservoir algorithm in Haskell

2012-04-20T00:00:00-07:00

Implementing the reservoir algorithm in Haskell

20 April 2012 – Cape Town

I’ve been working on a small project lately, for which I’ve been using Haskell. Part of it entailed implementing Vitter’s Algorithm R for reservoir sampling. It’s a simple enough algorithm: given a list with n items (where n is unknown), it allows us to randomly choose k samples from this list.

It works by utilizing a reservoir of randomly selected items of size k. Initially, we populate our reservoir with the first k items from the list. Thereafter, with k/i probability (where i is the number of items we’ve seen) we replace an item in our reservoir. We do this by taking a random number r between 1 and i, and if it falls between 1 and k we replace the r th element with the new item.

If all of that still sounds complicated, it’s only because I managed to complicate my explanation. The wikipedia page has a nice pseudocode implementation which should make things clear.

I found a number of existing Haskell implementations, but all of them seemed to rely on performing a single pass over the input data before returning the randomly selected elements. That’s suitable for most use cases, but I need this to take a sample on an ongoing basis, where I can at any point retrieve the current samples, but still continue to add new ones. While this obviously isn’t impossible with the implementations I found, it would require replicating the list (or array, etc.) of samples each time I added a new one, which is undesirable for performance reasons.

Implementation

Knowing that for my use case I needed to take a relatively large number of samples I decided to use a mutable array as the container for the reservoir. This entails some trade-offs:

Pros

provides fast indexed lookup of elements (as opposed to O(n) lookup of lists)
does not require duplicating elements every time a change is made (as opposed to an immutable array)

Cons

lives in the IO monad
changes are destructive

The cons are both related to not duplicating the data structure on updates: updating the array would have to require either duplicating it or mutating it. Whilst this should make sense logically, it is also confirmed by looking at the array source, which provides two functions for converting IArrays to MArrays, thaw and unsafeThaw. thaw copies the contents of the IArray to an MArray, whilst unsafeThaw provides mutable access to the array, either in-place or by copying the array’s contents (it makes no guarantees about which).

As an aside, another approach would be to use a DiffArray, which provides a pure – ostensibly immutable – interface but uses a mutable array under the surface. As updates are made to the array, they happen in-place and the changes required to return it to its prior state is recorded. This means that references to the old array return the old contents as expected, but at the cost of having to compute it by applying the list of changes needed to undo any updates that were made. However, since I had no need of this (and because the current DiffArray implementations performance is horrible) I didn’t try this approach.

Since an update mutates the array, the only option was to put it in the IO monad. However, this led to complications in that parts of the data structure – the array of samples – were mutable, whilst the rest – current pool size and total sample count – weren’t. This meant if you added a sample then referenced the original reservoir instead of the new reservoir it returned you would find the sample had been updated, but the size and count hadn’t. This seemed pretty horrible to me: since the sample had been updated a casual examination of the reservoir would indicate that it had updated in place, and the average user could easily make the false assumption of thinking they didn’t need to do anything with the return value of addElem. To rectify this, I decided to make reservoirSize an IORef, so that I could likewise update it in-place. This hopefully makes the behaviour more consistent for the user.

What’s next

At this point, the biggest thing I’ve gotten out of this is really the knowledge gained. The code itself will likely all be thrown away in the next few weeks (when I hope to have a bit of free time again). Future work will probably be:

measure performance
try using vectors
write some decent tests
make the code less likely to make people cry

Right now I have no idea of the performance of the implementation. This means that for the reservoir sizes I’ll be using, immutable data structures could prove to be fast enough, or conceivably even faster than the current structure with its use of IORefs and the like. An important first step then is writing benchmarks. With the new release of cabal and its support for benchmarking, this is a perfect chance to do it. Having benchhmarks also means writing an implementation using vectors will allow me to compare their performance instead of just going on the assumption that they should be faster. If this all seems obvious I suppose it’s because it is.

After that, I’ll have a chance to finally use QuickCheck and write some tests. Assuming of course that I can figure out how to use it to test non-deterministic data structures.

At the end of my hacking, it was satisfying to have implemented something in Haskell, but at the same time slightly disheartening for it to have taken so long to achieve such a basic task. I think it’ll always be true that using languages you know well makes you more productive than using a new language, and I think that’s especially so with something as different to what I’m used to as Haskell is. At least with this done I’ve gotten a few steps closer to making Haskell one of my productive languages.

Architecting a Rails App

2012-02-03T00:00:00-08:00

Architecting a Rails App

3 February 2012 – Cape Town

I gave a talk yesterday at Rubyfuza about Architecting Rails Applications. Primarily I spoke about how the focus on MVC alone has provided an insufficient level of abstraction, causing our models to become a dumping ground for application logic. Using DCI allows us to decompose and manage this complexity. By turning the algorithm into a first-class object in our code, we can better reason about it, more easily test it, and encapsulate it. Like any design pattern, it’s not always applicable, and won’t solve every problem, but it is a useful tool. My slides won’t be as meaningful without the talk, but here they are:

I think an extra ten minutes would have been useful – there were certain things I had to hurry through to fit into the time slot and still have a couple minutes to answer questions. Chatting to Nick Sutterer afterwards, he mentioned that he would have liked to see a bit more time spent discussing contexts specifically. I agree – for a concept that’s so vital I didn’t spend enough time examining it. That’s something I will try rectify by exploring it in more detail here.

After the conference was done for the day, Sven Fuchs and I chatted for a bit, and he raised (not for the first time) the issue of whether #extend is too expensive to call during each request/response lifecycle. I was aware that it might be an issue with JRuby due to it clobbering the constants lookup cache (see this blog post by Charles Nutter for some details on why this is), and he said it was likely an issue with Rubinius as well. I don’t know, and I think it’s something worth investigating. I’ve seen some microbenchmarks on the matter, but I don’t know how much faith one can put in them. It seems to me they benchmark the cost of calling #extend itself, without taking into account the long term cost (ie across multiple requests).

Two things strike me whilst writing this – firstly, it’s possible (likely even) that for the average application the extra cost to lookup constants is not going to be what determines whether or not the system performs adequately, and secondly, there is nothing inherent in DCI that requires that we use #extend. The fact that DCI is happily used in statically typed languages would suggest that this is the case. There are various alternatives that have already occured to me, none of which I’ve thought through particularly well, and none of which I like, but nonetheless I think with further thought at least one idea would be found to be a workable solution. I’m interested to see what ideas others have on the matter.

One thing that came up in the questions at the end of the talk was that someone (as I recall Sven) asked about the usage of #call for the context. I was glad it was raised, as it’s something I forgot to mention during the talk. I owe the insight (as I indeed owe the code in question) to Mike Pack. He suggests #call in lieu of #execute, #run or the various other verbiage that others have suggested as it retains the same calling semantics were one to use a Proc instead of a class based approach to Contexts.

When it comes to DCI, I owe the understanding I have – but certainly not any misconceptions – to a wide variety of sources, but some I found particularly helpful were: Mike Pack, Andrzej Krzywda and Jim Gay; as well as the obvious duo of Trygve Reenskaug and James Coplien

Rubyfuza Again

2012-02-02T00:00:00-08:00

Rubyfuza Again

2 February 2012 – Cape Town

Later today I’ll be giving a talk at Rubyfuza. I’ll be posting the slides when I’m done.

Feedburner

2011-05-26T00:00:00-07:00

Feedburner

26 May 2011 – Cape Town

I’ve changed my Atom feed to use Feedburner, so for the 2 (hmm, that might be a generous total) of you following my blog, please point your feed reader at http://feeds.feedburner.com/lukerandall so that you can stay up to date. Thanks.

Monoids

2011-05-22T00:00:00-07:00

Monoids

22 May 2011 – Cape Town

In an effort to break the usual Haskell newbie cycle of writing another blog post on monads, my inaugural Haskell themed blog post will be about monoids, which I’ve found to be surprisingly interesting.

What is a monoid?

Simply put, a monoid is an algebraic type with an associative binary operation – ie an operation that has two operands – called mappend, and an identity element – an element that, when combined with another element using the aforementioned binary operation, leaves the element unchanged – called mempty. Disregarding the unfortunate choice of names, some examples might help to illustrate the concept:

The natural numbers form a monoid under addition, with the binary operation obviously being addition, and the identity element 0. Likewise, they form a monoid under multiplication, with the identity element being 1. In both cases, the truthfulness of this can be trivially tested. Addition and multiplication both take two operands. Further adding 0 to any number returns that number; multiplying any number by 1 returns that number.

What’s the point?

With such simple examples, one might wonder what utility there is in creating a type class for monoids. In truth, I feel the power of monoids comes from the fact that they are 1. rather general, and 2. very simple. Since there is no limitation on the binary operation beyond that it be associative, many things can be represented as a monoid. Looking at the Data.Monoid documentation one finds a number of monoid instances.

Folding with monoids

To illustrate the utility of monoids, let’s try using foldMap and a few monoid instances. For example, the Sum monoid can be used thusly:

foldMap Sum []
foldMap Sum [1,2,3]

which return respectively Sum 0 and Sum 6. “So what?”, I hear you ask. Well, consider the situation where you want to compute the sum and the product of a list. No problem:

foldMap (\x -> (Sum x, Product x)) [1..4]

which returns a tuple containing Sum 10 and Product 24. I suppose it would be more accurate to say it returns:

(Sum {getSum = 10},Product {getProduct = 24})

The getSum and getProduct wrappers are because there can only exist one monoid instance per data type, so Sum and Product are newtype wrappers around Num.

I’m still not impressed

Gosh, you really lack imagination, don’t you? Anything that obeys our monoid laws can be made a monoid. For example, consider two functions with type signature Monoid b => a → b. There exists a monoid for said functions, which means you can combine these two functions with mappend. What does this mean for you? As cgibbard wonderfully demonstrates – and indeed this is what first helped me to recognise the universal utility of monoids – using the Ordering data type, you can order a list using a variety of criteria simply and succinctly. To wit, Ordering forms a monoid under the following usage:

LT `mappend` _ = LT
GT `mappend` _ = GT
EQ `mappend` x = x

mempty = EQ

Suppose then that we have a list containing integers, and we wish to sort it first by the sum of the list, then by list length, then by ordinary numerical sorting of the elements, one can do the following:

sortBy (comparing sum `mappend` comparing length `mappend` compare)
  [[1,2,3], [3,2,1], [5,1], [1,1,1,1,1,1], [4,2,1], [1,1,1,1]]

returning [[1,1,1,1],[5,1],[1,2,3],[3,2,1],[1,1,1,1,1,1],[4,2,1]]. As you can see, the list was sorted by sum, then length, then by comparison (hence [1,2,3] coming before [3,2,1]). Now consider how much code it would have taken to do this without using monoids.

You’d better be impressed

Although these examples barely skim the surface of all you can do with monoids, I hope demonstrated how much simpler your code could be by recognising and using monoids appropriately. Since first learning about them, it’s surprised me how this simple pattern appears in code I write every single day, and how often I could have written far simpler code if I had but recognised it for what it was – a simple, lowly monoid.

Haskell Again

2011-04-21T00:00:00-07:00

Haskell Again

21 April 2011 – Cape Town

It struck me, as I started typing this page, that I don’t move around nearly enough to warrant including a location in each blog post. Maybe once every few years when I move I can write “the next 5 years of blogging coming to you from city name” or something to that effect. Anyhow… As usual, I realised I haven’t blogged in ages. Like most blogs, mine seems to be a sort of metablog about blogging (or the absence thereof) rather than content. Perhaps this is the start of something more. Time will tell.

As usual, I’ve spent the last year suffering from technology-induced ADD. This includes starting 2 books on Scala, a book on Clojure, one on Common Lisp, another on JavaScript, etc. I’d say the JavaScript one was most successful in that I actually read enough of it for it to have affected my understanding (and writing) of JavaScript. I’ve since realised that, as much as there are 100 different subjects that fascinate me, I’m never going to master any of them unless I’m willing to accept that I need to focus on one or two at a time.

With that in mind, I’ve decided my primary focus – outside of whatever I’m doing at work, which will likely be a combination of Ruby and Objective-C – will be Haskell. I’m tired of having to resolve problems and rediscover things I’ve learnt before, so I’m going to try catalogue things as I learn them.

Starting today

I watched some presentations given by Nick Partridge on Haskell, and learnt about or was reminded of a few things. Briefly:

Use pointful to help you make sense of complex point-free expressions.
Use pointfree to turn pointful expressions into (complex, at times) pointfree expressions.
Use hlint on your source code for suggestions on how to improve it.
Hoogle can be installed locally.
First look in hackage for libraries that do what you are trying to accomplish before writing your own code.

Those were the salient points for me. Now I’m off to try my hand at getting Yesod up and running.

Some rambling thoughts on type inference

2010-12-02T00:00:00-08:00

Some rambling thoughts on type inference

02 Dec 2010 – Cape Town

O’Reilly were having one of their site-wide ebook discounts, and as usual I scoured the very comprehensive list of books to see what I should buy. It’s funny how something will suddenly become a necessity when you can get 60% off the purchase price. Needless to say I wound up buying Programming Scala, in spite of already owning a perfectly good – and unread – copy of Programming in Scala. Admittedly, I did find the latter somewhat slow going, which has not helped in my efforts to try and learn the language.

I’ve always (for the last 6 months at least!) considered my lack of knowledge of Scala to be an unfortunate shortcoming, and so I reasoned if I bought Just One More Book on it, I might read enough of it to learn a sufficent portion of the language to start enjoying it, allowing me to stick it out and learn further. It’s frustrating to me how many programming books start out by detailing minutiae of a language instead of getting on with teaching us about it’s style and strengths. I enjoy being given a complex, idiomatic piece of code in a language and having to figure out what it does, as well as identify the strange (or familiar) programming idioms. I find it fascinating to learn the different styles and patterns that become best practice in different languages.

Anyway, as I started reading, I was wondering how Scala performs it’s type inference. All the languages that perform type inference that I have a knowledge of use Hindley-Milner (or Damas-Milner to the pedantic), or some derivative of that. This is true of Haskell, ML, F#, etc.

While searching for an answer, I came across an article which suggests that H-M type inference is a bad thing. It contrasts two equivalent pieces of code – written in ML and Scala – and posits that the Scala version is somehow superior to the ML version, precisely because it is more verbose. Okay, it’s on the verbosity per se, but the type annotations necessitated by Scala performing only local type inference. Reading on, the author reasons that, due to the extensive use of type annotations in the Scala version, it is safer and more useful than the ML version. I must say, I find this argument to be rather absurd.

In Haskell, I’ve found type inference to be hugely useful. It gives the code you write a feel more akin to dynamically typed languages than the verbose, boilerplate filled code one normally associates with statically typed languages. Letting the compiler figure out the types lets you focus on solving the problem, not babysitting the compiler.

However, I have found it very useful when writing a function to start by thinking about its type signature. It accomplishes a number of things:

It forces you to formalise the problem in your head, and helps ensure your solution is actually solving the problem.
It gives you and others reading your code a succint explanation of what the code is doing.
It prevents errors of the sort the author complains about, where your function behaves differently to your expectations.

I’m not sure if this just reflects a difference in culture between Haskell and ML, but I’ve found (from my admittedly limited experience with Haskell) that there is an emphasis on manually writing the type signature for all but the most basic functions, to ensure that your function isn’t just internally consistent, but also consistent with your expectations of it. It provides numerous benefits, adds a single line of code above the function, and obviates the need for scattering ugly type annotations throughout your code.

If, as the author says, there is a tendency in ML to only include the type signature when necessary, I can see why this might cause frustration. But, it seems to be a case of throwing out the baby with the bathwater when the problem can be solved quite simply, and not by “protecting” ourselves by using a dumbed down type inference algorithm.

Could it be

2010-11-28T00:00:00-08:00

Could it be

28 Nov 2010 – Cape Town

Lately I’ve been trying to learn a lot of new (at least for me) technologies and languages, and I’ve wanted a place to keep track of my thoughts and progress. So I’ve decided it makes sense for my to dust off the cobwebs and see if I can try make blogging stick. Time will tell.

What’s new?

I’ve changed things up a bit. Mostly by swapping out my dull sans serif font stack for Skolar. TypeKit is great, and I’m glad to finally have a site where I can use it.

I’ve swapped out the most of the blue in the old style for red. It’s a work in progress, but I think it’s an improvement.

What I’ll be writing about

Lately I’ve finally taken it upon myself to improve my JavaScript. I’ll be doing some pretty interesting things in the coming months.

I’m also taking the time to learn more about functional programming, and in particular Haskell, so I’ll probably have some very rudimentary posts about Haskell from time to time.

Time travelling with Jekyll

2009-02-11T00:00:00-08:00

Time travelling with Jekyll

11 Feb 2009 – Johannesburg

So I went ahead and changed the front page so that it showed my last couple of posts. I didn’t like it though, so I changed it back. At the end of the day the whole thing is something of a hack since I just truncate the content of the post, which means that the HTML has a 99% chance of missing a closing p tag or something. Anyway, it works for now…

One thing that I haven’t figured out with Jekyll is how to have multiple entries from the same day appear in the correct order. I suppose I haven’t really tried to figure it out. I suppose the obvious thing to do would be to add in a timestamp. I dunno if Jekyll supports anything but the date. So in the meantime I’ve just resorted to back dating and post dating entries if the order is important. Hence the title of this post…

I was looking back at my old, abandoned blog (with all of two entries) and it struck me how quickly things move. I was busy blogging about Git and how I planned to look into GitHub. That was back in the days when you needed an invite to get onto GitHub. And that was less than a year ago. In less than a year GitHub has completely revolutionised open source, and more specifically Ruby, development.

Anyway, I hadn’t intended for this to be long. I’m hoping for once to get a decent night’s rest.

A few new additions

2009-02-10T00:00:00-08:00

A few new additions

10 Feb 2009 – Johannesburg

Well, more like one new addition. Since I don’t blog all that often, and I don’t have anything else I’m linking to, I disliked the fact that my latest blog entry wasn’t displayed on the home page. So, searching the net for a liquid cheat sheet (since I’ve never used it before), I hacked away at my index page for a few minutes and now have a truncated version of my newest post displayed on the home page. I’m thinking I’ll probably do that for the last 3 – 5 posts, and then display links to the older ones, but I’ll get to that soon enough.

Someone reminded me to update my blog

2009-02-09T00:00:00-08:00

Someone reminded me to update my blog

09 Feb 2009 – Johannesburg

Today, someone tweeted me and reminded me that my blog is one of the most shamefully neglected corners of cyberspace. Since I’ve never had anyone express interest in my blog before, I’ve never really felt too bad. But the fact that someone actually took notice means that I need to repent and become a more devout blogger.

I’ve been using Rails 2.3 for the past week or two. Well, 2.3 RC1 to be precise. It seems more than stable – certainly I’ve yet to run into any issues with it. And truly, the output of rake routes is a joy to behold now that all the formatted routes crap is gone. I don’t know that we use enough routes in any of our projects for it to make a huge difference memory-wise, but I’ll test that when I upgrade one of our older projects from Rails 2.1 to 2.3. Mostly I haven’t because I’ve just been a bit lazy. Considering it’s about 10 minutes worth of work (plus a few more to test), I really just need to buckle down and do it.

In other news, since I’ve been working more closely with other developers, I’ve actually started remembering to switch out to branches before I add features. When you’re pretty much the only person working on a particular code base, working on the master branch causes problems rarely enough that you tend to just do it. However, it’s one of those things that I’ve known I shouldn’t be doing for a while, so I’m glad I’ve finally had something to push me to remember. Now finally I can stop abusing git stash.

Anyway, I’m really going to try and make time for a few blog posts a week, since I often have things I think I should blog about but neglect to. Let’s see how that goes.

Things I think I'll like about Jekyll

2008-12-22T00:00:00-08:00

Things I think I’ll like about Jekyll

22 Dec 2008 – Johannesburg

Well, it’s been all of ten minutes. No wait, maybe fifteen. Anyway, with that much exposure to it, this is a real first impressions type post. But here’s what seems cool thus far.

Uses Git (and integrates with GitHub)

I like the fact that I can edit blog posts from TextMate. I think a big reason for me never blogging is the fact that I have to think of going to my Wordpress site, logging into the admin section, and then composing a new entry. Now, this doesn’t sound like much work (it really isn’t), but I suppose I’m lazy, and so being able to do things from TextMate (which – on my machine – is open 95% of the time) makes the workflow just that little bit cleaner. Plus, I can push the changes out to GitHub with just a couple of keystrokes.

Admittedly, this is not solely a Jekyll feature, since much of it’s utility depends on GitHub… Still, I’m viewing Jekyll from the angle of GitHub pages, so I think it’s a fair point.

You can hack on it. Easily

The code for this blog is pretty much straight HTML or Textile, with maybe 2 loops (using Liquid) to display the list of blog posts. You can’t get simpler than that.

And…?

Okay, so that’s only two points. But what more could you ask for in a blogging engine? Basically, the features TPW wanted it to have are really useful, and seem to be exactly what I need to start blogging more often. Time will tell I suppose.

My newest blog

2008-12-22T00:00:00-08:00

My newest blog

22 Dec 2008 – Johannesburg

Well, I’m at it again – creating a new blog. I think my blog:posts ratio is close enough to 1:1 that the actual variance is negligible. It’s shocking really. My last blog contained exactly 1 post, as did the one before it, etc. Plus to offset the few blogs that have contained multiple posts, I’ve created a few blogs that never even got their first post. For shame!

Anyway, this is a shameless rip-off of Mojombo’s blog, which he has happily invited us all to rip-off. I’m initially just interested in seeing my own name in Shiny letters on my GitHub page. I have high hopes of – in time – making this my own little creation. We’ll see I suppose.