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.
The sample solution for the 1000. A + B problem in Haskell:
main = do
[a, b] <- (map read . words) `fmap` getLine
You can also use the
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
show for input/output. There is a function similar to
read, but you’ll have to implement your own version of
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
fPart are of type
Integer, it is faster than
showD :: Double -> B.ByteString
showD n = B.pack $ show iPart ++ '.' : fDigs
(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.
We recommend you to use unboxed arrays (
Data.Array.ST), as they more efficient (up to several times).
If performance is still a problem, you can use functions
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.IntSet, which are optimized for this frequent case.
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:
- Bind the values with
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
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
sortWith. Now you can sort the strings in the order of increasing length like this:
sortWith length strings.