Jim Burton started a thread on haskell-cafe about working the Ruby Quiz problems in Haskell, and I decided to give it a go. I can't say that I'll work them all, but here's my solution to the first problem — implementing Bruce Schneier's Solitaire encryption algorithm. Among other things, a solution provides a quick walk-through of using Haskell's built-in Enum classes and list operations.
Step 1: A Deck of Cards
One of the ingredients for the cipher is a deck of 52 cards, numbered bridge-style from the ace of clubs through the king of spades and then followed by two jokers with suits "A" and "B". I'd like to implement the deck as a 2-tuple of a suit Enum, where the two jokers come from different suits, and a face Enum, like so:
data Suit = Clubs | Diamonds | Hearts | Spades | A | B
deriving (Enum, Show, Bounded, Eq)
data Face = Ace | Two | Three | Four | Five | Six | Seven
| Eight | Nine | Ten | Jack | Queen | King | Joker
deriving (Enum, Show, Bounded, Eq)
The "deriving" expression is worth some explanation after a 30-second, 30,000-foot look at Haskell's type system. A class in Haskell is a set of assertions of the form "there exists a function f with signature..." and potentially some default definitions, and a type can be an instance of the class if it has functions that meet the assertions. For example, the Eq class is defined:
(==), (/=) :: a -> a -> Boolean
x /= y = not (x == y)
x == y = not (x /= y)
For a given type that would play the role of the a, it's up to the implementer to supply (==) and (/=) functions with the correct signatures. The second and third statements mean that if the implementer only defines one of the two, the other is defined in the standard way. Nonetheless, the precise semantics of the functions — e.g., whether == remotely resembles "equals" or whether x==y implies not(x/=y) — are up to the implementer.
Back to the Suit and Face enumerated type definitions, the deriving tells Haskell that the type is an instance of the listed classes by inheriting default implementations. In simplest terms:
- An instance of
Enum has (at least) functions that convert from and to integer indices.
- An instance of
Bounded has a least element and a greatest element.
- An instance of
Show has a function to convert to a String.
- An instance of
Eq has (at least) an == operator.
(The links above are to the Zvon Haskell reference.) Haskell supplies these functions by numbering the enumerated elements starting at 0. A quick example with ghci:
*Main> Ace
Ace
*Main> succ Ace
Two
*Main> succ it
Three
*Main> fromEnum Queen
11
*Main> Ace == Two
False
(In ghci, it refers to the last result.)
Now, with a little more effort, we can create a Card type that enumerates the deck as tuples of (Suit,Face), except that we want to supply a custom enumeration, either using dictionary ordering for a normal card or a custom index for the jokers:
data Card = Cd Suit Face
deriving Eq
As above, this means that Haskell will supply an == for us, and it's important to have, e.g., to use functions like elemIndex:
Eq a => a -> [a] -> Maybe Int
I'll come to the Maybe monoid below, but the Eq a => means that the a in the definition must be an instance of Eq. Next up are a couple of convenience functions to access the components of a Card:
suit :: Card -> Suit
suit (Cd s _) = s
face :: Card -> Face
face (Cd _ f) = f
The Solitaire cipher imposes the bridge dictionary ordering on the deck with the A Joker and B Joker coming after the king of spades in the default order. So, the instance declaration that makes Card into an Enum:
instance Enum Card where
toEnum 53 = (Cd B Joker)
toEnum 52 = (Cd A Joker)
toEnum n = let d = n `divMod` 13
in Cd (toEnum (fst d)) (toEnum (snd d))
fromEnum (Cd B Joker) = 53
fromEnum (Cd A Joker) = 52
fromEnum c = 13* fromEnum(suit c) + fromEnum(face c)
Among other things, an instance of Enum makes the arithmetic sequence notation .. can be used to construct ranges, so the whole deck would be:
[(Cd Clubs Ace) .. (Cd B Joker)]
Note that typing this into ghci will result in an error. The type doesn't implement Show, so Haskell doesn't know how to display the elements of the list. This is easy enough to fix up:
show_suit :: Suit -> String
show_suit s = (take 1) (show s)
show_face :: Face -> String
show_face f = (take 1) (drop (fromEnum f) "A23456789TJQK$")
instance Show Card where
show c = (show_face (face c)) ++ (show_suit (suit c))
Now we can get a look at our deck:
*Main> [(Cd Clubs Ace) .. (Cd B Joker)]
[AC,2C,3C,4C,5C,6C,7C,8C,9C,TC,JC,QC,KC,
AD,2D,3D,4D,5D,6D,7D,8D,9D,TD,JD,QD,KD,
AH,2H,3H,4H,5H,6H,7H,8H,9H,TH,JH,QH,KH,
AS,2S,3S,4S,5S,6S,7S,8S,9S,TS,JS,QS,KS,
$A,$B]
(The linebreaks are added.) We're almost done, but the Solitaire cipher assigns different values to the cards than our enumeration does, so we wrap that up in a function:
value :: Card -> Int
value (Cd B Joker) = 53
value c = fromEnum c + 1
Step 2: Implement Shuffling
The Solitaire cipher uses a shuffling algorithm to generate a sequence of letters from the cards in the deck (thus the name for the cipher), and the next step is to implement the shuffling algorithm on top of the Card data type. There are three fundamental operations:
- "Move down" moves a card down in the deck. The deck is imagined to be circular, so moving a card "down" really involves swapping it with the card immediately below, where the card below the bottom of the deck is the top of the deck.
- "Triple cut" fixes the (inclusive) interval between two cards and swaps the top and bottom portions.
- ""Count cut" takes a number of cards off the top of the deck equal to the value of the card on the bottom of the deck and inserts those above the bottom card.
One approach would be to model these three operations as functions:
m :: Card -> [Card] -> [Card] -- "move down"
t_cut :: Card -> Card -> [Card] -> [Card] -- "triple cut"
c_cut :: [Card] -> [Card] -- "count cut"
With these in hand, the shuffle algorithm is:
c_cut ( (t_cut ja jb) ( (m jb) ((m jb) ( (m ja) ( deck )))))
where I'm using ja for (Cd A Joker) and jb for (Cd B Joker).
The whole implementation, complete with some inelegant bits for improvement, is here (or pretty-printed code here) and works:
*Main> encode "Code in Ruby, live longer!"
"GLNCQMJAFFFVOMBJIYCB"
*Main> decode it
"CODEINRUBYLIVELONGER"
Not all of the code is that pretty (I got a little bored toward the end...), so I'll just include a snippets here that demonstrate basic list handling and Maybe.
Maybe is a convenience that sidesteps the null return type problem in other languages. For example, here's a function that splits a String into five-character groups with all non-letters removed, all letters capitalized, and the last group padded:
cleanse :: String -> String
cleanse c = (map toUpper) ((filter isAlpha) c)
pad :: Int -> Char -> String -> String
pad n c s | length s < n = s ++ (replicate (n-length s) c)
pad n c s = s
maybe_split :: String -> Maybe(String,String)
maybe_split [] = Nothing
maybe_split s | w == "" = Just (pad 5 'X' s,w)
| True = Just (take 5 s, w)
where w = drop 5 s
quintets :: String -> [String]
quintets s = (unfoldr maybe_split) (cleanse s)
The Nothing value is just that, while Just wraps a real value. (Note that Nothing is outside of the normal value space of the wrapped type, so unlike null, this makes the semantics of "no return value" explicit.) The unfoldr function is a way to generate a list by repeatedly applying a function. It appends the first component of the return value to the list and then applies the function to the second component until the function returns Nothing. The quintets is almost the pretty-print routine discussed in the quiz and in the cipher:
*Main> quintets "That was an interesting exercise."
["THATW","ASANI","NTERE","STING","EXERC","ISEXX"]
*Main> concat (intersperse " " it)
"THATW ASANI NTERE STING EXERC ISEXX"
That said, the pretty-printed version is useless for computing the cipher...
I can think of a few ways to make this more elegant and efficient, and maybe I'll give that a shot later. In the meantime, hopefully it's an entertaining example.
Update. There is now a page on the Haskell wiki devoted to solutions.
