Sneaky Mustard

16:30 <@andre> is 2009 looking good so far?
16:30 < arun> yes
16:31 < arun> but it smells bad
16:31 <@andre> LOL

This afternoon I was talking to gatz on #bsd about the origins of the name "Sneaky Mustard"… All the credit goes to phi, back in 2004:

13:24 <@andre> but there’s a reason it’s called sneaky mustard
13:25 <@andre> one day i complained about not being able to find something
13:25 <@andre> and phi said "just like mustard"
13:25 <@andre> and i was like "huh?"
13:25 <@andre> and he said he can never find the mustard in his fridge when he
               wants it
13:25 <@andre> so, sneaky mustard :p
13:26 < DaGr8Gatzby> Lol
13:26 < DaGr8Gatzby> hahaha shit that’s fuckin classic

The other day I  implemented the Fisher-Yates Shuffle in Haskell. The algorithm is pretty simple, but writing it in Haskell was a challenge, because I had to work with the ST monad (more specifically STArrays), which I had never done, in order to write an efficient version (Haskell’s immutable arrays are simpler to use but wouldn’t work very well because of the copying needed on every update), and not only that, but also combine it with the State monad using a monad transformer, because the shuffling algorithm requires a random number generator, and the State monad is useful to keep it updated without the need for extra parameters in functions.

These are the modules we’ll use:

> import Control.Monad.ST
> import Control.Monad.State.Strict
> import Data.Array.ST
> import Data.Array.IArray
> import System.Random

The first function we need is one that swaps the elements of an array, given their indices. The code is straightforward, and the only thing worth mentioning is that since we’re using an STArray, the function has to be in the ST monad. Here’s the code:

> swap :: STArray s Int a -> Int -> Int -> ST s ()
> swap arr i j = do
>   x <- readArray arr i
>   y <- readArray arr j
>   writeArray arr i y
>   writeArray arr j x

The next step would be the main action of the shuffling algorithm, which is selecting a random array index and swapping it with the current upper bound on the array indices. This is where our need for the State monad transformer (StateT) appears. We need to keep our random number generator in the State monad, and also use the ST monad for the array operations. So we define a type synonym that represents that:

> type ShuffleT s a = StateT StdGen (ST s) a

This simply means we’re using the State monad to store an StdGen and that ST s is our inner monad. Computations of this type require a parameter of type s, which is required by the ST monad, and one of type a, which is the type of the return value of the computation.

Now we need a function that will give us a random array index, that is, an integer in some range delimited by the function’s parameters. Since we’re using the State monad, we’ll retrieve and update the random number generator using the get and put functions to access this implicit parameter.

> randomInt :: Int -> Int -> ShuffleT s Int
> randomInt lb ub = do
>   g <- get
>   let (r, g') = randomR (lb, ub) g
>   put g'
>   return r

With that, we can write the function that does the random swapping very simply:

> swapRand :: STArray s Int a -> Int -> Int -> ShuffleT s ()
> swapRand arr lb ub = do
>   r <- randomInt lb ub
>   lift $ swap arr r ub

Note that we can call randomInt directly, because the State monad is the outer monad in our stack, but we need to lift the result of swap, because it’s in ST, our inner monad (I guess calling it "upper" instead helps understanding the purpose of lift, if you consider a pile of stacked monads, with State at the bottom and ST at the top).

Finally, we can write the main function, which simply calls swapRand multiple times, each time decrementing the upper bound parameter until every element has been swapped. I’ll call it shuffle’.

> shuffle' :: STArray s Int a -> ShuffleT s (STArray s Int a)
> shuffle' arr = do
>   (lb, ub) <- lift $ getBounds arr
>   mapM_ (swapRand arr lb) [ub, ub-1 .. lb]
>   return arr

Note that the return type now is ShuffleT s (STArray s Int a), because we’re in ShuffleT and want to return an STArray. We use mapM_ with a decreasing range for the upper bounds, and apply each one to the partial application of swapRand to its first two arguments. Once again we have to lift the return value of a function that lives in the ST monad, this time getBounds.

The last step is getting the shuffled array out of the ST monad. Here I’m assuming that the array won’t be modified by the rest of the program, so we’re given an immutable array as an argument, convert it to a mutable array, shuffle it, extract it from StateT (ShuffleT in our case), freeze it, and finally extract it from ST. The array needs to be frozen in order to be extracted from ST, to avoid the mutability of the array to "escape" to the pure world. Credit for this wrapper goes to Ryan Ingram, who kindly explained this to me in Haskell-Cafe. The function also returns the modified random number generator for further use in the program. Here it is:

> shuffle :: Array Int a -> StdGen -> (Array Int a, StdGen)
> shuffle arr gen = runST $ do
>   stArr <- thaw arr
>   (stArr', gen') <- runStateT (shuffle' stArr) gen
>   arr' <- unsafeFreeze stArr'
>   return (arr', gen')

And that’s it! The only hard function, in my opinion, is shuffle, the wrapper around shuffle’. It’s not hard in the sense that the code is hard to follow, but you have to understand what needs to be done to get stuff out of the ST monad. Knowing that, it’s actually pretty simple.

Out of boredom, I wrote a daemonize function in Haskell, following the steps in Advanced Programming in the UNIX Environment. Here it is:

module Daemon where

import System.Directory
import System.Exit
import System.Posix.Files
import System.Posix.IO
import System.Posix.Process
import System.Posix.Signals

daemonize :: IO () -> IO ()
daemonize f = do
  omask <- setFileCreationMask 0
  pid <- forkProcess child
  exitSuccess

  where

    child :: IO ()
    child = do
      sess <- createSession
      ohandler <- installHandler sigHUP Ignore Nothing
      forkProcess grandChild
      exitSuccess

    grandChild :: IO ()
    grandChild = do
      setCurrentDirectory "/"
      devNullFd <- openFd "/dev/null" ReadWrite Nothing defaultFileFlags
      mapM_ (closeAndDupTo devNullFd) [stdInput, stdOutput, stdError]
      f
      where
        closeAndDupTo dupFd fd = closeFd fd >> dupTo dupFd fd


I’m collecting a list of movies that I want to watch, mostly taken from this thread at Netphoria. I thought I’d post the list here just in case anyone has seen any of these and wants to share a comment. Here’s the list, in no particular order:

• Let the Right One In (Låt den rätte komma in)
• RocknRolla
• Slumdog Millionaire
• Appaloosa
• Komm, süsser Tod
• The Wackness
• Man on Wire
• Dogville
• Good Bye Lenin
• Goodfellas
• Gone Baby Gone
• Girl, Interrupted
• The Magdalene Sisters
• Bittersweet life (Dalkomhan Insaeng)
• Edge of Heaven (Auf der anderen Seite)
• The Visitor
• Miller’s Crossing
• High Fidelity
• 21 Grams
• The Darjeeling Limited
• Blow
• 25th Hour
• London
• A Good Year
• The diving bell and the butterfly (Le scaphandre et le papillon)
• La vie en rose (La Môme)
• Juno
• Happiness
• 13 Tzameti

Edit: Added a few more:

• Tideland
• Gegen die Wand
• Donnie Brasco
• Traffic
• Control
• Jackie Brown
• Before the Devil Knows You’re Dead
   

I’ve just set up a microblog for Sneaky Mustard at micro.sneakymustard.com. This will be a simple collection of random pictures and quotes that I happen to find. I’m using Asaph as the microblog engine, and it’s really awesome.