Haskell programs are compiled on the server with GHC 7.6.1. The compiler is invoked with the following options:

ghc -v0 -O %1

You can find the compiler here.

Example solutions

The sample solution for the 1000. A + B problem in Haskell:

main = do
  [a, b] <- (map read . words) `fmap` getLine
  print (a+b)

You can also use the sum function:

main = interact $ show . sum . map read . words

The sample solution for the 1001. Reverse Root in Haskell:

main = interact $ 
  unlines . reverse . map (show.sqrt.fromInteger.read) . words

This solution hardly fits in the time limit constraint. Unfortunately, the standard Haskell String type is extremely inefficient. If you want to read or print a lot of numbers, as in this problem, you’ll have to use various tricks.

First of all, the module Data.ByteString.Char8 contains the string type based on the array, not on the linked list of characters. Second, we should no longer use standard functions read and show for input/output. There is a function similar to read, but you’ll have to implement your own version of show.

import Data.List
import Data.Char
import Data.Maybe

import qualified Data.ByteString.Char8 as B

We will use readInteger function to read the numbers.

readD :: B.ByteString -> Double
readD = fromInteger . fst . fromJust . B.readInteger

We’ll have to print the number ourselves. Please note that iPart and fPart are of type Integer, it is faster than Int64.

showD :: Double -> B.ByteString
showD n = B.pack $ show iPart ++ '.' : fDigs
  where
    (iPart, fPart) = quotRem (round (10000 * sqrt n)) 10000
    fDigs = let s = show fPart
            in  replicate (4 - length s) '0' ++ s

We are not able to print all the numbers at once because of the memory limit, so we’ll work with each number individually.

main = B.getContents >>=
  mapM_ (B.putStrLn.showD) . reverse . map readD . B.words

New solution works more than 10 times faster than the original version.

Arrays

We recommend you to use unboxed arrays (UArray in Data.Array.Unboxed and STUArray in Data.Array.ST), as they more efficient (up to several times).

If performance is still a problem, you can use functions unsafeRead, unsafeWrite and unsafeAt in Data.Array.Base. They drop array bounds checking and assume that array is indexed starting from 0.

Map and Set

If you use keys of type Int in Map or Set, consider using Data.IntMap or Data.IntSet, which are optimized for this frequent case.

Laziness

No expression in Haskell is evaluated until it’s needed. For example, you may print a first element of an infinite list. You can calculate 10 to the power of 1000000, and this would work as long as you don’t, for example, output this number.

The problem is that not yet calculated values (thunks) occupy much memory, and calculating them requires some "extra" time. For example, an expression

foldl (+) 0 [1..1000]

will, during its evaluation, expand into

(((...(0 + 1) + 2) + 3) + ... 999) + 1000

which may lead to stack overflow or unreasonable slowdown.

You can fight with lazy evaluation in three ways:

• Use functions and data structures enforcing the evaluation (they are usually marked with the word Strict or a single quote character: foldl', Data.Map.Strict, UArray etc.)
• Bind the values with seq. f (a `seq` b) means that evaluating b will automatically enforce evaluation of a, if it won’t be needed later.
• Exclamation. For example, function declaration f !a = ... is similar to f a = a `seq` ....

Some useful modules

• Data.Complex — complex numbers.
• Data.Fixed — fixed point numbers, and generalization of div and mod on real numbers.
• Data.Sequence — lists that support fast insertions to both ends, concatenation and random access.
• Text.Printf — implementation of printf from C.
• Text.ParserCombinators.ReadP — convenient for creating parsers of complex grammars (also good for arithmetic expressions).
• GHC.Exts — defines groupWith and sortWith. Now you can sort the strings in the order of increasing length like this: sortWith length strings.