Некоторые основные библиотеки

Библиотеки GHC Core

В рамках курса уже упоминался репозиторий Hackage. Однако большинство библиотек на Hackage разработаны третьими лицами. Часть библиотек, которые обычно называют Core Libraries, поставляется вместе с компилятором. Рассмотрим некоторые из них.

  • base – Основная часть стандартной библиотеки. Большинство модулей, которые мы обсуждали, определены здесь.
  • array – Чистые и изменяемые массивы. Модуль Data.Array. Обычно используют более высокоуровневый интерфейс из vector.
  • binary – Де-/сериализация в двоичное представление. Модуль Data.Binary
  • bytestring – Массивы (“строки”) байт. Близкий аналог строк C. Модуль Data.ByteString
  • containers – Типовые контейнеры. Модули Data.Graph, Data.Map, Data.IntMap, Data.Set, Data.IntSet, Data.Tree, Data.Sequence.
  • deepseq – “Глубокое” (структурное) форсирование значений. Модуль Control.DeepSeq
  • directory – Манипуляции с директориями ФС. Модуль System.Directory
  • filepath – Манипуляции с путями к файлам. Модуль System.FilePath
  • mtl – Типовые трансформаторы монад. Высокоуровневая библиотека на основе transformers.
  • parsec – Комбинаторы парсеров на основе монад. Эффективный нисходящий синтаксический анализ аналогичный рекурсивному спуску.
  • stm – Software Transactional Memory, абстракция для коммуникации между параллельными потоками. Модули Control.Concurrent.STM и Control.Monad.STM
  • text – Эффективное представление текстовых данных. Модуль Data.Text.
  • time – Вычисления с датой и временем. Модуль Data.Time
  • transformers – Типовые трансформаторы монад. Низкоуровневая библиотека, совместимая с Haskell98.

Другие часто используемые библиотеки

Системные и утилиты

  • typed-process – запуск и управление процессами ОС
  • random – генерация псевдослучайных чисел
  • string-interpolate – интерполяция строк

Регулярные выражения

  • regex-base и пр – поддержка регулярных выражений. Популярные бэкенды включают regex-tdfa (реализация регулярных выражений POSIX на основе конечных автоматов) и regex-pcre (на основе библиотеки PCRE)

Параллельное программирование

  • async – Control.Concurrent.Async, высокоуровневый интерфейс асинхронных и параллельных вычислений
  • parallel – оппортунистическое параллельное программирование

Тестирование

  • QuickCheck – библиотека автоматизированного тестирования свойств
  • hspec – фреймворк тестирования наподобие rspec из Ruby
  • tasty – фреймворк тестирования
  • criterion – тестирование производительности

Контейнеры

  • unordered-containers – хэш-таблицы и хэш-множества
  • vector – эффективный интерфейс к array
  • grid – произвольные сетки на основе vector
  • vinyl – расширяемые записи

Веб

  • req – HTTP-клиент
  • wai – API веб-приложений
  • warp – веб-сервер для wai
  • servant – фреймворк для REST API

Форматы файлов

  • cassava – ввод-вывод CSV-файлов
  • aeson – де-/сериализация JSON
  • HsYAML – де-/сериализация YAML
  • pandoc – чтение/запись различных форматов документов и преобразования над AST

Парсеры

  • attoparsec, megaparsec, nanoparsec, etc – различные вариации на тему parsec
  • trifecta – комбинаторы парсеров с красивыми диагностическими сообщениями
  • optparse-applicative – аппликативный парсер аргументов командной строки

UI и графика

  • gloss – декларативный фреймворк 2D-графики
  • brick – декларативный фреймворк 2D-графики в терминале (только Unix)
  • reanimate – декларативная анимация
  • threepenny-gui – GUI через браузер
  • gtk2hs – GUI на основе gtk+
  • gi-gtk-declarative – другой GUI на основе gtk+

Потоковая обработка

  • streamly
  • conduit
  • streaming
  • pipes

Файлы cabal

Для описания программного пакета и зависимостей используются файлы *.cabal. Типовая структура:

-- Версия формата файла
cabal-version:      2.4

-- Название проекта
name:               test

-- Версия проекта
-- Правила версионирования на https://pvp.haskell.org
-- Вкратце:         +-+------- Ломающие API изменения
--                  | | +----- Не ломающие API изменения
--                  | | | +--- Без изменения API
version:            0.1.0.0

-- Короткое описание проекта
synopsis:

-- Длинное описание проекта
-- description:

-- URL домашней страницы проекта
homepage:

-- URL багтрекера
-- bug-reports:

-- Лицензия на проект
license:            MIT

-- Файл с текстом лицензии
license-file:       LICENSE

-- Авторы
author:             Nikolay Yakimov

