Competitive Programming in Haskell: Basic Setup

I am the coach of my school’s competitive programming team and enjoy solving problems on Open Kattis. Since Kattis accepts submissions in a wide variety of languages (including Haskell, OCaml, Rust, Common Lisp, and even Prolog), I often enjoy submitting solutions in Haskell. Of the 946 problems I have solved on Kattis¹, I used Haskell for 607 of them (I used Java for the rest, except for one in C++).

After solving so many problems in Haskell, by now I’ve figured out some patterns that work well, identified some common pitfalls, developed some nice little libraries, and so forth. I thought it would be fun to write a series of blog posts sharing my experience for the benefit of others—and because I expect I will also learn things from the ensuing discussion!

The Basics: I/O

As a basic running example I’ll use the same example problem that Kattis uses in its help section, namely, A Different Problem. In this problem, we are told that the input will consist of a number of pairs of integers between \(0\) and \(10^{15}\), one pair per line, and we should output the absolute value of the difference between each pair. The given example is that if the input looks like this:

10 12
71293781758123 72784
1 12345677654321

then our program should produce output that looks like this:

2
71293781685339
12345677654320

Kattis problems are always set up this way, with input of a specified format provided on standard input, and output to be written to standard output. To do this in Haskell, one might think we will need to use things like getLine and putStrLn to read and write the input. But wait! There is a much better way. Haskell’s standard Prelude has a function

interact :: (String -> String) -> IO ()

It takes a pure String -> String function, and creates an IO action which reads from standard input, feeds the input to the function, and then writes the function’s output to standard output. It uses lazy IO, so the reading and writing can be interleaved with computation of the function—a bit controversial and dangerous in general, but absolutely perfect for our use case! Every single Kattis problem I have ever solved begins with

main = interact $ ...

(or the equivalent for ByteString, more on that in a future post) and that is the only bit of IO in the entire program. Yay!

From Input to Output

So now we need to write a pure function which transforms the input into the output. Of course, in true Haskell fashion, we will do this by constructing a chained pipeline of functions to do the job incrementally. The general plan of attack (for any Kattis problem) is as follows:

1. First, parse the input, that is, transform the raw String input into some more semantically meaningful representation—typically using a combination of functions like lines, words, read, map, and so on (or more sophisticated tools—see a later post).
2. Next, solve the problem, turning a semantically meaningful representation of the input into a semantically meaningful representation of the output.
3. Finally, format the output using things like show, unwords, unlines, and so on.

Idiomatic Haskell uses the composition operator (.) to combine functions. However, when solving competitive programming problems, I much prefer to use the reverse composition operator, (>>>) from Control.Arrow (that is, (>>>) = flip (.)). The reason is that since I often end up constructing long function pipelines, I want to be able to think about the process of transforming input to output and type from left to right at the same time; having to add functions from right to left would be tedious.

A Full Solution

So here’s my solution to A Different Problem:

main = interact $
  lines >>> map (words >>> map read >>> solve >>> show) >>> unlines

solve :: [Integer] -> Integer
solve [a,b] = abs (a - b)

A few notes:

• Since each line is to be processed independently, notice how I put the processing of each line inside a single call to map.
• We could probably inline the solve function in this case, but I prefer to split it out explicitly in order to specify its type, which both prevents problems with read/show ambiguity and also serves as a sanity check on the parsing and formatting code.
• The machines on which our solution will run definitely have 64-bit architectures, so we could technically get away with using Int instead of Integer (maxBound :: Int64 is a bit more than \(9 \times 10^{18}\), plenty big enough for inputs up to \(10^{15}\)), but there would be no benefit to doing so. If we use Integer we don’t even have to consider potential problems with overflow.

And one last thing: I said we were going to parse the input into a “semantically meaningful representation”, but I lied a teensy bit: the problem says we are going to get a pair of integers but I wrote my solve function as though it takes a list of integers. And even worse, my solve function is partial! Why did I do that?

The fact is that I almost never use actual Haskell tuples in my solutions, because they are too awkward and inconvenient. Representing homogeneous tuples as Haskell lists of a certain known length allows us to read and process “tuples” using standard functions like words and map, to combine them using zipWith, and so on. And since we get to assume that the input always precisely follows the specification—which will never change—this is one of the few situations where, in my opinion, we are fully justified in writing partial functions like this if it makes the code easier to write. So I always represent homogeneous tuples as lists and just pattern match on lists of the appropriate (known) length. (If I need heterogeneous tuples, on the other hand, I create an appropriate data type.)

Of course I’ve only scratched the surface here—I’ll have a lot more to say in future posts—but this should be enough to get you started! I’ll leave you with a few very easy problems, which can each be done with just a few lines of Haskell:

• Job Expenses
• Judging Moose
• Quick Estimate

Of course you can also try solving any of the other problems (as of this writing, over 2400 of them!) on Kattis as well.