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 Kattis1, 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 and , 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
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:
- First, parse the input, that is, transform the raw
Stringinput into some more semantically meaningful representation—typically using a combination of functions like
map, and so on (or more sophisticated tools—see a later post).
- Next, solve the problem, turning a semantically meaningful representation of the input into a semantically meaningful representation of the output.
- Finally, format the output using things like
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,
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
- We could probably inline the
solvefunction in this case, but I prefer to split it out explicitly in order to specify its type, which both prevents problems with
showambiguity 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
maxBound :: Int64is a bit more than , plenty big enough for inputs up to ), but there would be no benefit to doing so. If we use
Integerwe 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
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
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:
Of course you can also try solving any of the other problems (as of this writing, over 2400 of them!) on Kattis as well.
Did I mention that I really enjoy solving competitive programming problems?↩