Haskell

General information

You start out by finding a suitable problem to solve. Then you write code to solve the problem. After this, you submit the code to us for review. We will then compile your code and run it on some secret input. After some careful deliberation, you will get a judgement informing you whether your code behaved as expected or not.

Input/Output

Your program should read its input from standard input and produce output on standard output. This can for instance be done using interact.

Input will always follow the input specification (so you do not need to validate the input). Your output must follow the output specification.

Compiler settings

For Haskell, we use GHC version The Glorious Glasgow Haskell Compilation System, version 8.8.4 with the following flags: -O2 -ferror-spans -threaded -rtsopts {files}.

Runtime settings

For Haskell, we use the following runtime flags: +RTS -M{memlim}m -K8m -RTS.

Here {memlim} is the actual memory limit for the problem you are submitting to.

System libraries

You are allowed to use all standard libraries included with Haskell.

Hardware

We are currently using Dell PowerEdge R230 servers for judging. These are equipped with an Intel Xeon E3-1220V6 CPU running at 3.0 GHz and 8 GB RAM. A 64-bit Linux kernel is used.

Exiting

We will inspect the exit code of your program. If it is non-zero, we will judge your submission as Run Time Error.

Solving a problem

Now lets get down to business and write some code. The short tutorial below goes through the solution of A Different Problem.

  1. The problem
  2. Reading the input
  3. Computing the answer
  4. The solution

Step 1: The problem

You are tasked with writing a program that computes the difference between integers. Sounds simple, doesn't it? Well, as we will see, the problem still holds some small difficulties.

Step 2: Reading the input

One thing to note is that the integers can be fairly large, as large as 1015. This means that the Haskell Int may not be sufficient. Rather, Integer is needed. It is a good idea to test our solution on very large inputs to make sure it performs as expected.

Now that we have determined a suitable type, we just have to read the data. Reading is done from standard input. In this problem, we should read until the end of the file (in other problems, there might be an integer at the beginning of the input, specifying how much to read, or there might be a special indicator denoting that there is nothing more to read). The most straight forward pattern is to use the Haskell function interact transform where transform is some function that maps a String (the entire input) to another String (the entire output). In our case we use words to break the input into a list of strings, each string being the digits in a number. Then we use map read to turn it into a list of Integer:

readInput = (map read) . words -- "1 2\n3 5\n" --> ["1", "2", "3", "5"] --> [1, 2, 3, 5] main = interact (writeOutput . solve . readInput) --TODO: solve and writeOutput

Step 3: Computing the answer

Now that we've read the input as a list of Integer, we can process them in pairs, computing the absolute value of their difference.

solve [] = [] solve (a:b:rest) = abs(a - b):(solve rest)

Finally, it's time to print the result. Using map show to turn the list of integers (the result) into a list of String, and then apply unlines to turn this list into a single string with line breaks.

writeOutput = unlines . (map show) -- [1, 2] --> ["1", "2"] --> "1\n2\n"

Step 4: The solution

Now we are basically done, all that remains is to combine the above parts.

different.hs

So are we using Int or Integer in the computations? It turns out that read defaults to Integer, so we are fine.

External documentation

  1. Haskell