Подходы к вводу/выводу в Haskell. Часть 1

25.01.2022 | Категория Программирование

Оглавление:

Введение
Сложности
Монады
Монады и I/O
Комбинаторные парсеры

Парсер своими руками
Готовые библиотеки

Заключение

Введение
Популярность Haskell на рынке растёт, зарплаты специалистам на сайтах с вакансиями выглядят соблазнительно, но беглое изучение кода и статей отпугивает – синтаксис не похож на привычные языки, а терминология в статьях изобилует такими словами, как “монады”, “категории”, “функторы”, “оптики” и “type-level программирование”.

Где вообще используют Haskell? Да много где, на Haskell пишется Backend, он используются для блокчейнов и компиляторов. Основными достоинствами Haskell являются: строгая статическая типизация, Haskell является type-safe языком, если код скомпилировался и не было использовано unsafe конструкций, что указывается явно, – run-time ошибок не будет. Чистая функциональность – это позволяет формальную верификацию программ и безопасность в многопоточности. Эти факторы заставляют выбирать Haskell там, где требуется надёжность.

Сложности
Здесь перед новичком встаёт барьер – работа со стандартным вводом/выводом какая-то странная. Учебники и туториалы предлагают играться с интерактивной средой, вместо написания полноценных рабочих программ, откладывая I/O подальше, а статьи сразу уводят в пучины, пугая ранее упомянутыми магическими заклинаниями.

Сложность ввода/вывода в Haskell обусловлена двумя вещами – чистые функции и ленивость – первое вынуждает создавать конструкции, изолирующие изменяющиеся состояния, второе делает невозможными предсказания о порядке выполнения операций чтения/записи. Как не странно, обе проблемы решаются конструкцией, называемой монады, разобраться с ними необходимо.

Монады в Haskell

Монады вдохновлены теорией категорий, про это написано множество лекций, но для примитивного понимания изучать сложный математический аппарат не придется. В Haskell монада – это typeclass. Давайте посмотрим на определение и разберёмся.

class Applicative m => Monad m where -- Bind оператор - передаёт содержимое монады в идущую далее функцию (>>=) :: forall a b. m a -> (a -> m b) -> m b -- Возвращает вторую монаду, дополняя контекстом первой (>>) :: forall a b. m a -> m b -> m b -- Стандартная реализация: используются bind и лямбда -- Аргумент лямбды игнорируется m >> k = m >>= \_ -> k -- Делает монаду из атомарного типа return :: a -> m a

Лирическое отступление, классы в Haskell больше похожи на интерфейсы в ООП, в Idris, близком родственнике Haskell, они так и называются. Чтобы тип начал принадлежать тайпклассу, для него требуется объявить заложенные в определение класса функции и константы, используя ключевое слово instance. Через “=” в определение класса описаны реализации по умолчанию.

Итак, ClassName m обозначает принадлежность типа m к классу ClassName. Перед Monad m стоит условное выражение – тип m не может быть монадой, если он не является Applicative, что это такое – не важно. Так строится иерархия классов. Далее, после where, идёт описание сигнатур: forall указывает, что объявляемые функции должны принимать аргументы любых типов, без учета специфики. Круглые скобки вокруг имени функции обозначают, что операция инфиксная, то есть ставится между своих аргументов. А :: просто соотносит имя с типом. В типах можно увидеть m a и m b, дело в том, что у любой монады род m :: * → * – это значит, что любая монада параметризована простым типом, походит на классические дженерики.

От рассмотрения невероятного синтаксиса вернёмся к поразительной семантике. Как я указал выше, монады позволяют решить и проблему изоляции стейта, и проблему ленивости – отсюда две распространённые аналогии: коробка и конвейерная лента. Значение помещается в контейнер, откуда не всегда может быть извлечено. Функции, работающие с этим контейнером, принимают на вход распакованное значение, с помощью операции bind (>>=), а возвращают новый контейнер с опасным аномальным объектом, нарушающем чистоту Haskell. Bind определяет последовательность применений этих операций, локально нарушая ленивость. Рассмотрим на примере:

-- Функция, для безопасного извлечения первого элемента списка safeHead :: [a] -> Maybe a -- На вход - список. На выходе контейнер Maybe - результат или Nothing. safeHead (first:_) = return first -- Если есть первый элемент - заворачиваем его в монаду Maybe. safeHead [] = Nothing -- Если первого элемента нет, то возвращаем ничего. -- Функция, безопасно извлекает первый элемент первого списка. innerSafeHead :: [[a]] -> Maybe a innerSafeHead lst = safeHead lst >>= safeHead -- Результат первого safeHead передаётся во второй. -- Если вернулся Nothing, вычисления обрываются.

Maybe – функциональный nullable, по совместительству являющейся монадой. В императивном языке пришлось бы делать явную проверку на null, тут же её проводит bind, возвращая Nothing, если он был получен на любом шаге вычислений. Ниже приведена реализация Maybe.

data Maybe a = Just a | Nothing -- Объявляется новый алгебраический тип - Maybe. -- Maybe параметризован произвольным типом a. -- Все возможные конструкторы "обитателей" типа описаны после знака "=".

