Low-Discrepency Sequences, Haskell, and T-Shirts!

Oct 19, 2017   •   Noon van der Silk





GitHub Repo


If you’ve ever glanced at a blog post here before, you’ll know that we love deep learning! But we also love functional programming, and in particular Haskell. Lyndon even runs the Melbourne Haskell Meetup!

The picture at the top of this blog post is the result of attempting to replicate this picture:


but in the theme of Haskell, and actually created with Haskell, instead of hand-drawn.

The amazing Haskell library called diagrams makes actually creating the triangles, circles, lines and lambdas actually very quick. For example, here is how you make a circle:

c :: Diagram B
c = circle 5

Amazing!

So infact, most of the trouble I had was figuring out how to lay things out nicely.

Given no better ideas, one might consider simply picking random points in the square, and then drawing objects there.

The most helpful function in Diagrams for this purpose is position, which is demonstrated in this example in the Diagrams manual.

In order to use this function, we’ll want something very similar to the mkPoint function that they have there; here is the one I used:

mkPoint :: P2 Double -> (P2 Double, Diagram B)
mkPoint p = (p, circle 0.1 # lw none # scale 0.2)

With this utility function in hand, we can define a function that that will plot a bunch of these circles at random points. The first function one might write, would simply place the points randomly just straight from the system random number generator.

This is the code for that:

stdRandomSample :: IO (Diagram B)
stdRandomSample = do
    let n = 100
    points <- replicateM n (mkP2 <$> rs <*> rs)
    return $ position (map mkPoint points)
                # fc magenta
                # centerXY
   where
    rs = randomRIO (0, 1)

and the resulting picture is this:


The main observation to make here is that points aren’t particularly “visually-pleasingly-distributed”. I.e. they kind of clump together in some places, and overlap more than I’d like.

I initially tried to address this via a reasonably crazy scheme. I decided that, instead of placing circles randomly, I would place them in a regular grid across the dimensions of the image, and then randomly jitter their positions. (The below two images are produced with gridPlacement1 and gridPlacement2 respectively, in the code accompanying this blog post.)


This caused significant issues. Notably:

  • There was now no overlapping,
  • If I generated many random points per grid cell, you could actually start to see the boundaries of the grid. This was very bad.
  • (Technical Detail): This approach wasn’t super diagrams-friendly, as I had to hard-code more size information that I would’ve liked.
  • (Technical Detail): There were some problems with transparency that, to this day, mildly mystify me.

So I started thinking of some solutions. I had a vague memory of a blog post that talked about this problem. I couldn’t find the post at the time, so I asked my friend Reuben if he could remember it, and he didn’t remember it either, but he did direct me to this Wikipedia page: Low-discrepency sequence. If you take a glance at that page, you’ll see that it’s a scheme for placing points in a space in a quasi-random quasi-regular fashion.

I got pretty excited because it seems like a nice way to avoid randomness, and place this in a nice-looking way. Also, incredibly happily, a few of these functions are already implemented in the “gsl-random” library! Even more happily, there were bindings in Haskell to it!

So I quickly implemented it like so:

samples :: QRNGType -> IO (Diagram B)
samples t = do
    let n = 100

    points <- getPoints t n
    let diag = position (map mkPoint points) # fc magenta
                                             # centerXY
    
    return $ diag # bg white


main = mainWith (samples halton)

and the result is this:


Compared to the original, this is what better!

Note in particular that there is less direct overlapping, and that there are less empty spaces! There are some other sequences in there that you can play with, and they have different properties. The sobol one, for example, is very regular:


Anyway, finally with this technique in hand I was able to revisit my earlier attempts and produce the design at the top of the page which then found it’s way on to the “RetroHaskell” T-Shirt:


which you can now buy on my PAOM shop! Open source clothing!

Level 2
382 Little Collins Street
Melbourne VIC, 3000

Enter from McKillop Street

Contact us

(03) 9008 5922

Get the latest on machine learning and data science in your inbox each month