## Sunday, November 3, 2013

### Quickselect FTW!

More than a year ago, I answered a question on Stack Overflow about the Quickselect algorithm, which takes some unsorted data and finds the k-th smallest value (that is, the value that would be in position k if you were to sort the data). The person asking the question had seen multiple technical descriptions of the algorithm, but was looking for a simplified explanation that was not expressed as computer code. I tried to illustrate the algorithm in story form, and others seemed to like my story. The surprising part to me has been that votes continue to trickle in even today, and that this deliberately silly story is now my most upvoted answer. I suppose there's a lesson in there somewhere...

You walk into a gymnasium containing 200 children. It is September 8th, so you have a burning desire to find the 98th shortest child. You know that you could line them all up from shortest to tallest, but that would take forever. “I know”, you think, “I could use QUICKSELECT!”

You walk out into the crowd, close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at one of the children, Peter Pivot. You say, “Quickly! Everybody shorter than Peter, come stand over here. And everybody taller than Peter, go stand over there. If you're the same height as Peter, you can go into either group.”

The children shuffle around, and soon they are standing in the two groups. You count and find 120 children in the shorter group, and 79 children in the taller group. You know the 98th shortest child must be in the shorter group, so you tell Peter and the 79 taller children to sit in the bleachers.

You again close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at Peter's sister, Paula Pivot. You say, “Quickly! Those of you who are still standing. If you're shorter than Paula, come stand over here. If you're taller than Paula, go stand over there. If you're the same height, you can go into either group.”

The children shuffle around, and soon they are standing in the two groups. You count and find 59 children in the shorter group, and 60 children in the taller group. You know the 98th shortest child must be in the taller group, so you tell Paula and the 59 shorter children to sit in the bleachers.

You again close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at Paula's cousin, Prudence Pivot. You say, “Quickly! Those of you who are still standing. If you're shorter than Prudence, come stand over here. If you're taller than Prudence, go stand over there. If you're the same height, you can go into either group.”

The children shuffle around, and soon they are standing in the two groups. You count and find 37 children in the shorter group, and 22 children in the taller group. You know that Paula and 59 other shorter children are sitting on the bleachers. Along with the 37 shorter children still standing, you know that a total of 97 children are shorter than Prudence. Therefore, Prudence is the 98th shortest child!

Quickselect FTW!

## Sunday, November 6, 2011

### On the Dangers of Giving Games as Wedding PresentsorWell, it seemed like a good idea at the time...

[This is a letter I included with a recent wedding present.]

Dear Ben and Sarah,

Well, it seemed like a good idea at the time…

I think you’ll enjoy this game, Thunderstone. I’ve been playing it a lot with my son. Like Race for the Galaxy, this one works very well with two players, but can also handle more players. (Predictably, with more players, it becomes very chaotic, especially when thieves are in play…) I’m so certain you’ll enjoy it that I also got you the first expansion, Wrath of the Elements.

You might notice that this box is the Wrath of the Elements box. See, the first Thunderstone comes with a huge box, with lots of wasted space. That box is twice as big as this one, and only comes with about half the cards you see before you. Knowing that dealing with the larger box would be difficult for you, I’ve combined all the cards for both the main game and the expansion into this one box. (By the way, if you end up liking the game, this box will also easily hold the cards for the second expansion, Doomgate Legion.)

There was just one eensy teensy flaw with my plan. A minor thing really, hardly worth mentioning.

The original rulebook was too big for this box.

I considered several options: Just leave out the rulebook and point you to the online rules. Stick the rulebook in a separate, sturdy envelope, which is guaranteed to get lost in about 13.8 nanoseconds. Fold the rulebook in half and jam it in the box. Then I found the perfect solution. A post on BoardGameGeek described trimming the top and bottom off the rulebook—which is all wasted space anyway—with a paper cutter.

Fun With Words Did you know that a mangle was a British machine used in the 1800’s to press water out of clothes? It’s called a wringer in the US. A probably apocryphal story asserts that the word mangle came into the English language to describe the damage done to clothes by this machine, but I think the causal chain is more likely to run in the other direction, with the machine being named after the word.

Umm, where was I? Oh yes, paper cutter.

Anyway, so I bring the rulebook into school and take it over to the room with the paper cutter. I line it up carefully, and pull down the chopper…which cuts about an inch into the rulebook and sticks. I push down a little harder…and the entire back of the paper cutter lifts off the table, the chopper twists the rulebook and pulls it partway off the bed and…

