Guest User

Untitled

a guest
Feb 24th, 2013
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.38 KB | None | 0 0
  1. # Как писать решения на Хаскеле
  2.  
  3. Программы на Хаскеле компилируются на сервере с помощью GHC 7.6.1. Компилятор запускается со следующими опциями:
  4.  
  5. ghc -v0 -O %1
  6.  
  7. Вы можете скачать компилятор на [этой странице](http://www.haskell.org/ghc/).
  8.  
  9. ## Пример решения задачи
  10.  
  11. Пример решения задачи [1000. A + B problem](http://acm.timus.ru/problem.aspx?space=1&num=1000) на Хаскеле:
  12.  
  13. main = do
  14. [a, b] <- (map read . words) `fmap` getLine
  15. print (a+b)
  16.  
  17. Можно было бы также воспользоваться функцией `sum` и написать
  18.  
  19. main = interact $ show . sum . map read . words
  20.  
  21. ---
  22.  
  23. Пример решения задачи [1001. Обратный корень](http://acm.timus.ru/problem.aspx?space=1&num=1001) на Хаскеле:
  24.  
  25. main = interact $
  26. unlines . reverse . map (show.sqrt.fromInteger.read) . words
  27.  
  28. Этот код работает 1.9 секунды.
  29.  
  30. К сожалению, в Хаскеле стандартный тип `String` крайне неэффективен; если требуется считать или вывести много чисел, как в этой задаче, придётся прибегать к различным ухищрениям.
  31.  
  32. Во-первых, модуль `Data.ByteString.Char8` содержит строковый тип, основанный на массиве (а не на связном списке символов). Во-вторых, теперь мы не можем использовать стандартные функции `read` и `show` для ввода/вывода чисел; если аналог `read` ещё есть, то `show` уже придётся писать свой.
  33.  
  34. import Data.List
  35. import Data.Char
  36. import Data.Maybe
  37.  
  38. import qualified Data.ByteString.Char8 as B
  39.  
  40. Для чтения чисел применим функцию `readInteger`.
  41.  
  42. readD :: B.ByteString -> Double
  43. readD = fromInteger . fst . fromJust . B.readInteger
  44.  
  45. Выводить число придётся самостоятельно. Обратите внимание, что `iPart` и `fPart` имеют тип `Integer`; тут он быстрее, чем `Int64`.
  46.  
  47. showD :: Double -> B.ByteString
  48. showD n = B.pack $ show iPart ++ '.' : fDigs
  49. where
  50. (iPart, fPart) = quotRem (round (10000 * sqrt n)) 10000
  51. fDigs = let s = show fPart
  52. in replicate (4 - length s) '0' ++ s
  53.  
  54. Теперь всё довольно прозаично. Вывести числа одним куском не получится из-за ограничения по памяти в 16 MiB, так что с каждым числом работаем отдельно.
  55.  
  56. main = B.getContents >>=
  57. mapM_ (B.putStrLn.showD) . reverse . map readD . B.words
  58.  
  59. Новый код выполняется 0.16 секунды.
  60.  
  61. ## Массивы
  62.  
  63. Рекомендуется пользоваться unboxed массивами (`UArray` из `Data.Array.Unboxed` и `STUArray` из `Data.Array.ST`), так как они в несколько раз быстрее.
  64.  
  65. Если производительности всё ещё недостаточно, помогут функции `unsafeRead`, `unsafeWrite` и `unsafeAt` из `Data.Array.Base`. Они не производят проверок на принадлежность индекса границам массива, а также считают, что массив индексируется от 0.
  66.  
  67. ## Map и Set
  68.  
  69. Если в качестве ключей в Map или Set выступает `Int`, как это часто бывает, используйте `Data.IntMap` (`Data.IntSet`), оптимизированные специально для `Int`.
  70.  
  71. ## Ленивость
  72.  
  73. Никакое выражение в Хаскеле не вычисляется, пока оно не понадобится. То есть, можно вывести первый элемент бесконечного списка. Можно возвести 10 в 1000000 степень — и ничего не случится, пока вы не попытаетесь, например, вывести значение на экран.
  74.  
  75. Проблема кроется в том, что невычисленные значения (*thunks*) занимают много памяти, а на их вычисление тратится определённое «лишнее» время. Пример: строчка
  76.  
  77. foldl (+) 0 [1..1000]
  78.  
  79. , когда придёт пора её вычислять, сначала развернётся в пямяти в
  80.  
  81. (((...(0 + 1) + 2) + 3) + ... 999) + 1000
  82.  
  83. , что может привести к переполнению стека или неоправданно возросшему времени выполнения.
  84.  
  85. С ленивостью можно бороться тремя способами:
  86.  
  87. 1. Использование функций и структур данных, форсирующих вычисления (обычно помечены словом *Strict* или одинарной кавычкой — `foldl'`, `Data.Map.Strict`, `UArray` и т.д.)
  88. 2. Связывание значений при помощи `seq`. ``f (a `seq` b)`` означает, что при вычислении `b` будет автоматически вычислено и `a`, даже если оно нигде потом не понадобится.
  89. 3. Восклицание. Например, объявление функции `f !a = ...` аналогично ``f a = a `seq` ...``.
  90.  
  91. ## Некоторые полезные модули
  92.  
  93. * [Data.Complex](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/Data-Complex.html) — комплексные числа.
  94. * [Data.Fixed](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/Data-Fixed.html) — числа с фиксированным количеством знаков после запятой, а также обобщение `div` и `mod` на действительные числа.
  95. * [Data.Sequence](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/containers-0.5.0.0/Data-Sequence.html) — списки, поддерживающие быстрое добавление в оба конца, конкатенацию, доступ к произвольному элементу.
  96. * [Text.Printf](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/Text-Printf.html) — копия `printf` из языка C.
  97. * [Text.ParserCombinators.ReadP](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/Text-ParserCombinators-ReadP.html) — удобное написание парсеров для сложных грамматик (но и для арифметических выражений подойдёт).
  98. * [GHC.Exts](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/GHC-Exts.html) — определяет `groupWith` и `sortWith`. Отсортировать строки в порядке возрастания длины теперь можно так: `sortWith length strings`.
Advertisement
Add Comment
Please, Sign In to add comment