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?↩
Cool stuff. As a beginner to intermediate Haskeller, I am going to love this series. I already learned about `unlines`, `unwords` and `(>>>)`. So glad this post showed on Planet Haskell today.
But I don’t think I could bring myself to be satisfied with partial functions. So I would probably write something like:
solve l = abs . (foldr1 (-)) $ l
In France we have a saying: “Qui peut le plus peut le moins”.
In English, it could translate to “If you can do big things, you can still also do little things”. In this case, if you can solve lists of integers of any length, you can still solve lists of two integers.
Cool, I hope you continue to enjoy the series!
Your definition of solve is cute. (Note that you could eta-reduce it and just write
solve = abs . foldr1 (-)
I don’t think I like it, though, since it is much harder to write and understand, for questionable benefit. Remember that the goal here is to optimize for the amount of time taken to write a correct program, NOT for maintainability or theoretical elegance. Yes, it does not crash on more lists (note it still crashes on the empty list!), but so what? You say “if we can solve lists of integers of any length”, but what does it mean to “solve” a longer list? It means nothing because the problem only specifies what to do with exactly 2 integers.
Here’s another perspective that might be helpful. The problem is that the function’s type and implementation do not match: the function is only a partial specification of the behavior required by the type. You are looking at the type and trying to make the function bigger to match; but from another point of view what we really want to do is make the type *smaller*. That is, I really want to write something like (this is pseudo-Haskell):
solve :: List 2 Integer -> Integer
solve [a,b] = …
i.e. solve takes lists of exactly 2 integers. From this point of view the function is not partial at all, it just has a type that can’t (easily) be specified in Haskell, so we have to write a type that is an overapproximation of its true type. (Its true type *can* be specified in Haskell using more advanced type system features, but it would be overkill for solving competitive programming problems.)
Maybe I should turn this discussion into another blog post. =)
use of >>> is quite clever and inpiring
Pingback: Competitive Programming in Haskell: Scanner | blog :: Brent -> [String]
I find >>> confusing particularly if reading subsequent posts in this vein without having read this one! In my limited experience using . is idiomatic particularly for unsophisticated users. I find it bizarre that the arrow package bothers to define <<< as a synonym for . In general, IMHO, weird symbols, instead of names, hinders adoption and understanding of Haskell. . is fine for function composition as it is very close to the math symbol for function composition.
Pingback: Competitive programming in Haskell: summer series | blog :: Brent -> [String]