» Secret Santas in Haskell I: Preliminaries #

Paul R. Brown @ 2006-12-17

A while back I posted a solution to the first Ruby Quiz in Haskell. The next quiz problem is about "secret santas", which I'll rephrase as follows:

Given a set P of people, each with a first name, last name, and email address, define a bijective "secret santa" function s :: P -> P such that (last . s)(p) /= last(p) for all p in P, where last :: P -> String maps a person to their last name.

There are also some requirements about reading the names from a file and sending email, and I'll deal with those up front, here in Part I. Subsequent parts (all available under the secretsanta tag, in case you choose to follow the thread) contain some additional background on the problem (including a simple, strong characterization of when solutions exist) and a couple of solution techniques.

Reading and Writing People

Haskell has the Read and Show type classes that provide, respectively, the ability to read and write a type. Writing out one of the secret santa participants is straightforward:

data Participant = Participant (String,String,String)

first_name :: Participant -> String
first_name (Participant (f,_,_)) = f

last_name :: Participant -> String
last_name (Participant (_,l,_)) = l

email_addr :: Participant -> String
email_addr (Participant (_,_,a)) = a

instance Show Participant where
    show p = (last_name p) ++ ", " ++ (first_name p) ++ " <"
             ++ (email_addr p) ++ ">"

(Show and Read can be obtained in this case by deriving their implementations, but the representation is practical but not that appealing.) To read in the same representation, a very simple parser is preferable to implementing the low-level functions that Haskell requires (see, e.g., 8.3 of the GITH). Parsec makes it simple:

normalize :: String -> String
normalize = unwords.words

participant_parser :: Parser Participant
participant_parser = do { last_n <- many1 (letter <|> space)
                        ; char ','
                        ; first_n <- many1 (letter <|> space)
                        ; char '<'
                        ; email_a <- many1 (letter <|> oneOf ".-_@+")
                        ; char '>'
                        ; return (Participant (normalize first_n,
                                               normalize last_n,
                                               normalize email_a))

Parsec also makes it simple to parse a list of participants from a flat file, like so:

participants_parser :: Parser [Participant]
participants_parser = participant_parser `sepEndBy` (many1 newline)

load_participants :: String -> IO [Participant]
load_participants filename = do { result <- parseFromFile participants_parser filename
                                ; case (result) of 
                                    Left err -> (error (show err))
                                    Right val -> return val

If you're not a Haskell person, it's worth stopping to scratch your head about why the load_participants function creates values of type IO [Participant] instead of [Participant]. When I first started learning Haskell, I searched in vain for a function with a signature like f :: IO a -> a, but the nature of Haskell dictates that no such function can exist. (This is not a general trait of monads, as it's straightforward to unwrap Maybe or Either.) In a nutshell, IO exists to both separate and integrate the purely functional world where referential transparency reigns and the external world, and the list doesn't exist in the functional world until the I/O operation (reading the file) is performed, thus the need to deal with the inner value within an IO context, e.g., within a main function, in an interactive session, or by lifting functions into the IO monad.

Sending Email

There are two easy ways to send email. The simplest is to use the System.Cmd module included with the core libraries and the system function. The other way is the sendmail function from the Network.Email.Sendmail module in MissingH. Neither one is particularly exciting...

A Little Abstraction Goes a Long Way

Before I actually get going in the other parts, I'd like to introduce a layer of abstraction:

class Marked a where
    marker :: a -> String

instance Marked Participant where
    marker = last_name

This gets me out of having to type Participant everywhere and makes the functions easier to reuse, e.g., for balls where marker is color or animals where marker is species or music tracks where marker is artist and album, or...


← 2006-10-25 — Solitaire Cipher in Haskell
→ 2006-12-17 — Secret Santas in Haskell II: Orbits and Lists