Академия: Введение в функциональное программирование. 8 неделя, ч.1: функциональные парсеры (и немного монад)

Привет. Я участвую в проекте Академия от @ontofractal и публикую конспекты курса  Введение в функциональное программирование от Delft University of Technology. Как уже говорилось в предыдущей части, мы закончили разбирать отдельные строительные блоки, из которых состоят программы на Хаскеле и теперь учимся составлять их в полноценные скрипты. В прошлой части рассказ шел о том, как комбинировать отдельные функции с помощью функций высшего порядка, а сегодня попробуем написать простой парсер

Функциональные парсеры

Для тех, кто не знаком с понятием, сообщаю, что парсер - это программа, получащая кусок текста и анализирующая его синтаксическую структуру. С их помощью можно делать множество удивительных вещей, вплоть до анализа структуры предложений в человеческих языках. Но мы, конечно, не будем забираться столь глубоко и ограничимся написанием простейших парсеров

Примерная схема работы парсера

Типы парсеров

При написании функций на Хаскеле значительную часть работы можно сделать в одночасье, хорошо подумав о типах. Поэтому, прежде чем писать сами функции, нужно определиться с типом парсера

Как видно из приведенной выше иллюстрации, парсер описывает синтаксическую структуру строки при помощи дерева, поэтому тип парсера может выглядеть так:

type Parser = String -> Tree

Однако, в процессе работы нередко оказывается, что не все подстроки нужны с ходе работы парсера. Поэтому сразу перепишу тип с учетом такой возможности:

type Parser = String -> (Tree, String)

String в итоговой паре - это как раз подстроки, которые не подверглись анализу

Также, парсер может выдавать несколько результатов сразу, поэтому будет лучше, если он начнет возвращать не одну пару, а список из неограниченного числа пар:

type Parser = String -> [(Tree, String)]

Наконец, результат анализа не обязательно возвращать в виде дерева, поэтому можно сделать функцию параметризированной, то есть, заменим конкретный тип Tree на переменную типа а

Первый парсер

Разобравшись с типами, можно наконец перейти к написанию первых парсеров. Для начала напишу функцию, принимающую строку и возвращающую пару, состоящую из первого символа и остатка строки:

type Parser a = String -> [(a, String)]

item :: Parser Char

item = \inp -> case inp of

[] -> []

(x:xs) -> [(x, xs)]

Запусаем GHCi и тестируем:

Отлично. Теперь было бы любопытно написать парсеры, всегда возвращающие успешный и неуспешный результат:

failure :: Parser a

failure = \inp -> []

return' :: a -> Parser a

return' v = \inp -> [(v, inp)]

Первая функция всегда возвращает пустой список (забыл упомянуть, но пустые списки я буду использовать как результат неудачных вычислений), вторая всегда возвращает переданное ей значение, не обращая внимания на строку, которую мы хотим обработать. Пока что оба варианта выглядят бесполезными, но кто знает, быть может позже удастся приспособить их к чему-нибудь нужному

Еще одна полезная функция, которую можно написать, принимает два парсера и строку, и если анализ с помощью первого парсера окончился неудачей, передает строку второму парсеру

(+++) :: Parser a -> Parser a -> Parser a

p +++ q = \inp -> case p inp of

[] -> parse q inp

[(v, out)] -> [(v, out)]

Наконец, можно написать функцию, применяющую парсер к заданной строке:

parse :: Parser a -> String -> [(a, String)]

parse p inp = p inp

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

Например, мы можем захотеть не скомбинировать два парсера, а построить более сложную композицию, которая будет последовательно обрабатывать входное значение. В этом нам поможет конструкция do:

p :: Parser (Char, Char)

p = do x <- item

	item

	y <- item

	return (x, y)

Что делает этот код? Первая строка говорит "возьми некое значение item, обработай его и верни х". Вторая строка тоже говорит, что нужно обработать item и вернуть некое значение. Для нас оно не важно, поэтому никак не будем его называть. Третья строка привязывает результат обработки item к переменной у. Наконец, последняя строка берет получившиеся значения х и у и возвращает пару, включающую эти значения

Таким образом, do позволяет нам взять несколько действий, расположить их последовательно и создать таким образом единую конструкцию. Звучит довольно просто, но на самом деле в этом паттерне скрывается большая выразительная сила

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

