mult.ifario.us

When negotiating with a potential customer, it's tempting to offer things that you think will make them take the deal. This is wrong for two reasons.

First, what you think will make them take the deal and what they actually want may be different, so you're making a concession that doesn't help your cause. Worse than that, you run the risk of confusing a less savvy customer who will then try to understand the enlarged deal terms or showing a more savvy customer that you're desperate.

Second, you always want the simplest, most uniform deals possible. Repeatability is scalability for the organization, and a one-off deal proves nothing about a product or business model. (Bending — but not breaking — the rules for a big deal is acceptable.) Moreover, having a limited number of form agreements greatly simplifies due diligence for financing or acquisition.

Via Bob's FoodJaunt social portal (at least that's what I'd call it) and younger sister to Greenthumbr, I found an NYT article (compare article at SFGate) about a gardener-for-hire who will plant and tend a garden in your yard, and the idea of a decentralized urban farm is compelling.

One paragraph in the NYT article misses the point:

Although a completely local diet is out of reach for even the most dedicated, the shift toward it is being driven by the increasingly popular view that fast food is the enemy and that local food tastes better. Depending on the season, local produce can cost an additional $1 a pound or more. But long-distance food, with its attendant petroleum consumption and cheap wages, is harming the planet and does nothing to help build communities, locavores believe.

Local isn't just better for the planet. Local is just better.

For example, one facet of better is fresher. The lettuce we buy at the local farmer's market (usually from "Let Us Farm") travels the 100-ish miles (Google Maps routing says 99.8 miles — "local" it is!) from the field to my fridge in under 24 hours if not under eight hours, and it stays edible for a week or more. For comparison, a smaller head of butter lettuce from Whole Foods, entombed in its keep sake plastic clamshell, keeps at most a few days once brought home from the store just because of the additional handling and time elapsed. Moreover, the local lettuce costs less. When presented with the apples-to-apples comparison, even the crassest consumer would choose the local option.

As energy costs increase, decentralized production and distribution should result in lower prices, higher quality, and more variety. The irresistible force of fundamental economic self-interest is going to drive change in our food supply chain, not something more noble or farsighted. That's a good thing, too, because relatively few people have a sense of duty to the collective good, but everyone has a wallet.

Cédric posted a nice puzzle on his blog:

[W]rite a counter function that counts from 1 to max but only returns numbers whose digits don't repeat.

Bob tweeted about a minimal solution in terms of execution time, although (like the guy in the cartoon) I still like my Haskell version of the sequence (up to some details with use of Data.Int.Int64 and typing the enumeration):

f k = [ n | n <- [1..k], (length . show $ n) == (length . nub . show $ n) ]

And the function to compute the maximum gap:

drop_tail k = reverse . (drop k) . reverse
by_pairs u = zip (drop 1 u) (drop_tail 1 u)
g k = maximum . map (uncurry (-)) . by_pairs . f $ k

This approach, while visually appealing, is unacceptably slow, even with some of the usual optimizations applied. The fact is that any solution that is implemented in terms of testing all of the numbers between 0 and k will perform orders of magnitude more poorly than the recursive style that Bob's using. But how would I know that...?

Subfactorials, Derangements, and Chooses

A derangement is a permutation with no fixed points, e.g., (123) is a derangement of the set {1,2,3}, but (12) is not because it maps 3 to 3. Like the number of permutations of an n-element set (n!), the number of derangements has its own function called the subfactorial and written !n. MathWorld has a decent write-up, with the major takeaway for present purposes being that !n ~ n!.

The number of elements in Cédric's set, for a fixed radix n is the sum from k=0 up to n of !k (n choose k), and that's much smaller than nn. (This reminds me of the whole "bad shuffle" meme from a long time ago.)

Just how much less work does the enumeration approach require than the iteration approach? Here's a quick snippet to compute the number of derangements and the corresponding Beust number for a given radix:

fac :: Integer -> Integer
fac 0 = 1
fac n = n * (fac (n-1))

choose :: Integer -> Integer -> Integer
choose n k = (fac n) `div` ((fac k) * (fac (n-k)))

d :: Integer -> Integer
d 1 = 0
d 2 = 1
d n = (n-1) * ( d (n-1) + d (n-2) )

b :: Integer -> Integer
b n = sum [ (d k) * (n `choose` k) | k <- [ 1..n ] ]

Then, b10 is 3628799, so a solution like Bob's should have around a 2500-fold advantage over a more brute force method. And that advantage gets huge in short order. As reminder of how much bigger nn is than n! and friends, 2626 is roughly 15,264,691,107 times larger than b26...