-- E-mail адрес мейнтейнера
maintainer:         [email protected]

-- Дополнительные файлы исходных кодов
extra-source-files: CHANGELOG.md

-- Описание библиотеки (может быть только одна)
library
    -- Модули экспортируемые библиотекой
    exposed-modules:  MyLib

    -- Модули, используемые, но не экспортируемые библиотекой
    -- other-modules:

    -- Расширения языка
    -- other-extensions:

    -- Зависимости
    build-depends:    base ^>=4.14.1.0

    -- Директории, в которых содержатся исходники
    hs-source-dirs:   lib

    -- Версия базового языка
    default-language: Haskell2010

-- Исполняемый файл, их может быть несколько
executable myexe
    -- Имя файла с модулем Main
    main-is:          Main.hs

    -- Прочие модули
    -- other-modules:

    -- Расширения языка
    -- other-extensions:

    -- Зависимости
    build-depends:
        base ^>=4.14.1.0,
        test

    -- Директории, в которых содержатся исходники
    hs-source-dirs:   app

    -- Версия базового языка
    default-language: Haskell2010

-- Набор тестов
test-suite test
    -- Версия базового языка
    default-language: Haskell2010

    -- Тип тестов. Обычно exitcode-stdio-1.0
    type:             exitcode-stdio-1.0

    -- Директории, в которых содержатся исходники
    hs-source-dirs:   test

    -- Имя файла, содержащего модуль Main для тестов
    -- Только если type: exitcode-stdio-1.0
    main-is:          MyLibTest.hs

    -- Зависимости
    build-depends:    base ^>=4.14.1.0

Интерактивно сгенерировать файл cabal можно командой cabal init -i в пустой директории.

Формат hpack

Альтернативой файлам cabal является использование описания package.yaml и hpack для генерации файла cabal:

name: test
version: 0.1.0.0
synopsis: ""
license: MIT
license-file: LICENSE
author: Nikolay Yakimov
maintainer: [email protected]
extra-source-files: CHANGELOG.md
dependencies:
  - base ^>=4.14.1.0
library:
  exposed-modules:  MyLib
  source-dirs:   lib
executables:
  app:
    main: Main.hs
    source-dirs: app
tests:
  test:
    source-dirs: test
    main: MyLibTest.hs

Сгенерировать структуру проекта с package.yaml можно выполнив stack new <name>, где <name> – имя нового проекта (будет создана новая директория)

Примеры

Упражнения

Упражнение 1

Добавление в конец списка имеет сложность \(O(n)\). В containers определён тип Seq, реализующий более эффективную структуру. Однако есть более простой вариант, называемый DList:

newtype DList a = DL { unDL :: [a] -> [a] }

Операция добавления в начало DList может быть реализована следующим образом:

infixr `cons`
cons :: a -> DList a -> DList a
cons x xs = DL ((x:) . unDL xs)

Реализуйте следующие операции:

-- 1. Конструирует пустой DList
empty :: DList a
empty = undefined

-- 2. Конструирует DList из одного элемента
singleton :: a -> DList a
singleton = undefined

-- 3. Преобразует DList в обычный список
toList :: DList a -> [a]
toList = undefined

-- 4. Добавляет элемент в конец DList
infixl `snoc`
snoc :: DList a -> a -> DList a
snoc = undefined

-- 5. Конкатенация DList
append :: DList a -> DList a -> DList a
append = undefined

В качестве шаблона рекомендуется использовать https://github.com/haskell-course-lierdakil/dlist-template, там определены тесты корректности и производительности.

Упражнение 2

Реализуйте эффективную (амортизированную \(O(1)\)) функциональную очередь на основе списков, использующую следующие определения и интерфейс:

-- См. Chris Okasaki, Purely Functional Data Structures
data Queue a =
  Queue { enqueue :: [a]
        , dequeue :: [a]
        } deriving (Eq, Show)

-- Добавить элемент в конец очереди
push :: a -> Queue a -> Queue a
push = undefined

-- Удалить элемент из начала очереди
pop :: Queue a -> Maybe (a, Queue a)
pop = undefined

Конец очереди – первый элемент enqueue. Начало очереди – первый элемент dequeue.

Указание (сначала попробуйте самостоятельно; нажмите чтобы показать):

Если при выполнении pop оказывается, что dequeue пуст, а enqueue – нет, элементы enqueue перемещаются в dequeue в обратном порядке.

В качестве шаблона рекомендуется использовать https://github.com/haskell-course-lierdakil/queue-template, там определены тесты корректности и производительности.

Упражнение 3 (*)

Реализуйте простую игру “крестики-нолики” на поле 3x3 на языке Haskell. Для графики рекомендуется использовать библиотеки gloss или brick.