Hey, have you ever had a jam in a paper shredder? And cleared it by pulling half shredded paper back out the top of the machine. The papers come out looking pristine partway down the page, and then at a certain line of demarcation (you know, that line really ought to have a cool name, like the Maginot Line or the Mendoza Line), the rest comes out drooping in sad, wrinkled tatters. What’s the word? Oh yeah, mangled. Why do I bring that up? No reason, really.

Hmm, where was I? Right, paper cutter!

So I lift up the chopper and pull the rulebook out and…let’s just say it’s not looking too good. I flip it over—the rulebook, not the paper cutter, although that might have worked better—and try again on the other side. Let’s just say that that side left me longing for the Golden Age epitomized by the results of the first side. A few more minutes, and a few muttered imprecations later, and…

You know, my wife use to do scrapbooking, and they sell these funny little scissors that are designed to make an artistic ragged edge. Expensive little buggers. If only I had known, I could have saved her a lot of money.

So…Thunderstone! Great game! I think you’re going to like it. [a few personal comments deleted]

Congratulations!

Chris

## Sunday, July 18, 2010

### Eating My Way Across Oahu

See also Eating My Way Across Kauai

New for Lost fans: see extra links at the end of the post

We had fewer days on Oahu than Kauai, and part of that time was spent visiting family, so we had a lot fewer meals out on Oahu. But, on our last full day, we went on the Hole-In-The-Wall food tour of Honolulu with Hawaii Food Tours. I've been on several really good food tours around New York, but this blew them all away. I highly recommend taking the tour if you ever get the chance.

Also, the title above is misleading, because all but one of the places reviewed below were in Honolulu.

### Mochi

As a kid, one of my favorite treats was when my father picked up mochi from Fugetsu-Do in the Little Tokyo area of Los Angeles. Unfortunately, New York offers nothing comparable. (I've found several places that offer various kinds of manju, but not the kind I grew up with.)

What is mochi? The kind I'm talking about is a sweet, sticky, soft, smooth rice dough, usually wrapped around a sweet red or white bean filling.

In planning our trip, I found several mochi stores in Honolulu that I knew we had to try.

Mikawaya Confectionary (inside the Shirokaya department store in Ala Moana Center): We bought four pieces and split them. The hits were orange gyohi (an unfilled orange-flavored piece that tasted a bit like a creamsicle), and taro gyohi (a purple piece with taro-flavoring in the outer dough).

Fujiya Limited (hard to spot store on Waikamilo Road): The specialty here is fruit mochi. I was expecting some kind of fruit paste, but no, it's whole pieces of fruit wrapped inside the dough along with a little bit of bean paste. We had strawberry, blueberry, and raspberry. (I also snuck in a tsumami, which was the closest I've had to the ones I grew up with, but softer.)

Nisshodo Candy Store: The hardest of the three to find, it's literally in a warehouse behind a strip mall. Unfortunately, it was by far the worst of the three, so don't bother. My beloved white bean filling was particularly bad.

### Other Sweets

I usually tend more to the savory side, but the rest of my family shares a profound sweet tooth. Hence, many of our stops involved sweets, even beyond the mochi above.

Liliha Bakery (N Kuakini St, just a little off Liliha St): Two words‒coco puffs. They sell over 5000 of these puppies a day. Basically an oversize cream puff with a creamy chocolate filling and a cap of chantilly frosting. How good are they? We went to the bakery four times, including three times in less than 24 hours! Interesting tidbit: The tiny little diner attached to this bakery is where they shot the scene in Lost where Kate visited her mother.

Leonard's Bakery (Kapahalu and Charles): It's all about the malasadas (Portuguese doughnuts). Fried dough, more bread-like than ordinary doughnuts, with hints of Portuguese sweet bread. Always served warm. Covered in your choice of several different powders (I took the classic sugar, but wish I had tried the li hing). Available with several different fillings (I chose haupia), or without. If you're into sweet fried dough‒you know who you are!‒this is probably a must try. I'm not, so I thought it was merely good. However, more people on our food tour picked this as their favorite stop than any other single place. Given the quality of the other places we stopped, Leonard's must be doing something right.

Rainbow Tea Stop (Maunakea Marketplace): Very good coconut tarts, but then we tried their banana lumpia. Bananas fried in lumpia wrappers, with a carmelized coating. Out of this world. And I don't even like bananas!

While I'm talking about sweets, I should say a few words about haupia, a kind of coconut pudding. Imagine coconut-milk jello not quite as firm as finger jello and you'll be on the right track. Haupia is everywhere in Hawaii, either by itself or as a filling for other desserts, such as malasadas from Leonards or the amazing vanilla haupia pie at the Snack Shack on Kauai. If you're willing to use canned coconut milk, it's very easy to make at home. Whisk 3 cups canned coconut milk with 5 tablespoons sugar and 5 tablespoons cornstarch. Keep whisking over heat until bubbly. Spread into a pan, and refrigerate until firm. Cut into squares to serve. (Some people substitute water or milk for up to half of the coconut milk.)