One of the many nifty features of bash is that it provides context-sensitive completion, but for some reason this capability isn't part of the bash that ships with Mac OS X, at least as of 10.5.3, which is what I'm presently using.

To rectify the oversight, first install the bash_completion port via MacPorts:

$ sudo port install bash-completion

And then modify your ~/.profile as directed, e.g., by adding:

if [ -f /opt/local/etc/bash_completion ]; then
    . /opt/local/etc/bash_completion
fi

To load your own local collection of completion hooks, create the directory ~/.bash_completion.d and then put the following in ~/.bash_completion (essentially cut/pasted out of /opt/local/etc/bash_completion):

if [ -d $USER_BASH_COMPLETION_DIR -a -r $USER_BASH_COMPLETION_DIR -a \
     -x $USER_BASH_COMPLETION_DIR ]; then
        for i in $USER_BASH_COMPLETION_DIR/*; do
                [[ ${i##*/} != @(*~|*.bak|*.swp|\#*\#|*.dpkg*|.rpm*) ]] &&
                        [ \( -f $i -o -h $i \) -a -r $i ] && . $i
        done
fi
unset i

Next, above the other block added to ~/.profile, add:

export USER_BASH_COMPLETION_DIR=~/.bash_completion.d

As for the contents of .bash_completion.d, I put the completion files supplied with darcs and cabal-install there, so in addition to the usual niceties like completion of paths on remote servers (e.g., for scp), I also get convenient completion behavior at the commandline, e.g., with cabal:

$ cabal install hsc[TAB]
hsc2hs hsc3 hsclock hscolour hscurses

Kid #1 is doing well enough that sometimes I forget that she's just a little over three years old, but then she'll whip out a malaprop or mangle an idiom to remind me. For example, while she was explaining to me that she was Lowly Worm and I was Huckle the Cat, she tripped and fell flat on her face, and the following conversation ensued:

Dad: Whoa! Are you alright?

Kid #1: No, Dad! [somewhat exasperated] I'm Lowly Worm...

The hslogger package provides a few handlers, e.g., for files and for Syslog, but the implementation of the file logger uses an MVar as a lock for writing log events. This isn't a bad thing, per se, since the GHC runtime will do a good job of queuing waiters for that lock, but it had a noticable impact on performance for perpubplat when I added some initial logging.

To decouple the log event dispatch and disk access, I whipped up a quick AsyncLogHandler (source) that does the job. Here is a quick tour in snippets, starting with a base data structure:

type Timestamp = String

type LogMessage = String

data AsyncLogHandler
    = AsyncLogHandler { channel :: Chan (LogRecord, LogMessage, Timestamp)
                      , level :: Priority }

An admittedly imperfect instantiation for the LogHandler type class:

instance LogHandler AsyncLogHandler where
    setLevel alh p = alh { level = p }
    getLevel alh = level alh
    emit alh lr msg = do { n <- now
                         ; writeChan (channel alh) $! (lr,msg,n) }
    close _ = return () -- make this better

This is less than perfect because it doesn't deal with altering the priority level or closing the stream on the fly, but I'm not concerned with either of those things for the moment. (To make that work, I'd need an additional level of encapsulation on the Chan that wraps log messages and control requests.) I'm on the fence with the necessity of making the writeChan strict in the second argument, but I believe it's necessary to ensure that the timestamp is computed when the message is dispatched as opposed to when it's output.

Setup just requires forking a lightweight thread to pull log messages out of the channel:

asyncHandler :: Int -> Handle -> Priority -> IO AsyncLogHandler
asyncHandler n h pri = do { c <- newChan
                          ; forkIO $ append n 0 h c
                          ; return $ AsyncLogHandler { channel = c
                                                     , level = pri } }

And then a tail-recursive function to pull the events, format output, and periodically (every n messages) flush the stream:

append :: Int -> Int -> Handle -> Chan (LogRecord, LogMessage, Timestamp) -> IO ()
append n i h c = do { ((p,m),l,ts) <- readChan c
                    ; (hPutStrLn h $ ts ++ " [" ++ (show p) ++ "] " ++ l ++ " - " ++ m)
                      `CE.catch` (printex h)
                    ; if i == n then
                          do { (hFlush h) `CE.catch` (printex h)
                             ; append n 0 h c }
                      else
                          append n (i+1) h c }

printex :: Handle -> CE.Exception -> IO ()
printex h e = hPutStrLn System.IO.stderr $ "Error writing to log handle "
              ++ (show h) ++ ": " ++ show e

And that's it.

Usability according to Abbott and Costello: