Аппликативное программирование или как парсить SQL на чистом Haskell

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

Первая часть доклада — про основы синтаксиса Haskell. Во второй части — поговорим про функторы, из которых мы будем собирать нашу программу. В финале — мы сделаем парсер общего назначения в аппликативном стиле и научим его разбирать небольшое подмножество языка SQL.

Transcript

1. Аппликативное программирование или Как парсить SQL на чистом Haskell Дмитрий Цепелев
2. DmitryTsepelev 🌆 2 @dmitrytsepelev 🌎 dmitrytsepelev.dev
3. DmitryTsepelev 🌆 Зачем это все? • ФП — это весело; • многие штуки доезжают из ФП в модные языки через 10-30 лет, можно заглянуть в будущее 🔮; • есть свои сложности и интересные способы их решать (спросите меня про линзы!); • некоторые вещи значительно проще, чем в ООП; • сам Haskell простой как 🚪, сложные концепции надстраиваются (одну штуку мы увидим прямо сейчас!). 3
4. Haskell 101
5. DmitryTsepelev 🌆 Типы 5 Int - - целое число String - - строка type IntList = [Int] - - список type String = [Char] - - строки это списки букв (Int, Int) - - пара
6. DmitryTsepelev 🌆 Функции • все функции чистые; • состояние не мутируется; • функция принимает 0 или более аргументов и возвращает одно значение; • могут вызываться в инфиксной форме с помощью ``. 6 sum : : Int - > Int - > Int sum x y = x + y sum 3 6 - - 9 3 `sum` 6 - - 9
7. DmitryTsepelev 🌆 Функции: инфиксная форма • in fi x делает функцию инфиксной по умолчанию; • первый аргумент — приоритет функции; • могут вызываться в инфиксной форме с помощью (). 7 sum : : Int - > Int - > Int sum x y = x + y inf i x 6 /\/\ (/\/\) = sum 1 /\/\ 2 - - 3 (/\/\) 1 2 - - 3
8. DmitryTsepelev 🌆 Изменение приоритета операций: $ • выполняется сначала правая часть, затем левая; • позволяет избавиться от лишних скобок; • не является частью синтаксиса языка. 8 show 1 + 1 - - No instance for (Num String) arising from a use of + show (1 + 1) - - 2 inf i xr 0 $ ($) : : (a - > b) - > a - > b f $ x = f x show $ 1 + 1 - - 2
9. DmitryTsepelev 🌆 Частичное применение функции • можно считать, что функция всегда принимает и возвращает один аргумент; • если аргументов больше — вернется новая функция; • такая операция называется каррированием. 9 sum : : Int - > (Int - > Int) sum x y = x + y sum3 : : Int - > Int sum3 = sum 3 sum3 6 - - 9
10. DmitryTsepelev 🌆 Композиция • функция . (точка) позволяет из двух функций создать одну, вызывающую обе по очереди; • можно убрать немного скобок. 10 inf i xr 9 . (.) : : (b - > c) - > (a - > b) - > a - > c (.) f g a = f (g a) succ . (*2) $ 3 - - 7
11. DmitryTsepelev 🌆 Алгебраические типы умножение (product/И): тип, состоящий из нескольких других типов 11 data User = User String String User "john.doe@example.com" "Jonh Doe" сложение (sum/ИЛИ): тип, который может принимать значения разных типов data UserType = Admin | User | Guest
12. DmitryTsepelev 🌆 Алиасы типов • для читабельности можно создать алиасы (Email, Name); • можно явно указать названия в сигнатуре чтобы сгенерировать функции. 12 type Email = String type Name = String data User = User Email Name User "john.doe@example.com" "Jonh Doe" data User2 = User { email : : String, name : : String }
13. DmitryTsepelev 🌆 Параметризованные типы • параметризованный тип может содержать значение произвольного типа; • на тип можно накладывать ограничения; • Just в примере ниже — конструктор. 13 data Maybe a = Just a | Nothing Just 3
14. DmitryTsepelev 🌆 Pattern matching и guard conditions • можно проверять тип значения и разбирать его в теле функции; • можно использовать guard conditions чтобы проверять более сложные условия. 14 sayHi : : Maybe String - > String sayHi (Just name) = "Hi, " + + name + + "!" sayHi Nothing = "Hi!" sayHi mName | isJust mName = "Hi, " + + (fromJust name) + + "!" | otherwise = "Hi!"
15. DmitryTsepelev 🌆 Классы типов • аналог интерфейсов в ООП; • содержит функции, которые должен реализовывать тип, который реализует данный класс типов; • может содержать реализации по умолчанию. 15 class Num a where (+), (-), (*) : : a - > a - > a negate : : a - > a abs : : a - > a signum : : a - > a fromInteger : : Integer - > a x - y = x + negate y negate x = 0 - x
16. DmitryTsepelev 🌆 Реализация классов типов • нужно объявить все обязательные методы; • если класс типов содержит минимальную реализацию, то его можно объявить в сокращенной форме. 16 instance Num Integer where (+) = integerAdd (-) = integerSub (*) = integerMul negate = integerNegate fromInteger i = i abs = integerAbs signum = integerSignum data User = User { email : : String } deriving (Show) User "john.doe@example.com" - - User {email = "john.doe@example.com"}
17. DmitryTsepelev 🌆 Более гибкие функции • вместо конкретных типов можно использовать переменные–типы (type variables); • при вызове будут использованы конкретные типы; • для того, чтобы ограничить подходящие типы, можно использовать классы типов (перед = > ). 17 sum : : Num a = > a - > a - > a sum x y = x + y sum 3 6 - - 9
18. Функторы и аппликативные функторы
19. DmitryTsepelev 🌆 Работа со значением в коробке 19 type UserID = Int type Email = String data Maybe a = Just a | Nothing deriving (Show) getEmail : : UserID - > Maybe Email getEmail 42 = Just "john.doe@example.com" getEmail _ = Nothing formatEmail : : Maybe Email - > Maybe Email formatEmail (Just email) = Just $ "Email: " + + email formatEmail Nothing = Nothing formatEmail $ getEmail 42 - - Just "Email: john.doe@example.com"
20. DmitryTsepelev 🌆 Класс типов Functor 20 class Functor f where fmap : : (a - > b) - > f a - > f b • преобразовывает значение в коробке с учетом типа коробки.
21. DmitryTsepelev 🌆 Реализация Functor для Maybe 21 data Maybe a = Just a | Nothing deriving (Show) instance Functor Maybe where fmap f (Just x) = Just (f x) fmap f Nothing = Nothing type UserID = Int type Email = String getEmail : : UserID - > Maybe Email getEmail 42 = Just "john.doe@example.com" getEmail _ = Nothing formatEmail : : Maybe Email - > Maybe Email formatEmail = fmap (\email - > "Email: " + + email) • если значение Just — происходит распаковка, применение функции и запаковка; • Nothing остается без изменений.
22. DmitryTsepelev 🌆 <$> — инфиксный fmap 22 data Maybe a = Just a | Nothing deriving (Show) instance Functor Maybe where fmap f (Just x) = Just (f x) fmap f Nothing = Nothing inf i x 4 < $ > ( < $ > ) = fmap type UserID = Int type Email = String getEmail : : UserID - > Maybe Email getEmail 42 = Just "john.doe@example.com" getEmail _ = Nothing formatEmail : : Maybe Email - > Maybe Email formatEmail maybeEmail = ("Email: " + + ) < $ > maybeEmail
23. DmitryTsepelev 🌆 Реализация Functor для пары 23 • у пары есть семантика; • функция применяется ко второму элементу. instance Functor ((,) a) where fmap f (x,y) = (x, f y)
24. DmitryTsepelev 🌆 Реализация Functor для списка 24
25. DmitryTsepelev 🌆 Аппликативные функторы • fmap принимает функцию с одним аргументом; • у нас есть каррирование, поэтому все функции подходят; • что будет, если передать функцию с двумя аргументами? 25 (+1) < $ > Just 42 - - Just 43 (+) < $ > Just 42 - - Just (42 +)
26. DmitryTsepelev 🌆 Класс типов Applicative • теперь мы можем упороться и применить функцию в коробке к значению в коробке; • pure заворачивает значение в минимально простой контейнер; • < * > достает значение из коробки слева и применяет к значению в коробке справа, затем кладет всё в исходную коробку (если сможет!). 26 class (Functor f) = > Applicative f where pure : : a - > f a ( < * > ) : : f (a - > b) - > f a - > f b
27. DmitryTsepelev 🌆 Реализация Applicative Functor для Maybe 27 data Maybe a = Just a | Nothing deriving (Show) instance Functor Maybe where fmap f (Just x) = Just (f x) fmap f Nothing = Nothing inf i xl 4 < $ > ( < $ > ) = fmap instance Applicative Maybe where pure = Just Nothing < * > _ = Nothing (Just f) < * > something = f < $ > something formatEmail : : Maybe Email - > Maybe Email formatEmail maybeEmail = pure ( + + ) < * > maybeEmail < * > Just "Email: " • pure — кладет значение в Just; • <*> вернет Nothing если Nothing будет слева либо справа; • иначе — обычный fmap.
28. DmitryTsepelev 🌆 Каррирование в аппликативном стиле • можно создавать функции, работающие только с «хорошим сценарием»; • плохой сценарий будет обработан реализацией аппликативного функтора для используемого типа. 28 sum3 : : Num n = > n - > n - > n - > n sum3 x y z = x + y + z pure sum3 < * > Just 3 < * > Just 2 < * > Just 4 - - Just 9 pure sum3 < * > Just 3 < * > Nothing < * > Just 4 - - Nothing
29. DmitryTsepelev 🌆 *> <* • класс типов Applicative содержит дополнительные операции, которые могут быть выведены из <*>; • *> выполняет операцию, но игнорирует значение левого аргумента; • <* выполняет операцию, но игнорирует значение правого аргумента. 29 pure (42+) * > Just 2 - - Just 2 pure (42+) * > Nothing - - Nothing Nothing * > Just 2 - - Nothing pure (42+) < * Just 2 - - Just (42+) Nothing < * Just 2 - - Nothing pure (42+) < * Nothing - - Just (42+)
30. Аппликативный парсер за 15 минут
31. DmitryTsepelev 🌆 Простейший парсер 31 data Parser a = Parser { parse : : String - > Either String (String, a) } satisfy : : (Char - > Bool) - > Parser Char satisfy pr = Parser f where f "" = Left "unexpected end of input" f (c:cs) = if pr c then Right (cs, c) else Left ("unexpected " + + [c]) anyChar : : Parser Char anyChar = satisfy (const True) parse anyChar "ABC" - - Right ("BC",'A')
32. DmitryTsepelev 🌆 Простейший парсер 32 import Data.List (isPref i xOf) data Parser a = Parser { parse : : String - > Either String (String, a) } char : : Char - > Parser Char char p = satisfy ( = = p) parse (char 'A') "ABC" - - Right ("BC",'A') parse (char 'B') "ABC" - - Left "unexpected A” string : : String - > Parser String string str = Parser f where f s | str `isPref i xOf` s = Right (drop (length str) s, str) | otherwise = Left $ "unexpected " + + s + + ", expected " + + str parse (string "AB") "ABC" - - Right ("C","AB")
33. DmitryTsepelev 🌆 Реализуем функтор 33 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Functor Parser where fmap f (Parser p) = Parser $ fmap (fmap f) . p parse (toLower < $ > char 'A') "ABC" - - Right ("BC",'a')
34. DmitryTsepelev 🌆 Реализуем аппликацию 34 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Applicative Parser where pure a = Parser $ \s - > Right (s, a) pf < * > pv = Parser $ \s - > case parse pf s of Right (s', g) - > case parse pv s' of Right (s'', a) - > Right (s'', g a) Left e - > Left e Left e - > Left e
35. DmitryTsepelev 🌆 Реализуем аппликацию 35 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Applicative Parser where pure a = Parser $ \s - > Right (s, a) pf < * > pv = Parser $ \s - > case parse pf s of Right (s', g) - > case parse pv s' of Right (s'', a) - > Right (s'', g a) Left e - > Left e Left e - > Left e
36. DmitryTsepelev 🌆 Реализуем аппликацию 36 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Applicative Parser where pure a = Parser $ \s - > Right (s, a) pf < * > pv = Parser $ \s - > case parse pf s of Right (s', g) - > case parse pv s' of Right (s'', a) - > Right (s'', g a) Left e - > Left e Left e - > Left e
37. DmitryTsepelev 🌆 Реализуем аппликацию 37 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Applicative Parser where pure a = Parser $ \s - > Right (s, a) pf < * > pv = Parser $ \s - > case parse pf s of Right (s', g) - > case parse pv s' of Right (s'', a) - > Right (s'', g a) Left e - > Left e Left e - > Left e
38. DmitryTsepelev 🌆 Реализуем аппликацию 38 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Applicative Parser where pure a = Parser $ \s - > Right (s, a) pf < * > pv = Parser $ \s - > case parse pf s of Right (s', g) - > case parse pv s' of Right (s'', a) - > Right (s'', g a) Left e - > Left e Left e - > Left e
39. DmitryTsepelev 🌆 Реализуем аппликацию 39 parse (pure ( : ) < * > char 'A' < * > string "BC") "ABC" - - Right ("","ABC") parse (char 'A' * > string "BC") "ABC" - - Right ("","BC") parse (char 'A' < * string "BC") "ABC" - - Right ("",'A')
40. DmitryTsepelev 🌆 Класс типов Alternative 40 import Control.Applicative hiding (many) import Data.Either (isRight) data Parser a = Parser { parse : : String - > Either String (String, a) } instance Alternative Parser where empty = Parser $ \s - > Left $ "unexpected " + + s p < | > q = Parser f where f s = let ps = parse p s in if isRight ps then ps else parse q s parse (char 'A' < | > char 'B') "AB" - - Right ("B",'A') parse (char 'A' < | > char 'B') "BA" - - Right ("A",'B')
41. DmitryTsepelev 🌆 Комбинаторы 41 import Control.Applicative hiding (many) import Data.Either (isRight) data Parser a = Parser { parse : : String - > Either String (String, a) } instance Alternative Parser where empty = Parser $ \s - > Left $ "unexpected " + + s p < | > q = Parser f where f s = let ps = parse p s in if isRight ps then ps else parse q s many : : Parser a - > Parser [a] many p = pure ( : ) < * > p < * > many p < | > pure [] parse (many (char 'A')) "AAABC" - - Right ("BC","AAA") parse (many (char 'A')) "BC" - - Right ("BC","") many1 : : Parser a - > Parser [a] many1 p = pure ( : ) < * > p < * > many p parse (many1 (char 'A')) "AAABC" - - Right ("BC","AAA") parse (many1 (char 'A')) "BC" - - Left "unexpected B"
42. DmitryTsepelev 🌆 SQL: select 42 whitespace : : Parser String whitespace = many (char ' ') sepBy : : Parser a - > Parser sep - > Parser [a] sepBy p sep = pure (flip ( : )) < $ > many (p < * sep) < * > p alphaNum : : Parser Char alphaNum = satisfy isAlphaNum tableNameP : : Parser String tableNameP = many1 (alphaNum < | > char '.') selectP : : Parser [String] selectP = string "select" * > whitespace * > (tableNameP `sepBy` (char ',' < * whitespace)) parse selectP "select movies.id, movies.title" - - Right ("",["movies.title","movies.id"])
43. DmitryTsepelev 🌆 SQL: from 43 fromP : : Parser String fromP = whitespace * > string "from" * > whitespace * > many1 alphaNum parse fromP "from movies" - - Right ("","movies")
44. DmitryTsepelev 🌆 SQL: join 44 data Join = Join String String String deriving (Show) joinP : : Parser Join joinP = Join < $ > (whitespace * > string "join" * > whitespace * > many1 alphaNum < * whitespace) < * > (string "on" * > whitespace * > tableNameP < * whitespace) < * > (char '=' * > whitespace * > tableNameP) parse joinP "join directors on movies.directorId = directors.id” - - Right ("",Join "directors" "movies.directorId" "directors.id")
45. DmitryTsepelev 🌆 SQL: joins 45 data Join = Join String String String deriving (Show) optionMaybe : : Parser a - > Parser (Maybe a) optionMaybe p = Parser $ \s - > let ps = parse p s in case ps of Right (s', a) - > if s' / = s then Right (s', Just a) else Right (s', Nothing) Left _ - > Right (s, Nothing) joinsP : : Parser (Maybe [Join]) joinsP = whitespace * > optionMaybe (many joinP)
46. DmitryTsepelev 🌆 SQL: joins 46 let query = "join directors on movies.directorId = directors.id join moviesActors on moviesActors.movieId = moviesId" parse joinsP query - - Right ("",Just [Join "directors" "movies.directorId" "directors.id",Join "moviesActors" "moviesActors.movieId" "moviesId"]) parse joinsP "" - - Right ("",Nothing)
47. DmitryTsepelev 🌆 SQL 47 runParser : : Parser a - > String - > a runParser p s | Right ("", a) < - parse p s = a | otherwise = error "failed to run parser" data Query = Query { selection : : [String], from : : String, joins : : Maybe [Join] } deriving (Show) sqlP : : Parser Query sqlP = Query < $ > selectP < * > fromP < * > joinsP runParser sqlP "select movies.title, movies.createdAt from movies join directors on directors.id = movies.directorId" - - Query {selection = ["movies.createdAt","movies.title"], from = "movies", joins = Just [Join "directors" "directors.id" "movies.directorId"]}
48. DmitryTsepelev 🌆 Выводы • ФП — это весело (да?); • все используют функторы; • с помощью хитрых операций с функциями можно получать интересное поведение; • аппликативные функторы позволяют выстраивать цепочки вычислений без обработки ошибок в процессе. 48
49. DmitryTsepelev 🌆 Куда пойти дальше • Learn You a Haskell (http:/ /learnyouahaskell.com); • Функциональное программирование на языке Haskell (https:/ / stepik.org/course/75/syllabus). 49
50. Спасибо! @dmitrytsepelev 🌎 dmitrytsepelev.dev
51. Спасибо! @dmitrytsepelev 🌎 dmitrytsepelev.dev Надо что–то спросить 🤔 • что там за эмоджи слева сверху было? 🌇 • покажи фокус с долларом • почему реализация Applicative для парсера была страшная, как смерть водолаза? • а что там про монады было? • а правда ли что главное чтобы типы сошлись?
52. DmitryTsepelev 🌆 Фокус с долларом 52 zip [1, 3] [2, 4] - - [[1, 2], [3, 4]] zipWith (+) [1, 3] [2, 4] - - [4, 6] [(+4), (*5)] [3, 7] как вызвать функции из массива слева с аргументом справа? sum $ zipWith ($) [(+4), (*5)] [3, 7] - - 42 sum [(+4) $ 3, (*5) $ 7]
53. DmitryTsepelev 🌆 Реализуем аппликацию 53 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Applicative Parser where pure a = Parser $ \s - > Right (s, a) pf < * > pv = Parser $ \s - > case parse pf s of Right (s', g) - > case parse pv s' of Right (s'', a) - > Right (s'', g a) Left e - > Left e Left e - > Left e
54. DmitryTsepelev 🌆 Applicative Parser на монадах: bind 54 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Applicative Parser where pure a = Parser $ \s - > Right (s, a) pf < * > pv = Parser $ \s - > parse pf s > > = \(s', g) - > parse pv s' > > = \(s'', a) - > Right (s'', g a)
55. DmitryTsepelev 🌆 Applicative Parser на монадах: do–нотация 55 data Parser a = Parser { parse : : String - > Either String (String, a) } instance Applicative Parser where pure a = Parser $ \s - > Right (s, a) pf < * > pv = Parser $ \s - > do (s', g) < - parse pf s (s'', a) < - parse pv s' return (s'', g a)
56. DmitryTsepelev 🌆 many вообще не зависит от наших парсеров! 56 many : : Parser a - > Parser [a] many p = ( : ) < $ > p < * > many p < | > pure []
57. DmitryTsepelev 🌆 many вообще не зависит от наших парсеров! 57 many : : Alternative t = > t a - > t [a] many p = ( : ) < $ > p < * > many p < | > pure []
58. DmitryTsepelev 🌆 Магия типов: pure f <*> g == f <$> g 58 pure ( : ) < * > char 'A' ( : ) : : a - > [a] - > [a] pure : : a - > Parser a pure : : Char - > Parser a Parser (Char - > [Char] - > [Char]) < * > Parser Char ( < * > ) : : Parser (a - > b) - > Parser a - > Parser b ( < * > ) : : Parser (Char - > [Char]) - > Parser Char - > Parser [Char] Parser ([Char] - > [Char]) fmap : : (a - > b) - > Parser a - > Parser b fmap : : (Char - > [Char]) - > Parser Char - > Parser [Char] (Char - > [Char] - > [Char]) < $ > Parser Char Parser ([Char] - > [Char]) ( : ) < $ > char 'A'