М - значит молчание

Многие концепции, используемые в ФП, кажутся чем-то сложным и малопонятным, но даже среди них монады занимают особное положение. Многие начинающие программисты, пытающихся освоить премудрости ФП, сходятся во мнении, что монады - это некая эзотерическая область знания, и их мнение во многом обосновано. Все дело в том, что монады обладают весьма необычным свойством - сами по себе они являют довольно простую концепцию, понятную каждому (взять несколько выражений и составить из них общую цепочку вычислений), но когда кто-либо пытается разобраться в этой теме и называет монады по имени, он ничего не может понять. Чтобы эта магия была более понятной, опишу все это на конкретном примере

Красивые обещания

Disclaimer: все описанное в этом разделе не относится к содержанию курса и является личным видением автора конспекта. Если вы сомневаетесь в компетентности автора и хотите получить знания из авторитетного источника, вам стоит пролистнуть этот раздел

В мире Яваскрипта есть аналог описанной выше ситуации. В этом языке есть вид объектов, называемый промисы и позволяющий очень просто устроить работу с асинхронными вызовами 

При работе с Яваскриптом есть потребность в написании большого количества асинхронного кода, иначе обработка скриптов будет блокировать загрузку интерфейса. Однако, долгое время  единственным способом создать подобные вызовы было написание коллбек-функций. Главной проблемой при использовании таких функций было то, что при выполнении цепочки асинхронных запросов, требовалось написать большое количество вложенных функций, в которых зачасту было очень сложно ориентироваться. Например, представим, что нужно написать скрипт, берущий с сервера данные о пользователе, потом берущий с сервера его посты, затем извлекающий данные о людях, комментировавших эти посты, а затем собирающий список их подписчиков. При использовании коллбек-функций скрипт будет выглядеть как длинная цепочка вложенных вызовов: 

fetchUser(user, function(err, res) {

   fetchPosts(res.posts, function(err, res) {

      fetchComments(res.authors, function(err, res) {

         fetchFollowers(res, function(err, res) {

            etc...

         }

      }

   }

}

Согласитесь, что выглядит это просто ужасно. Причем, в реальных примерах уровней вложенности может быть еще больше, и в какой-то момент подобный скрипт может стать практически нечитабельным. В какой-то момент коллбек-функции так надоели яваскрипт-программистам, что код с их использованием стали называть Callback Hell

Все изменилось с приходом промисов. Благодаря ним даже длинную цепочку вызовов можно оформить в виде одноуровневой структуры:

fetchUser(user)

   .then(res => {

      ...

      return fetchPost(res.posts) //

   }

   .then(posts => {

      ...

      return fetchComments(res.authors)

   }

   .then(res => {

      ...

      return fetchFollowers(res.names)

   }

Однако, несмотря на простоту устройства, за промисами тоже закрепилась слава сложной темы, которую можно понять далеко не с первого раза. Из-за подобной репутации немалое число программистов в свое вреся боялось перейти на промисы и продолжало мучиться с коллбек-функциями

Кстати, заметили сходство? И в функциональном парсере, и в примере с промисами суть происходящего сводится к просто формуле: взять исходное значение и последовательно обработать, передавая от функции к функции. И действительно, промисы - это те же монады, только из мира JS

Заключение

Подведем итоги. Монада - не что иное, как функциональный паттерн, используемый при композиции функций. Благодаря нему многие сложные действия можно описать при помощи одноуровневой цепочки последовательных преобразований 

Монады получили широкое применение в функциональном программировании (а также за его пределами, как мы могли видеть в примере с промисами), поэтому в своих конспектах я буду неоднократно возвращаться к этой теме, и расскажу впоследствии, какие еще преимущества несет в себе эта техника

На этом я предлагаю закончить восьмую конспекта. В следующей части я продолжу разбирать  восьмую неделю курса и продолжу строить функциональные парсеры

Что показалось самым интересным на этой неделе

Больше всего мне понравились две вещи: то, что повествование перешло от теории к практике, и то, что в этой части курса так изящно объясняются вещи, кажущиеся на первый взгляд сложными и запутанными. Подобнoе качествo нечасто встречаются в обучающих курсах и литературе, поэтому всем, кто интересуется функциональным программированием, я рекомендую присмотреться к курсу FP101

“Конспект подготовлен для Академии Голоса @academy”.