FOB

Ran across the homepage of Berkeley Logo a few days ago. One of the things on there is this demo code

to choices :menu [:sofar []]
  if emptyp :menu [print :sofar stop]
  foreach first :menu [(choices butfirst :menu sentence :sofar ?)]
end

When invoked as

choices [[small medium large]
         [vanilla [ultra chocolate] lychee [rum raisin] ginger]
         [cone cup]]

we get a list of choices starting with

small vanilla cone
small vanilla cup
small ultra chocolate cone
small ultra chocolate cup
…

I got curious about how Haskell stacks up against Logo here…

For reasons detailed in Debian Bug #559961 the cryptoloop module has been dropped from the Debian kernel as of the 2.6.32-trunk binary packages. I've filed a complaint at that bug. I know what I'm doing, and am unhappy that the Debian kernel maintainers have taken it upon themselves to gratuitously delete functionality from the Linux kernel image…

This is a rought-draft page that I'm making to take some notes on how I got the Debian Gnome Bluetooth support to work this time around. Bluez and its supporting utilities are an endless source of frustration and perhaps even of nightmare, so it's probably a good idea to have some notes…

While doing some research for an upcoming paper, I came upon a 2008 blog post describing a special case of the following interesting problem:

Given an alphabet of n symbols, construct a uniformly-selected sequence of m of these symbols, with the sequence containing no duplicate symbols.

[Updated 2009/12/14] The difficulty arises when both m and n are large. The obvious method is a rejection method: repeatedly pick a random symbol from the alphabet and check whether you've picked it already. If not, append it to your target number. The problem is that the duplicate check seems to require log m time even if you code it cleverly, giving an asymptotic performance of O(m log m). Hash tables can help some, but ultimately you're going to waste a lot of time checking for the unlikely case that you've generated a duplicate.

There were various solutions given in the comments, but none of them were optimal. A spoiler follows…

I woke up yesterday morning in Tuscon. A lovely day…