Программы на Хаскеле компилируются на сервере с помощью GHC 7.6.1. Компилятор запускается со следующими опциями:

ghc -v0 -O %1

Вы можете скачать компилятор на этой странице.

Примеры решения задач

Пример решения задачи 1000. A + B problem на Хаскеле:

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

Также можно воспользоваться функцией sum:

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

Пример решения задачи 1001. Обратный корень на Хаскеле:

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

Это решение работает на пределе ограничения по времени. К сожалению, в Хаскеле стандартный тип String крайне неэффективен. Если требуется считать или вывести много чисел, как в этой задаче, придется прибегать к различным ухищрениям.

Во-первых, модуль Data.ByteString.Char8 содержит строковый тип, основанный на массиве, а не на связном списке символов. Во-вторых, теперь мы не можем использовать стандартные функции read и show для ввода/вывода чисел. Если аналог read ещё есть, то show уже нужно писать свой.

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

import qualified Data.ByteString.Char8 as B

Для чтения чисел применим функцию readInteger.

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

Выводить число придется самостоятельно. Обратите внимание, что iPart и fPart имеют тип Integer, тут он быстрее, чем 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

Вывести числа одним куском не получится из-за ограничения по памяти, так что с каждым числом будем работать отдельно.

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

Новое решение работает более чем в 10 раз быстрее исходной версии.

Массивы

Рекомендуется пользоваться unboxed массивами (UArray из Data.Array.Unboxed и STUArray из Data.Array.ST), так как они в несколько раз быстрее.

Если производительности все еще недостаточно, помогут функции unsafeRead, unsafeWrite и unsafeAt из Data.Array.Base. Они не производят проверок на принадлежность индекса границам массива, а также считают, что массив индексируется от 0.

Map и Set

Если в качестве ключей в Map или Set выступает Int, как это часто бывает, используйте Data.IntMap (Data.IntSet), оптимизированные специально для Int.

Ленивые вычисления

Никакое выражение в Хаскеле не вычисляется, пока оно не понадобится. То есть, можно вывести первый элемент бесконечного списка. Можно возвести 10 в 1000000 степень — и ничего не случится, пока вы не попытаетесь, например, вывести значение на экран.

Проблема кроется в том, что невычисленные значения (thunks) занимают много памяти, а на их вычисление тратится определённое «лишнее» время. Например, строчка

foldl (+) 0 [1..1000]

когда придёт пора её вычислять, сначала развернется в пямяти в

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

что может привести к переполнению стека или неоправданно возросшему времени выполнения.

С ленивостью можно бороться тремя способами:

• Использование функций и структур данных, форсирующих вычисления (обычно помечены словом Strict или одинарной кавычкой — foldl', Data.Map.Strict, UArray и т.д.)
• Связывание значений при помощи seq. f (a `seq` b) означает, что при вычислении b будет автоматически вычислено и a, даже если оно нигде потом не понадобится.
• Восклицание. Например, объявление функции f !a = ... аналогично f a = a `seq` ....

Некоторые полезные модули

• Data.Complex — комплексные числа.
• Data.Fixed — числа с фиксированным количеством знаков после запятой, а также обобщение div и mod на действительные числа.
• Data.Sequence — списки, поддерживающие быстрое добавление в оба конца, конкатенацию, доступ к произвольному элементу.
• Text.Printf — копия printf из языка C.
• Text.ParserCombinators.ReadP — удобное написание парсеров для сложных грамматик (но и для арифметических выражений подойдет).
• GHC.Exts — определяет groupWith и sortWith. Отсортировать строки в порядке возрастания длины теперь можно так: sortWith length strings.