instance Monad Maybe where -- Типу Maybe присваивается класс Monad. return a = Just a -- return оборачивает переменную конструктором Just. Nothing >>= _ = Nothing -- Если слева от оператора bind Nothing - вычисления обрываются. (Just a) >>= f = f a -- Если монада содержала значение - значение передаётся далее.

Через data объявляются алгебраические типы данных (они просто описывают структуру всех возможных представителей типа). Дальше идёт уточнение, как функционал класса будет работать с этими данными. Сопоставлением по шаблону перечисляются все возможные комбинации аргументов. Это не сложно, если вы пока не совсем понимаете, просто продолжайте читать.

Монады в Haskell очень распространены, поэтому для них существует специальный синтаксический сахар, очень напоминающий императивное программирование. Но важно помнить – это лишь сахар, Haskell не превращается в императивную тыкву с неконтролируемыми побочными эффектами вычислений. Вводится через ключевое слово do, поэтому упоминается как do-notation.

stuff :: State Int Int -- stuff - это монада типа State -- Хранит состояние и результат в Int stuff = do -- Объявление do-notation num1 <- get -- Переданное изначально состояние сохраняется в переменной num1 put $ num1 + 10 -- Сохраняется новое состояние, старое + 10 num2 <- get -- Оно записывается в новую переменную return $ num1 + num2 -- Возвращает сумму переменных как результат evalState stuff 10 -- evalState stuff возвращает функцию -- на вход подается начальное состояние -- возвращает результат выполнения (return)

Знак доллара ($) – это открывающаяся скобка, автоматически закрывающаяся на конце строки. Как видете, такой сахар сластит – код стало удобнее читать, а его псевдо-императивная суть сделалась явной. Следует помнить, do можно использовать к любой монаде, но главным образом он используется для монад, имитирующих внешнее состояние (Reader, Writer, State и IO). Теперь пора приступить непосредственно к IO.

Монады и I/O
Как и любая другая монада, IO параметризуется атомарным типом. Это тип результата работы IO процедуры, то есть тип считанного значения. Если последовательность I/O процедур обрывает процедура вывода, то параметризуемый тип () – Unit, тип с одним единственным значением, “обозначающий” отсутствие значения. Теперь мы готовы.

main :: IO () main = do putStrLn "What's your name?" name <- getLine putStrLn ("Hello, " ++ name ++ "!")

Hello name – хорошая программа для начала, но не слишком поражает. Давайте попробуем сделать игру “угадай число”.

guess :: Integer -> IO Integer guess num = do numGuessed <- getLine return $ num - read numGuessed answer :: Integer -> IO () answer n | n < 0 = putStrLn "Your number is too large!" | n > 0 = putStrLn "Your number is too small..." | otherwise = putStrLn "You've guessed!" main :: IO () main = do guess 12 >>= answer

Комбинаторные парсеры

Парсер своими руками
Работает, но игра завершается в любом случае. А если пользователь введёт не число, то read не сможет сосчитать значение. Давайте попробуем реализовать парсер, а попутно решим, как обойтись с циклом. Для создания парсера подойдёт уже упомянутые типы: State и Monad.

type Parser a = State String (Maybe a) -- Сокращение типа для парсера parseChar :: Parser Char parseChar = do str <- get -- Получаем строку case str of -- Сопоставляем с образцами (c:rest) -> do -- Если есть первый символ put rest -- остаток сохраняем в состояние

-- # Здесь была Революция

-- print(“Python лучше!\nСкачивайте RollerScanner!”) return $ Just c -- а первый символ возаращем otherwise -> return Nothing -- иначе возвращаем Nothing

Но это плохой подход. Во-первых, фактически в контейнере Maybe a, а не a – у нас не монада, комбинировать с помощью оператора bind не получится. Во-вторых, возникает много избыточных конструкций, например return $ Just c. Для подобных случаев существует StateT (State with monad Transformer) . Вот наш код, с использованием этого типа:

type Parser a = StateT String Maybe a parseChar :: Parser Char parseChar = do str <- get case str of (c:rest) -> do put rest return c -- делает то же самое, что и return $ Just c в прошлом коде otherwise -> lift Nothing -- "Поднимает" монаду Maybe a до State Maybe a parseCharOf :: String -> Parser String parseCharOf str = do c <- parseChar -- Помещает в c сразу же Char -- в старом коде было бы Maybe Char if elem c str then return [c] -- Если c есть в строке str, то возвращает [c] else lift Nothing -- В ином случае поднимает Nothing main = do print $ evalStateT (parseCharOf "12345") "abvf" -- Выводит Nothing print $ evalStateT (parseCharOf "12345") "123" -- Выводит Just “1”

Но встает другая проблема. Число может быть произвольной длины, чтобы вычленить его нам снова понадобится цикл, но в Haskell есть только рекурсия.

repeatP :: Monoid a => Parser Bool -> Parser a -> Parser a repeatP test p = do helper mempty -- Передает во вспомогательную функцию пустой аккумулятор where helper acc = do -- Определение вспомогательной функции b <- test -- Проверяет условие выхода if b then do val <- p -- Если истина, то совершает итерацию helper (acc <> val) --добавляет результат к аккумулятору else return acc -- Если ложь, возвращает аккумулятор

