ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## How to write solutions on Haskell

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

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`.