> unwords ( reverse ( words ( "you can cage a swallow can't you" ) ) ) "you can't swallow a cage can you"
Practice and Learn
I’d like to do better in programming contests, but I have little time to train. Furthermore, I’m mostly interested in the algorithms; I’m far less interested in perfecting boilerplate, memory allocation, avoiding overflow and so on.
Hence Haskell: it takes care of much of the paperwork, thanks to features like type inference, garbage collection, and arbitrary precision integer arithmetic.
In the past, I focused on Google Code Jam’s Past Problems for several reasons:

Online judge.

Accepts any language.

Diverse highquality problems.

Solutions, so I have no qualms about publishing my own.
Unfortunately, the website has changed considerably. My links may no longer work. Also, the judging system has changed. They once let anybody submit output for given input for judgement. Now, a user must create an account, sign in, and submit code.
Reverse Words
Our task is easy to express in English: with separating spaces, join the words of the reverse of the list of words in a given line.
Our task is arguably even easier to express in Haskell:
As one might guess, words
splits a line into a list of words, reverse
reverses a list, and unwords
joins a list of words into a single line
with separating spaces.
We turn this into a full program satisfying contest conditions with interact
,
a function that passes the entire input as a giant string to a function of our
choice, then prints the returned string to standard output.
 reversewords.hs
main = interact $ unlines . zipWith (++)
["Case #" ++ show t ++ ": "  t < [1..]] . map solve . tail . lines
solve = unwords . reverse . words
The ($)
operator saves us a pair of parentheses. In general, we can
rewrite something like a(b(c(d)))
as the less cluttered a $ b $ c $ d
.
The code following the $
defines the function we pass to interact
.
Because the function composition operator (.)
is rightassociative,
to understand our definition, we read it right to left.
It breaks the input string into lines (lines
), then ignores the first line
(tail
); the first line contains the number of test cases which is handy for
languages with primitive memory allocation facilities.
We then run our algorithm on each input line (map solve
), and prepend "Case
#x:" to the result (zipWith (++)
and the list comprehension). Finally, we
join all the output lines together into a giant string (unlines
) to return to
interact
.
This tiny program showcases several crown jewels of Haskell:

pointfree programming: instead of defining "f(x) = g(h(x)) for all x", we dispense with the distracting variable x and simply say
f = g . h
. 
list comprehensions: expressions like
[t^2  t ← [1..]]
mimic how mathematically inclined humans define sets when communicating with each other. 
lazy evaluation: why does the infinite list
[1..]
work? Because Haskell only computes as much as it needs. Lazy evalution also implies our program doesn’t wait for the entire input before moving to the next step. On the contrary, it’s more like piping in the shell: it only reads and computes on as much input is needed to print the next character. 
map: half of Google’s famed MapReduce is named after this function. (The other half is named after another functional programming gem which Haskell programmers call
fold
instead of "reduce".) 
currying: we’re composing
map solve
with other functions with(.)
, but how ismap solve
a function? Easy: it’s the function that maps thesolve
function over a given input list. In other words, iff = map solve
, thenf x = map solve x
. 
flexible fixity: we can dance between infix and prefix notation, mixing the two for maximum clarity.

boilerplatefree strong static types: we have no type declarations, yet not only is it impossible to confuse a string with an int, but it’s also impossible to confuse a pure function with an impure function. The only impure function here is
interact
; the rest of the program is pure. 
equal rights: in many languages, the equal sign means assignment, not equality. That is, the right side gets assigned to something the left side refers to. In Haskell, provided the function is pure, any time we see the stuff on one side of the equals sign, we can swap it out for the stuff on the other, a property known as referential transparency.
But enough navelgazing for now. After downloading the input data (via the webpage), we compile and run the program, then submit the output (via the webpage) for some easy points:
$ ghc reversewords $ ./reversewords < in > out
We could write a faster solution in C: we’re given bounds on the input size, so we could do everything on the stack and avoid heap manipulations that Haskell must be doing behind the scenes. My younger self would have done this, and relished the speed.
How much running time would this shave off? Let’s be generous and say we could save 5 seconds by using C. Now consider how much time it takes to write a complete C program, versus 3 words and 2 dots in Haskell. Even with an advanced IDE, it’s hard to imagine the savings in running time compensating for the cost in programming time.
Store Credit
Since we may assume each input test case has a unique pair of items whose cost sum to the desired amount, we can write a straightforward solution with a list comprehension:
solve c ps = let m = length ps  1
in head [show (i + 1) ++ " " ++ show (j + 1) 
i < [0..m1], j < [i+1..m], ps!!i + ps!!j == c]
Here, c
is the desired amount, and ps
is the list of prices of the items.
We slap on a dab of code to parse the input and print the "Case #x:" preamble:
main = interact $ unlines . zipWith (++)
["Case #" ++ show t ++ ": "  t < [1..]] . f . tail . lines
f [] = []
f (_c:_:_ps:s) = solve (read _c) (map read $ words _ps) : f s
But this solution is slow. Haskell lists truly are linked lists, so looking up the nth member takes n steps, implying cubic running time. We should instead use arrays for a quadratictime solution. (A hash table could solve the problem in linear time, but the inputs are so small we may as well stick with arrays.)
import Data.Array
main = interact $ unlines . zipWith (++)
["Case #" ++ show t ++ ": "  t < [1..]] . f . tail . lines
f [] = []
f (_c:_:_ps:s) = solve (read _c) (map read $ words _ps) : f s
solve c ps = let
n = length ps
a = listArray (1, n) ps
in head [show i ++ " " ++ show j 
i < [1..n1], j < [i+1..n], a!i + a!j == c]
Lists and Arrays
The two solutions above serve as an introduction to lists and arrays in Haskell.
Haskell’s lists are a pleasure to work with. Standing on the shoulders of Lisp, much thought went into their design, and over the years, a rich and luxurious library of list functions has evolved and matured.
Arrays on the other hand, though tolerable, are less refined. Within the
Data.Array
namespace there are several kinds of arrays to choose from, all
slower than good old C arrays. Moreover, Data.Vector
may be better sometimes,
and this module must be installed separately to the base system.
Updating a single array element takes constant time in other languages, but unless we make a special effort, in Haskell, this operation is as expensive as copying the entire array.
Thus for smaller problems, we often reach for lists first, and consider arrays later, the opposite of our behaviour when programming in Clike languages.