Тут нам встречается новый класс – Monoid. Моноиды очень простые, весь их интерфейс состоит из константы mempty и инфиксного оператора <>. В пример моноидам можно привести натуральные числа. 0 – это mempty, оператор сложения – <>. Если mempty участвует в операции, то он не изменяет значения другого аргумента. В нашей программе используется моноид String (memty = “”, <> = ++). Теперь нужны условия выхода.

end :: Parser Bool end = gets null

-- Проверяет, не нулевое ли состояние. notEnd :: Parser Bool notEnd = fmap not end

-- Применяет функцию not к результату монады

-- Возвращает новую монаду

Функция fmap пользуется тем, что, как мы указали выше, любая монада обязана быть функтором. В приложение к монадам, она применяет функцию к результату последнего выражения в цепочке. В отличие от операции bind, fmap принимает функцию, результат которой не завернут в монаду.

(>>=) :: forall a b . Monad m => m a -> (a -> m b) -> m b fmap :: Functor f => (a -> b) -> f a -> f b

Теперь мы готовы сделать полноценный guess a number. Число не будет случайным, но цикл и проверка данных будут.

digit :: Parser String digit = parseCharOf "0123456789" parseNumber :: Parser Integer parseNumber = fmap read $ repeatP notEnd digit -- Пытаемся считать цифры до конца строки -- Если получилось, получаем числовое значение

Для расширения функционала придется добавить пару комбинаторов.

errorP :: Parser a errorP = lift Nothing -- Обрывает парсинг ignore :: Parser String ignore = return "" -- Ничего не делает (|||) :: Parser a -> Parser a -> Parser a -- Комбинатор "если не, то" p ||| b = do inp <- get -- Получаем строку case (runStateT p inp) of -- Пытаемся спарсить первым парсером Just (result, rest) -> do -- В случае успеха put rest -- Остаток передаем дальше return result -- Результат возвращаем Nothing -> do -- Если ошибка put inp -- Загружаем исходную строку b -- И вызываем второй парсер p +++ b = do val <- p -- Получаем результат исполнения первого парсера val' <- b -- Получаем результат второго return (val <> val') --Возвращаем объединенный результат

Теперь мы можем сопоставить строку с грамматикой, заданной BNF. Добавим нашему парсеру возможность считывать отрицательные числа.

parseNumber = fmap read $ (parseCharEq '-' ||| ignore) +++ (repeatP notEnd digit)

Для игры осталось совсем немного. Проворачиваем такой же трюк с циклом:

until :: IO Bool -> IO () until m = do b <- m if b then return () else until m

Изменим guess, чтобы он научился парсить число.

guess num = do putStrLn "Your guess?" inpt <- getLine maybe -- maybe default f m -- Если m = Just x, f(x) -- Если m = Nothing, default (putStrLn "It's not a number!" >> guess num) -- В случае ошибки парсинга выводит сообщение (\ans -> return $ ans - num) -- Если было введено число, возвращает разницу с загаданным (runParser parseNumber inpt) -- Запускает парсер с пользовательской строкой

main процедура игры:

main :: IO () main = do putStrLn "You need to guess my number!" untill (guess 10 >>= answer)

Написанный парсер весьма неплох для валидаторов данных, но не годится для фактического парсинга, слишком уж костный StateT. Примером более совершенных комбинаторных парсеров является Parsec. Перепишем парсер целого неотрицательного числа.

Готовые библиотеки

number :: (Monad m) => ParsecT String u m Integer number = fmap read $ manyTill digit eof

Готовые библиотеки парсеров снабжают пользователя множеством готовых конструкций. Их принцип работы не сильно отличается от того, что написали мы, но они учитывают гораздо больше факторов. Например, в типе ParsecT описывается, что парсер будет получать на вход (в случае выше это String), к какому типу будет принадлежать результат выполнения (Integer), как мы будем хранить состояние (u) и даже, в контексте какой монады будет происходить парсинг (m), то есть, мы сможем использовать lift, подобно тому, как делали это в StateT.

На данный момент существуют три основные библиотеки:

parsec – медленная, но заточена под работу с пользовательским текстом, имеет хороший вывод ошибок;
attoparsec – заточена под обработку сетевых протоколов и бинарных файлов, намного быстрее parsec, но имеет худший вывод ошибок и работу с кодировками
megaparsec – улучшенная версия обычного parsec, больший функционал и работает быстрее.

Заключение
Мы успели рассмотреть достаточно много, для написания простых консольных программ этого вполне достаточно. IO монада, тем не менее, не идеальный вариант. Существуют лучшие реализации для стриминговых данных, а история, как докатилось до такого, интересна сама по себе. К сожалению, в этой статье не удастся рассмотреть I/O в достаточной полноте. Во второй части мы рассмотрим такой подход, как Iteratee и используем attoparsec на практике.

Подходы к вводу/выводу в Haskell. Часть 1

Авторизация