Code Review Swap?

#1

I have a request that may seem novel. I would like someone to do code review for a side project that I’m working on, and I would be willing to do the same in exchange. The code I review doesn’t even have to be Haskell.

I’ll give a brief description of what I’m working on. It’s a bridge website built on top of wai-routes with hsx templates and storage in Cassandra. I built a static file server to go with it that aggressively caches and pre-compresses the static files, and then serves the smallest one that a browser will expect. There’s a CMS-lite component to the site for the content.

I also have a card shuffling algorithm that shuffles and deals together, exploiting the fact that a hand of cards is the same no matter the order in which the cards were dealt. Right now it’s just a command line tool that feels prototypy, but I’d eventually like to make it scriptable with lua to allow for running card dealing simulations with various constraints.

There are parts of the code I would be willing to open source if there were interest:

  • I have a reference counting framework for ResourceT to allow for shared resources to be releaseed early, but not too early.
  • I ported the fstatat and mkdirat low level functions to have higher-level wrappers.
  • I have a low level recursive directory walking helper that returns directory walk events. This one probably needs a fair amount of work to clean up into something more generic, but it’s 80% there.
  • A module of glue code for digestive-functors and lucid-html.

I’d also be happy to share the code with anyone that is just curious.

Kyle

4 Likes
#2

Sounds like a cool idea! I’d be happy to review some of your code (whichever parts I can understand!) in exchange for a review of servant-routes, a package I’ve been working on that’s currently a candidate package on Hackage.

From a quick glance at your description, I’d definitely be interested in the shuffling algorithm stuff (I have a mathematics background), and the directory walker. Open to others too!

On a more general note, I think this is a great concept with a lot of potential. I’m imagining a mailing list, or even a website, that pairs people up based on their skillsets and areas of interests. The Tinder of code review…

3 Likes
#3

I’m pretty busy until Monday, but I’ll give a brief overview of the shuffling. It’s straightforward.

One way to uniformly shuffle a deck of cards is to assign uniform binary fraction in the range [0, 1) one bit a time to each card, and then sort by that binary fraction. This is an infinite amount of bits for each card, but in order to compare them, we only need to look at a finite number of bits to compare them. In fact, you could start by assigning a single bit to each card, putting the 0’s in front and the 1’s in back. You can keep doing this to the sub-piles until they are of size 1.

There’s a slight optimization for a sub-pile of size 2. There are only 2 outcomes, so we can take a single bit and if it’s 0, then leave it alone, and if it’s 1, then swap.

My insight was to combine this with the hands that are being dealt. In the final shuffled deck, the first 13 cards go to the same player, and then the next 13 cards, etc.

When you have a sub-pile of cards that all belong to the same player, you don’t need to shuffle them any more.

The code I have works from both ends of the deck. It flips bits at the front, just incrementing the front index whenever there’s a 0. When there’s a 1, it goes to the back. At the back, it flips bits until there is a 0, and then it swaps the front card that got a 1 with the back card that got a 0. Then it goes back to the front. At the end of the sub-pile, it records the 2 sub piles. There’s a bit of logic that compares the piles with the hand boundaries to decide when it can skip shuffling.

It’s fast enough that printing out the hands was a measurable bottleneck, and I made an ascii-output version that pre-allocates memory for each hand fills up a buffer of bytes to write oute.

I have it set up getting bits from ChaCha/8. The idea was that a tournament organizer could generate a week’s worth of deals (or more) from a key / nonce pair and then publish the key / nonce at the end as a way of demonstrating fairness.

Potential improvements

There are a bunch of improvements that I have in mind, like dealing some subset of the cards together with placeholders, and then checking some condition. If the condition holds, you can shuffle a smaller deck into the placeholders. You might do this for simulation reasons, if you wanted to do as little work as possible before throwing away a deal that didn’t meet your criteria. As an example, you can construct a deck with 13 black cards, all the same, and 39 white cards. The black cards are stand ins for spades. We can shuffle the cards like before, with 2 speedups. We can skip any sub pile that is all the same. We can stop when the first hand is dealt and check if it has 5 or more spades. Or we can stop when 2 hands are dealt and then check if the first 2 hands have 8 or more spades.

It is just as fairly random to deal a deck with placeholders to each player, and then trade the placeholders for spades as it is to just deal the spades directly.

1 Like
#4

Interesting. Is there a name for this sort of binary shuffling algorithm? And are you sure limiting the shuffle after you’ve dealt one player’s cards doesn’t introduce any sampling bias? I imagine you’d need an extensive test suites to show otherwise.

#5

In the literature, it’s called an inverse GSR (Gilbert-Shannon-Reeds) shuffle. Doing it backwards is easier with a computer because it just requires uniform bits.

There’s 2 things you could mean by “limiting the shuffle after you’ve dealt one player’s cards”. If you just mean the standard algorithm where we avoid shuffling cards that belong to one player, then no, we don’t need extensive testing. As long as the complete deck shuffling algorithm is fair, then it’s straightforward to prove that we can skip steps that don’t change which cards go to which player.

If you mean that when you’re trying to do guided dealing, there could be a bias problem, then yes there’s a trap that you could fall into.

If you want the first hand to have two properties A and B, suppose you deal a deck with placeholders and then check for property A, and then deal the placeholders and check for property B.
If you fail property B you have to go back to the beginning. You can’t re-use the partially dealt hand that passed property A. Otherwise you introduce a sampling bias.

As long as you’re just doing early rejection, you shouldn’t introduce any sampling bias. You’re effectively doing a lazy shuffle of the deck, looking at the first 13 cards, and then possibly rejecting.

If your bit source is independent, then it shouldn’t matter that you didn’t consume the shuffle bits that would have been used to further shuffle the rest of the deck.

If you mean that there’s a bias introduced if you throw away hands where north doesn’t have 4 Aces, then yes, but that’s exactly what you’re trying to do. As long as you don’t introduce any other bias, then it’s fine.

#6

It came back to me over a couple of days. The shuffle is called the Rao-Sandelius (RS) shuffle. I haven’t done an extensive search, but I haven’t seen anything in the literature on using the intended deal to abbreviate the shuffle. I got that idea from this paper on physical riffle shuffles.

There wasn’t a Wikipedia article on the Rao-Sandelius shuffle, so I wrote one:

The Sandelius paper anticipates the optimization of not shuffling a players hand when discussing a random sample of 50 items from 150. A bridge hand is a random sample of 13 cards from 52. Followed by a sample of 13 from the remaining 39, etc. I haven’t seen anyone else that cites the paper use this detail.

#7

Thanks for the explanation. If one use case is professional cards tournaments, I imagine they’d require you to prove correctness/bias-less-ness anyway?

I’ll take a look at the paper you linked, as well as your article. Do you have a repo you could share so I can see your implementation so far?

#8

DM your email and I’ll add send you an invitation to the repo.

Feel free to point me at a section of servant-routes that you’d like me to look at.