### Manapua

The name “manapua” literally translates to “flower power”, which makes no sense because it was a corruption of the longer phrase “mea ono pua'a” (roughly, pork pastry).

Manapua is the Hawaiian version of a Chinese bao, with the bun made out of a dough similar to Portuguese sweet bread. The buns can be baked or steamed, and the fillings can be savory or sweet, with char siu (Chinese roast pork) being the most popular. Manapua are so popular on Hawaii that they used to be sold door-to-door by the “manapua man” (Hawaii's version of the Good Humor Man). These days the manapua man sells out of a truck.

Royal Kitchen (on the pedestrian part of River Street just off N Kukui Street): If I could transport one shop from Hawaii to my neighborhood, this would be it. I could eat a couple of these EVERY SINGLE DAY for breakfast. I loved the cha siu manapua, and the lup chong manapua was almost as good. I probably wouldn't bother with the curry chicken manapua again, but I'd still like to try the kalua pork and the Portuguese sausage. The sweet lovers in my family also enjoyed the coconut manapua and the black sugar manapua. (Another Lost sighting: the pedestrian bridge by Royal Kitchen is where they filmed Sun paying off Jin's mother.)

Libby Manapua (corner of Kalihi and Kalani): After enjoying Royal Kitchen so much, we stopped here on our way to the airport to pick up lunch. My internet research had turned up Libby Manapua as a strong contender for best manapua on the island. My verdict was that Royal Kitchen is better. The buns at Libby were bigger than Royal Kitchen's, but with too little filling for all that bread. Also, Libby offered a much smaller selection of fillings. On the other hand, the pork hash at Libby was fantastic. You can see these little pork-filled dumplings in the upper right corner of the box.

Sing Cheong Yuan Bakery (Maunakea Street): Not really manapua, but close enough that I'll mention it here. We never went into the store, but we were able to sample their ma tai su, a flaky bun filled with an intensely flavorful pork/shrimp mixture. Heavenly!

### Noodles

Ramen Nakamura (on Kalakaua Avenue in Waikiki): After binging on Hamura Saimin on Kauai, I wanted to compare it to the “real thing”. Ramen Nakamura was very, very good‒I'd happily eat there again anytime‒but a notch below Hamura. To me, the biggest difference was in the noodles themselves, but I also had a slight preference for Hamura's broth. To be fair, Ramen Nakamura offers several different broths; I had the miso, but maybe the shio or shoyu broth would have fared better. Someone whose opinion I trust later told me that Ramen Nakamura has the best ramen in the city, and I believe it. Any negativity here should be read as praise for Hamura rather than a knock against Ramen Nakamura.

Ying Leong Look Funn Factory (Keekaulike Street): We were lucky enough to tour this tiny factory, where they still make look funn rice noodles by hand. First, they ladle the soupy noodle batter onto aluminum sheet pans, then steam them in the silver steamers shown in back. When the pans come out of the steamer, they are stacked in front of fans to cool. The noodles are carefully peeled out of the pan... ...and folded into stacks that look like giant calamari. Most of the noodles shown in these pictures are plain, but you can see small chunks in the batter in the first picture. These chunks are green onion and either char siu or shrimp. Below, you can see the finished product, sliced and drizzled with a little bit of soy sauce. Delicious!

### Polynesian Cultural Center Luau

We spent a full day at the Polynesian Cultural Center. It's fun and worth the trip, although if we do it again we would skip the tour guide. But forget all the cultural stuff‒I'm here to talk about the food!

First, I have to get something off my chest: Dear PCC, The shave ice you sell in the park really should be shaved, not crushed!

Ok, I feel much better now.

The shave ice may have been disappointing, but their luau more than made up for it. Everything I tried was at least good, with many dishes reaching into outstanding territory, including

• fabulous kalua pig, probably the second best I had on the trip
• outstanding taro rolls (purple dinner rolls made with taro flour)
• the best poke I had on the trip (poke is marinated chunks of raw ahi, although I found out later that PCC uses a Tahitian recipe rather than Hawaiian)
• a wonderful sweet potato salad made from purple Okinawan sweet potatoes
• fabulous pipikaula (similar to beef jerky, but softer)
• the best haupia I had on the trip

Of course, they also had luau staples such as poi, lomilomi salmon, chicken long rice, chicken teriyaki, and fresh pineapple. All these were good, but not as memorable as the above dishes.

Speaking of fresh pineapple... At the family luau we went to for my cousin's first birthday, I gorged myself on fresh pineapple sprinkled with li hing powder.

A few years ago, I tried li hing mui, the king of the Hawaiian snack genre known as “crack seed”. Li hing mui is a salty dried plum covered with a bright red powder. The combination is salty, sweet, sour, stains your fingers red, and does funny things to your mouth. I have to admit I didn't like it. I think I even used the word “disgusting”.

But what I've now learned is that you can get the powder without the plum. I had it several times this trip sprinkled on fresh pineapple, which takes an already excellent treat up to the next level. I've heard that the powder is also good sprinkled on other kinds of fruit, on popcorn, even on ice cream. We brought a bag home that I look forward to experimenting with.

### New for Lost Fans

I found a website (Lost Virtual Tour) that includes some great pictures of the places I mentioned, showing what they look like in the show and in real life.

To my surprise, this site also shows the pub where we went to our family luau.

## Friday, July 16, 2010

### Eating My Way Across Kauai

See also Eating My Way Across Oahu

I love to eat, so I'm going to temporarily hijack this blog with some dining recommendations from our recent vacation in Hawaii.

We just got back from almost two weeks in Hawaii. My favorite part of the trip was eating my way across Kauai and Oahu. In planning for the trip, I got a lot of good tips from food blogs and other internet reviews, so I'm going to pay it forward by reporting on our dining hits and misses. This post will cover Kauai, and the next post will cover Oahu.

Be aware that many of these places take cash only.

### Must Try

Hamura Saimin Stand (Lihue, close to the airport): This place is a dive...and I mean that in the best possible way. It's old, run-down, hard-to-find, and tiny, so you'll probably have to wait for a few minutes. But the food is amazing, not to mention cheap and plentiful! I'm a huge fan of ramen (the real stuff, not the dried packages you find in the grocery store) and Hamura serves some of the best you'll find this side of Japan. The “special” (shown to the right) is a huge bowl filled with wonderful noodles and broth, and then topped with char siu (roast pork), won tons, fish cake, ham, green onions, cabbage, and a hard-boiled egg. The bbq sticks (beef or chicken), crispy wontons, and lilikoi (passion fruit) chiffon pie are also excellent, but be aware that they run out of the pie. Seating is at a single zig-zag counter, so be prepared to chat with your neightbors.

### Highly Recommended

Hanalei Dolphin Restaurant (Hanalei, on the right as you first drive into town): The best “fancy” meal we had on the trip. I had the shutome (broadbill swordfish) and my wife had the walu (Hawaiian butter fish). The shutome was among the best fish I've had in my life, and the walu was almost as good. Both were simply grilled, and then served with a slice of lemon and some drawn butter. The butter, in particular, was a revelation for me. Sure, you often see it with lobster and the like, but usually not with fish. After experiencing how much it enhanced the fish here, I'll have to ask for it at other places.

Puka Dog (Poipu, inside the Poipu Shopping Village): My son LOVED these, declaring them almost as good as my father's sweet-and-sour chicken wings, which is his high-water mark for non-dessert foods. They take a huge unsliced bun, and stick it onto a big spike, which both makes a hole for the dog and toasts the inside of the bun. They then put some toppings in the hole, fill the bun with a polish sausage, and add some more toppings to the tip of the sausage sticking out of the hole. Okay, the hole thing is a gimmick, but where they really shine is the toppings‒six different fruit relishes including mango, pineapple, papaya, banana, star fruit, and coconut (mango and pineapple are probably the best). They also include a mayonnaise-like “garlic lemon secret sauce”.

Pat's Taqueria (aka Pat's Taco Wagon) (Hanalei, by the base of the pier): On the mainland, lunch wagons are usually nothing special, but Hawaii has a tradition of great food served out of trucks. Pat's Taco Wagon is an excellent example. My first visit, I had the kalua pork burrito, which was very good. My second visit, I had the carne asada taco, which was mind-blowing. Both were kind of drippy, so be sure to lean over when you eat them.

Village Snack & Bakery (aka The Snack Shack) (Hanalei, in the back of the Ching Young Village Shopping Center): My favorite dessert on the island, vanilla haupia pie. Mmmm! If you get there early in the morning, you may also be lucky enough to get their fried mochi (three balls of mochi with a sugary coating on a stick). Their loco moco (a Hawaiian tradition with two scoops of rice, a hamburger steak, and two fried eggs, covered with brown gravy) and teriyaki beef sandwich were also outstanding, but the pancakes and apple cobbler were only so-so.

Shave Ice Paradise (Hanalei, across the street from the Ching Young Village Shopping Center): Shave ice is everywhere in Hawaii. Think giant snow cone, but made with shaved ice instead of crushed ice. The difference in texture is substantial, smooth instead of pebbly. You have a choice of many different syrups, and can add on ice cream underneath or sweetened condensed milk on top. The ice cream at the bottom didn't do much for me because you end up eating the top half of the ice without it, but the sweetened condensed milk on top (sometimes called a sno cap) is fantastic, changing what can sometimes be sickly sweet to sweet and creamy. Shave ice stands are very common, and there's not necessarily a lot of difference between them, but this one was the best we tried.

Hanalei Taro & Juice Company (Hanalei, in front of Kayak Kauai): Another lunch wagon. Plate lunches are a Hawaiian tradition with two scoops of rice, macaroni salad, and some kind of meat. I had the kalua pork plate lunch, which turned out to be the best kalua pork I tried on the island. The plate lunch also came with a little slice of their mochi cake, which is very good. They are famous for their smoothies, with use a taro base in addition to various combinations of fruit. My smoothie was good, but nothing special. The downside is that it's hard to find them open! I think they move around, but I didn't know where to look other than their main location.

### Recommended

Kountry Kitchen (Kapaa): Gigantic macadamia nut pancakes, which were fantastic with coconut syrup. I had the special loco moco, which had kalua pork instead of the usual hamburger steak, and it was very good also.

Bubba Burgers (Hanalei, across the street from the Ching Young Village Shopping Center): Try the teriyaki burger with pineapple. These are fast food burgers rather than restaurant burgers, but still good.

Lappert's Hawaii (Princeville, in the Princeville Center): Good ice cream with unusual flavors. I'd say good, but not great. Both Kilauea Video and Ice Cream (in Kilauea) and Pink's Creamery (in Hanalei) sounded better to me, but we didn't get to try those.

Banana Joe's (Kilauea, just off the highway): I didn't go, but my family loved their frostees. They also had some great fresh fruit, including lychees and “apple bananas”.

Tip Top Motel Cafe & Bakery (Lihue): Very busy, but incredibly fast service. The pancakes were good, but not as good as Kountry Kitchen's. I enjoyed the bento breakfast, which included teriyaki beef, chicken wings, Goteborg sausage, rice and macaroni salad.

Mediterranean Gourmet (Hanalei, way past the main drag, almost to Haena, at the Hanalei Colony Resort): We ate two lunches there, with good gyros, falafels, and chicken kebabs. We also went to their once-a-week luau since we were staying at the resort. The food at the luau was only so-so, but the entertainment was fun, if much lower key than many of the fancier tourist luaus.

### Not Recommended

Bar Acuda (Hanalei): We were disappointed in this highly recommended tapas bar. The food we had there was good, some of it excellent. The problem is that their menu is just too limited, with only about a dozen choices for tapas. After running through everything we wanted to try out of their tapas offerings, we proceeded down the street to Bubba Burgers because the kids were still hungry.

Hanalei Gourmet (Hanalei): Okay, but nothing special.

Bouchons Hanalei (Hanalei): Nice atmosphere, but mediocre food. I did not try their sushi, so maybe that's better.

## Monday, November 23, 2009

### Round-Robin Tournament Scheduling

For the last several years, I've held an in-class tournament on the last class day before Thanksgiving. Everybody's mind is elsewhere anyway, so the positive vibes generated by an hour spent hootin' and hollerin' are far more valuable than class content that would be forgotten long before the turkey made it into the oven.

Tomorrow's the big day, so I've spent part of today working out the tournament schedule. As usually seems to be the case, I have a different number of teams this year from past years, so I had to make a new schedule from scratch. I keep forgetting how I did it last time, but I always seem to converge back on the same technique. I finally decided to write down the technique so I can just look it up next year. Also, I'm hoping somebody can tell me what this technique is called, since it can't possibly be original.

Unless I have too many teams, I like to run a round-robin tournament, where everybody plays everybody else. There's a well-known algorithm for scheduling such a tournament by hand. I'll illustrate this algorithm with 6 teams, numbered 0–5. Start by writing the teams down in two rows, as follows:

```   0 1 2
5 4 3
```
The columns say which teams play each other. In this case, team 0 plays team 5, team 1 plays team 4, and team 2 plays team 3.

Now, leave team 0 in place, but rotate teams 1–5 one position clockwise.

```   0 5 1
4 3 2
```
In this round, team 0 plays team 4, team 5 plays team 3, and team 1 plays team 2. This process continues for three more rounds:
```   0 4 5
3 2 1

0 3 4
2 1 5

0 2 3
1 5 4
```
For an even number of teams, this technique generates a schedule with N−1 rounds, and N/2 games per round. For an odd number of teams, you add an extra dummy team, yielding a schedule with N rounds and (N−1)/2 games per round. In each round, the team scheduled against the dummy gets a bye.

Many games have a slight asymmetry, such as a homefield advantage or a first-move advantage. For my game, the “red” team has a very small advantage over the “blue” team. In tournaments for such games, it is important to balance the number of “home” games and “away” games played by each team. In the above algorithm, this is accomplished by making the top row the home team in odd-numbered rounds and the bottom row the home team in even-numbered rounds. (Note that, when N is even, half the teams will get one extra home game.)

Okay, so the above technique is easy, but it has a major drawback for my purposes, at least when N is odd. Because the tournament must be completed by the end of the class period, I need to be ready to drop games from the schedule if it looks like we're running long. The easiest way to accomplish this is to drop an entire round. But when N is odd, one team has a bye, which means that that team will end up playing a different number of games from everybody else, which in turn can make it difficult to determine the winner of the tournament.

To avoid this problem, I use the following technique. I organize the schedule in N/2 rounds, rounded down if N is odd. In each round (except possibly the last), every team plays twice: one home game and one away game. The rule is that, in round R, team X plays at home against team (X+R) mod N, and away against team (X−R) mod N. (If you don't remember how mod works, it simply means that the team numbers wrap around.) For example, here is a schedule for 7 teams, numbered 0–6.

```   Round 1: 0-1 1-2 2-3 3-4 4-5 5-6 6-0

Round 2: 0-2 1-3 2-4 3-5 4-6 5-0 6-1

Round 3: 0-3 1-4 2-5 3-6 4-0 5-1 6-2
```
Each game is listed as HOME TEAM–AWAY TEAM.

If N is even, then the last round is treated specially. As described so far, the last round in an 8-team tournament would look like

```   Round 4: 0-4 1-5 2-6 3-7 4-0 5-1 6-2 7-3
```
This involves repeat games, such as 0-4 and 4-0. To prevent such repeats, we chop off the second half of the last round when N is even.

Again, the advantage of this scheduling algorithm is that I can delete a round on the fly without causing an imbalance in the number of games that each team plays. Deleting a round also maintains the balance between home games and away games for each team, although that's a lesser concern.

## Thursday, October 22, 2009

### Binomial queues as a nested type

Warning: this is probably only of interest to functional programmers.

Maciej Kotowicz recently asked on the Haskell Cafe mailing list about implementing binomial queues (also known as binomial heaps) using fancy type machinery so that the type-checker can enforce the shape invariants of the data structure. This reminded me of a discussion I had with some colleagues in the summer of 1998 about using nested types to enforce these kinds of invariants. A little digging around in mail archives yielded this email, presented here with some light formatting and a few fixed typos.

I've been playing with binomial queues as a nested type, and I think you'll find the end result interesting.

### REVIEW

Let me first quickly review the usual implementation of binomial queues. Recall that a binomial tree has the shape

```data Tree a = Node a [Tree a]
```
A binomial tree of rank k has k children, of ranks k-1 .. 0 (stored in the list in decreasing order of rank). Note that we can combine two heap-ordered binomial trees of rank k to get a heap-ordered binomial tree of rank (k+1) as follows:
```combine a@(Node x xs) b@(Node y ys)
| x <= y    = Node x (b : xs)
| otherwise = Node y (a : ys)
```
Now a binomial queue is a list of heap-ordered binomial trees of increasing height (but not necessarily of consecutive ranks). We'll represent the ranks of those trees that are present by their position in the tree. Thus, some ranks will be empty. This could be implemented as
```type Binom a = [Maybe (Tree a)]
```
or somewhat more efficiently as
```data Binom a = Nil
| Zero (Binom a)
| One (Tree a) (Binom a)
```
or better still by unboxing the Tree in the One constructor
```data Binom a = Nil
| Zero (Binom a)
| One a [Tree a] (Binom a)
```
I won't go over all the operations -- they are amply covered elsewhere. I'll just describe two functions. The first, add, takes a tree and a list (where the tree has the same rank as the first position in the list), and returns a new list. It works basically like the increment function on binary numbers.
```add :: Ord a => a -> [Tree a] -> Binom a -> Binom a
add x xs Nil = One x xs Nil
add x xs (Zero h) = One x xs h
add x xs (One y ys h)
| x <= y    = Zero (add x (Node y ys : xs) h)
| otherwise = Zero (add y (Node x xs : ys) h)
```
The merge function is similar and works basically like the addition function on binary numbers.

Finally, the getMin function returns the minimum element of a queue paired with the queue without that element. The helper function getMin_ returns a triple of the minimum element in some suffix of the queue, the list of children associated with that minimum element, and the suffix without that element.

```getMin_ :: Ord a => Binom a -> (a, [Tree a], Binom a)
getMin_ (Zero h) = case getMin_ h of
(y,ys,h') -> (y,ys,Zero h')
getMin_ (One x xs Nil) = (x,xs,Nil)
getMin_ (One x xs h) = case getMin_ h of
(y,ys,h') | x <= y    -> (x,xs,Zero h)
| otherwise -> (y,ys,One x xs h')

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge (list2binom xs Nil) h')

list2binom [] h = h
list2binom (Node x xs : ys) h = list2binom ys (One x xs h)
```
Note that when getMin receives a list of children, it converts them to a valid binomial queue by reversing the list (and changing each pair of a Node constructor and a (:) constructor to a One constructor).

### NESTED REPRESENTATION -- FIRST ATTEMPT

By following the same approach we have been using to design nested datatypes, we get the following representation of binomial queues.

```data Binom_ a b = Nil
| Zero (Binom_ a (Trees a b))
| One a b (Binom_ a (Trees a b))

type Trees a b = (a, b, b)

type Binom a = Binom_ a ()
```
Here the list of children
```  (Node x3 xs3 : Node x2 xs2 : Node x1 xs1 : Node x0 xs0 : [])
```
is being represented by the nested triples
```  (xs3,xs3', (x2,xs2', (x1,xs1', (x0,xs0', ()))))
```
(where xsN' is the appropriate conversion of xsN).

All the functions are perfectly straightforward, except for getMin and getMin_ which must incrementally build up the reversing function to convert

```  (xs3,xs3', (x2,xs2', (x1,xs1', (x0,xs0', ()))))
```
to
```  One x0 xs0' (One x1 xs1' (One x2 xs2' (One x3 xs3' Nil)))
```
As a result of building up this reverse function incrementally, this implementation ends up being roughly 10% slower than the original.

### INTERLUDE ON REVERSING LISTS

Suppose we want to support the following ADT. We want sequences with three operations:
```empty :: ReversableSeq a
cons  :: a -> ReversableSeq a -> ReversableSeq a
rev   :: ReversableSeq a -> [a]
```
with the obvious semantics. cons must take O(1) time, but rev may take O(n) time. A list is a reasonable implementation with
```type ReversableSeq a = [a]
empty = []
cons = (:)
rev = reverse
```
but, if you think about it, there's a fair amount of interpretive overhead in the pattern matching that reverse performs at every step. Way back in 1985, John Hughes came up with a representation that avoids this overhead:
```type ReversableSeq a = [a] -> [a]
empty = id
cons x xs = xs . (x:)
rev xs = xs []
```
The result of cons 1 (cons 2 (cons 3 empty)) is
```id . (3:) . (2:) . (1:)
```
which, when applied to [] by the rev function, yields [3,2,1]. One way to think of this representation is as lists with "holes" at the ends. The cons operation fills in this hole with an element and another hole, and the rev operation fills in the hole with []. (This is quite similar to difference lists in logic programming...)

Applying this trick to the regular representation of binomial queues yields

```data Binom a = Nil
| Zero (Binom a)
| One a (Binom a -> Binom a) (Binom a)
```
which turns out to be about 10% faster than the original representation.

### NESTED REPRESENTATION -- SECOND ATTEMPT

Ok, let's try to make a nested datatype out of this. Conceptually, the nesting should keep track of our position in the queue so that we know what rank the current tree has and can't possibly mix up trees of different ranks. We hypothesize some Base type for the beginning of the list, and some type transformer Succ that modifies the type as we move down the queue.

```type Base = ???
type Succ b = ???  -- this might need to be Succ a b

type Binom a = Binom_ a Base

data Binom_ a b = Nil
| Zero (Binom_ a (Succ b))
| One a (Binom_ a ??? -> Binom_ a ???) (Binom_ a (Succ b))
```
Now, what should the missing types in the One constructor be? Well, the function (Binom_ a ??? -> Binom_ a ???) represents the children of the current node. If this node is of rank k, then these children are of ranks 0 .. k-1. The function (Binom_ a ??? -> Binom_ a ???) takes a queue starting at rank k and adds the children to the front of it, yielding a queue starting at rank 0. So the ???'s can be filled in as
```                | One a (Binom_ a b -> Binom_ a Base) (Binom_ a (Succ b))
```
or just
```                | One a (Binom_ a b -> Binom a) (Binom_ a (Succ b))
```
Now, what should the types Base and Succ be? It doesn't matter because we never construct data of those types, we simply use the types to discriminate between positions in the queue. So we can define Base and Succ as
```type Base = Void
newtype Succ b = S Void
```
I think this is a very interesting type for several reasons:
• It includes an arrow type, which we haven't seen much.
• The RHS of the datatype definition (in fact, just the One constructor) has occurrences of Binom_ at no fewer than three different types
```Binom_ a b
Binom_ a Base
Binom_ a (Succ b)
```
I've seen two before, but not three.
• It includes types which are never used, but are merely there to capture certain invariants (in this case, that trees of different ranks should never be confused). [2009 Comment: Today, these are called phantom types.] In some ways this might make this type less interesting, but an interesting consequence is that the code satisifes a certain "type erasure" property: if you erase the types from all the functions, you get code for the optimized regular representation.
Because of this "type erasure" property, you might expect it to be just as fast as the optimized regular representation, but in fact it is roughly 10% slower -- or roughly as fast as the original regular representation. This is because the extra types hinder a certain optimization that the programmer might make (and which I did make in the optimized regular representation).

Recall the type of the getMin_ function from the original regular representation, and the way it was used by getMin.

```getMin_ :: Ord a => Binom a -> (a, [Tree a], Binom a)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge (list2binom xs Nil) h')
```
For the optimized regular representation, this becomes
```getMin_ :: Ord a => Binom a -> (a, Binom a -> Binom a, Binom a)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge (xs Nil) h')
```
Now, consider the optimized nested representation. We can't just write
```getMin_ :: Ord a => Binom_ a b -> (a, Binom_ a b -> Binom a, Binom_ a b)
```
because we don't know the rank of the tree that the second component of the triple came from. (Note that if we had existential types, we could write
```getMin_ :: Ord a => Binom_ a b ->
(a, exists c. Binom_ a c -> Binom a, Binom_ a b)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge (xs Nil) h')
```
Some implementations do in fact support existential types, but in limited ways that would carry efficiency costs of their own...)

Instead of returning the children and then applying them to Nil at the end, we apply the children to Nil first, and then return the result, yielding the type

```
getMin_ :: Ord a => Binom_ a b -> (a, Binom a, Binom_ a b)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge xs h')
```
This depends on laziness to evaluate only the children of the final minimum, and not all the children of the temporary minimums along the way. However, this does mean that we build a lot more thunks of the form (xs Nil) along the way. And building these thunks is apparently quite expensive.

2009 Addendum Ralf Hinze considers a similar representation in Section 6 of Numerical Representations as Higher-Order Nested Datatypes. Today, you would probably use fancier type machinery like dependent types or maybe GADTs, but it's still amazing how far you can get with only nested types.

## Wednesday, October 1, 2008

### Score one for induction!

One of my favorite textbooks on algorithms—in spite of the fact that it's twenty years old—is Udi Manber's Introduction to Algorithms: A Creative Approach. However, I have never been tempted to actually use it in class. You see, the book's greatest strength is also its greatest weakness.

Most textbooks on algorithms show you a lot of polished algorithms, but provide little or no insight on how to go about designing such algorithms. Manber's book does a very good job providing such insight, by making an analogy with inductive proofs. If you have any skill with induction, then you can use Manber's approach to help you design algorithms. (Of course, this should come as no surprise since writing an inductive proof and writing a recursive function are essentially the same activity.)

I'm sure you see the flaw here—most students are even less comfortable with induction than they are with recursion. It's like trying to help somebody learn to drive a car by making an analogy with riding a unicycle. For a certain segment of the audience, that analogy might be just what they need, but for the most of the audience, the analogy will only produce puzzled looks.

I was recently helping a student who was struggling to get a handle on recursion. He was making the common beginner mistake of trying to think about what happens during the recursive call instead of trusting that the recursive call works (sometimes called the recursive leap of faith). By sheer coincidence, I had happened to notice the day before that this student had done very well in our discrete math course the previous year. Time to give it a try...

“You know when you're writing a proof by induction and at some point you use the inductive hypothesis? That's just like a recursive call. You don't worry about what happens inside the inductive hypothesis, you just say ‘Assume that it works for N-1...’ It's the same with recursion. You just assume that the recursive call works.”

That comparison actually seemed to help. Maybe Manber was onto something after all!