Аппликативные парсеры на Haskell

  • Tutorial


Мотивация


Когда я только начинала осваивать Haskell, меня очень раздражало повсеместное использование сложных абстракций вместо каких-то конкретных решений. Мне казалось, что гораздо лучше всегда следовать принципу KISS и писать велосипеды с использованием элементарных конструкций языка, чем разбираться во всех этих классах типов, чтобы где-то в итоге написать одну якобы удобную конструкцию.


Мне не хватало хорошего примера, где бы окупались усилия, потраченные на освоение "матчасти". Для меня одним из самых удачных таких примеров оказались парсеры. Теперь я довольно часто рассказываю про них, когда у меня спрашивают, для каких распространённых задач можно красиво использовать Haskell.


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


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


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


Для тех, кто на Haskell никогда не писал, но хочет понять, что здесь происходит, рекомендую сначала посмотреть на соответствующую страницу на Learn X in Y minutes. В качестве отличной русскоязычной книги для начинающих советую "О Haskell по-человечески" Дениса Шевченко.


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


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


Классы типов


Классы типов в Haskell не имеют ничего общего с классами в С++ и прочих объектно-ориентированных языках. Если проводить аналогию с ООП, то классы типов скорее напоминают перегрузку методов и функций.


Классы определяют, какие действия можно совершать с объектами тех типов, которые входят в класс. Например, все числа можно сравнивать на равенство, но упорядочить можно все, кроме комплексных, а функции в общем случае сравнить вообще нельзя. Класс типов, которые можно сравнивать, называется Eq, упорядочить — Ord (типы не обязательно должны быть числовыми). То, что можно напечатать, переведя в строку, принадлежит к классу Show, у него есть "противоположенный" класс Read, который определяет, как преобразовывать строки в объекты нужного типа.


Для набора стандартных классов типов (таких как Eq, Show, Read ...) можно попросить компилятор реализовать нужный функционал стандартным образом, используя ключевое слово deriving после определения типа:


data Point = Point
    { xCoord :: Float
    , yCoord :: Float
    } deriving (Eq, Show)

Можно определять свои классы типов:


class PrettyPrint a where
  pPrint :: a -> String

Здесь PrettyPrint — имя класса, a — переменная типа. После ключевого слова where следует список так называемых методов класса, т.е. функций, которые могут быть применены к объектам, имеющим тип из этого класса.


Для того, чтобы обозначить принадлежность типа данных к классу, используется следующая конструкция:


instance PrettyPrint Point where
  pPrint (Point x y) = "(" ++ show x ++ ", " ++ show y ++ ")"

Язык позволяет указывать ограничения на классы типов, к которым должны относиться аргументы функции:


showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String)
showVsPretty x = (show x, pPrint x)

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


>>> showVsPretty (Point 2 3)
("Point {xCoord = 2.0, yCoord = 3.0}","(2.0, 3.0)")

>>> showVsPretty "str"
error:
    No instance for (PrettyPrint [Char]) arising from a use of ‘showVsPretty’

Реализация


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


Для описания одного результата работы парсера подойдёт кортеж из двух элементов (String, a), где a — переменная типа, которая может обозначать любой пользовательский тип.


Поскольку парсер разбирает строку по каким-то правилам, опишем его как функцию, принимающую на вход строку и возвращающую список результатов:


newtype Parser a = Parser { unParser :: String -> [(String, a)] }

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


parseString :: String -> Parser a -> Maybe a
parseString s (Parser p) = case (p s) of
    [("", val)] -> Just val
    _           -> Nothing

Простейшие парсеры


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


Начнём с разбора одного символа, который должен удовлетворять предикату. Если входная строка пуста, то и результатом работы является пустой список. В противном случае проверяем значение предиката на первом символе строки. Если вернулось значение True, то результатом разбора является этот символ; возвращаем его вместе с остатком строки. В противном случае разбор также оканчивается неудачей.


predP :: (Char -> Bool) -> Parser Char
predP p = Parser f
  where
    f "" = []
    f (c : cs) | p c = [(cs, c)]
               | otherwise = []

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


charP :: Char -> Parser Char
charP char = predP (\c -> c == char)

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


stringP :: String -> Parser String
stringP s = Parser f
  where
    f s' | s == s' = [("", s)]
         | otherwise = []

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


skip :: (Char -> Bool) -> Parser ()
skip p = Parser (\s -> [(dropWhile p s, ())])

Следующие два парсера очень похожи друг на друга. Оба проверяют префикс входной строки, только первый в случае успеха возвращает этот префикс, а второй — пустой кортеж, т.е. позволяет пропустить произвольную строку в начале входа. Для реализации используется функция isPrefixOf, определённая в модуле Data.List.


prefixP :: String -> Parser String
prefixP s = Parser f
  where
    f input = if s `isPrefixOf` input
                then [(drop (length s) input, s)]
                else []

skipString :: String -> Parser ()
skipString s = Parser f
  where
    f input = if s `isPrefixOf` input
                then [(drop (length s) input, ())]
                else []

Чуть позже мы рассмотрим более простую реализацию последней функции и избавимся от дублирования кода.


Парсер как функтор


Можно выделить целый класс типов-контейнеров, для которых верно следующее: если известно, как преобразовывать объекты внутри контейнера, то можно преобразовывать и сами контейнеры. Простейший пример — список в качестве контейнера и функция map, которая есть практически во всех высокоуровневых языках. Действительно, можно пройтись по всем элементам списка типа [a], применить к каждому функцию a -> b и получить список типа [b].


Такой класс типов называется Functor, у класса есть один метод fmap:


class Functor f where
  fmap :: (a -> b) -> f a -> f b

Предположим, что мы уже умеем разбирать строки в объекты некоторого типа a, и, кроме того, знаем, как преобразовать объекты типа a в объекты типа b. Можно ли сказать, что тогда есть парсер для объектов типа b?


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


(a -> b) -> Parser a -> Parser b

Этот тип совпадает с типом функции fmap, поэтому попробуем сделать парсер функтором. Создадим с нуля парсер значений типа b, который будет сначала вызывать первый парсер (он у нас уже есть), а затем применять функцию к результатам его разбора.


instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap f (Parser p1) = Parser p2
    where
      p2 :: String -> [(String, b)]
      p2 s = convert (p1 s)
      convert :: [(String, a)] -> [(String, b)]
      convert results = map (\(s, val) -> (s, f val)) results

У функции fmap есть удобный инфиксный синоним: fmap f x == f <$> x.


Если в качестве аргумента fmap использовать функцию, просто заменяющую свой первый аргумент на новое значение, то получим ещё одну полезную операцию, которая уже реализована для всех функторов даже в двух экземплярах (они отличаются только порядком аргументов):


(<$) :: Functor f => a -> f b -> f a
($>) :: Functor f => f a -> b -> f b

Помните парсер, который пропускает определённую строку (skipString)? Теперь можно его реализовать следующим образом:


skipString :: String -> Parser ()
skipString s = () <$ prefixP s

Комбинации парсеров


В Haskell все функции по умолчанию каррированы и допускают частичное применение. Это значит, что функция от n аргументов — это на самом деле функция от одного аргумента, возвращающая функцию от n-1 аргументов:


cons :: Int -> [Int] -> [Int]
cons = (:)

cons1 :: [Int] -> [Int]
cons1 = cons 1 -- функция cons применена частично

Применим функцию от трёх аргументов к какому-нибудь значению внутри парсера, используя fmap. Типы будут такие:


f :: c -> a -> b
p :: Parser c
(fmap f p) :: Parser (a -> b)

Получился парсер функции?! Конечно, возможна ситуация, когда во входной строке действительно находится представление функции, но хотелось бы иметь возможность применять эту функцию, а точнее комбинировать парсеры Parser (a -> b) и Parser a, чтобы получить Parser b:


applyP :: Parser (a -> b) -> Parser a -> Parser b

Тип этой функции очень похож на тип fmap, только сама функция, которую нужно применить, также находится в контейнере. Это даёт интуитивное понимание того, как должна выглядеть реализация функции applyP: получить функцию из контейнера (как результат применения первого парсера), получить значения, к которым должна применяться функция (результат применения второго парсера) и "запаковать" преобразованные с помощью этой функции значения обратно в контейнер (создать новый парсер). В реализации будем использовать list comprehension:


applyP :: Parser (a -> b) -> Parser a -> Parser b
applyP (Parser p1) (Parser p2) = Parser f
    where f s = [ (sx, f x) | (sf, f) <- p1 s,  -- p1 применяется к исходной строке
                              (sx, x) <- p2 sf] -- p2 применяется к строке, оставшейся после предыдущего разбора

Существует класс Applicative, у которого есть метод с таким же прототипом. Второй метод класса называется pure и используется для того, чтобы "завернуть" или "поднять" (lift) значение, в том числе функциональное. В случае реализации для парсера функция pure добавляет свой аргумент в результат работы парсера, не изменяя при этом входную строку.


class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

instance Applicative Parser where
  pure x = Parser (\s -> [(s, x)])
  pf <*> px = Parser (\s -> [ (sx, f x) | (sf, f) <- unParser pf $ s,
                                          (sx, x) <- unParser px $ sf])

Функция applyP — это и есть <*> из класса Applicative. Типы, принадлежащие к этому классу, называются аппликативными функторами.


Для аппликативных функторов реализованы две вспомогательные функции, которые будут нам полезны:


(*>) :: f a -> f b -> f b
(<*) :: f a -> f b -> f a

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


Комбинируя <$> и <*>, можно создавать очень удобные конструкции. Рассмотрим следующий тип данных:


data MyStructType = MyStruct
  { field1 :: Type1
  , field2 :: Type2
  , field3 :: Type3
  }

Конструктор значений MyStruct — это тоже функция, в данном случае она имеет тип Type1 -> Type2 -> Type3 -> MyStructType. С конструктором можно работать как и с любой другой функцией. Предположим, что для типов полей структуры уже написаны парсеры:


parser1 :: Parser Type1
parser2 :: Parser Type2
parser3 :: Parser Type3

С помощью функции fmap можно частично применить MyStruct к первому из этих парсеров:


parserStruct' :: Parser (Type2 -> Type3 -> MyStructType)
parserStruct' = MyStruct <$> parser1

Попробуем дальше применять функцию, которая теперь находится "внутри" парсера. Для этого уже нужно использовать <*>:


parserStruct'' :: Parser (Type3 -> MyStructType)
parserStruct'' = parserStruct' <*> parser2

parserStruct :: Parser MyStructType
parserStruct = parserStruct'' <*> parser3

В итоге мы получили парсер для всей структуры (конечно, здесь используется предположение, что в исходной строке представления её полей идут подряд). То же самое можно сделать в одну строчку:


parserStruct :: Parser MyStructType
parserStruct = MyStruct <$> parser1 <*> parser2 <*> parser3

Такие конструкции будут часто встречаться в примере использования.


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


data Operand
  = IntOp Int
  | IdentOp String

Если мы уже умеем разбирать целые числа и идентификаторы (например, как в языке С), то нам нужен один парсер для операндов который может разобрать одно или другое. Этот парсер представляет собой альтернативу из двух других, поэтому нам нужна функция, умеющая комбинировать парсеры таким образом, чтобы результаты их работы объединялись. Результатом работы парсера является список, а объединение списков — это их конкатенация. Реализуем функцию altP, комбинирующую два парсера:


altP :: Parser a -> Parser a -> Parser a
altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)

Тогда парсер операнда можно реализовать, используя эту функцию (здесь предполагается, что parserInt и parserIdent уже где-то описаны:


parserOperand :: Parser Operand
parserOperand = altP parserIntOp parserIdentOp
  where
    parserIntOp = IntOp <$> parserInt
    parserIdentOp = IdentOp <$> parserIdent

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


class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a

instance Alternative Parser where
  empty = Parser (const [])
  px <|> py = Parser (\s -> unParser px s ++ unParser py s)

Операция <|> — это и есть функция altP, только в инфиксной записи, которую удобнее использовать, комбинируя несколько парсеров подряд.


Для всех типов в этом классе реализованы две функции, some и many типа f a -> f [a]. Каждая из них может быть выражена через другую:


some v = (:) <$> v <*> many v
many v = some v <|> pure []

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


Пример использования


Теперь у нас всё готово для того, чтобы написать свой парсер, например, для простых арифметических выражений со следующей грамматикой:


 expr      ::= constExpr | binOpExpr | negExpr
 const     ::= int
 int       ::= digit{digit}
 digit     ::= '0' | ... | '9'
 binOpExpr ::= '(' expr ' ' binOp ' ' expr ')'
 binOp     ::= '+' | '*'
 negExpr   ::= '-' expr

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


Примеры правильной записи выражений:


"123"
"-(10 + 42)"
"(1 + ((2 + 3) * (4 + 5)))"

Примеры неправильной записи:


" 666 "
"2 + 3"
"(10  * 10)"

Объявим необходимые типы данных (само выражение и бинарная операция):


data Expr = ConstExpr  Int
          | BinaryExpr Expr Operator Expr
          | NegateExpr Expr

data Operator = Add | Mul

Можно приступать к разбору! Само выражение состоит из трёх альтернатив. Так и запишем:


-- expr ::= constExpr | binOpExpr | negExpr
exprParser :: Parser Expr
exprParser = constParser <|> binParser <|> negParser

Константа — целое положительное число. В нашем типе данных оно "завёрнуто" в конструктор, поэтому мы не можем использовать парсер для целого числа напрямую, но можем применить fmap, чтобы получить значение нужного типа.


-- const ::= int
constParser :: Parser Expr
constParser = ConstExpr <$> intParser

Целое число, согласно грамматике, представляется как непустая последовательность цифр. Для разбора одной цифры используем вспомогательную функцию predP и предикат isDigit из модуля Data.Char. Теперь для построения парсера для разбора последовательности цифр используем функцию some (не many, потому что должна быть хотя бы одна цифра). Результат работы такого парсера возвращает список всех возможных вариантов разбора, начиная с самой длинной записи. Например, если входная строка "123ab", список результатов будет следующим: [("ab", "123"), ("3ab", "12"), ("23ab", "1")]. Нам нужно разобрать самую длинную последовательность цифр и преобразовать её к типу Int. Целиком реализация выглядит следующим образом:


-- int   ::= digit{digit}
-- digit ::= '0' | ... | '9'
intParser :: Parser Int
intParser = Parser $ \s -> let res = unParser (some digitParser) s in
  case res of
      [] -> []
      ((rest, i) : xs) -> [(rest, read i)]
  where
    digitParser = predP isDigit

Следующий вариант записи выражения — применение бинарной операции. Согласно грамматике, во входной строке сначала должна идти открывающая скобка, первый операнд, пробел, символ операции, ещё один пробел, второй операнд и закрывающая скобка. Для разбора отдельных символов (скобок и пробелов) используем функцию charP. Операнды — это выражения, а для их разбора парсер уже есть (exprParser). Для разбора символа бинарной операции опишем вспомогательный парсер чуть ниже. Остаётся аккуратно скомбинировать этот набор парсеров. В начале и в конце выражения должны быть скобки: нужно это проверить, но сам результат отбросить. Для этого используем *> и <*:


binParser :: Parser Expr
binParser = charP '(' *> ??? <* charP ')'

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


BinaryExpr <$> exprParser -- первый операнд
           <*> (charP ' ' *> binOpParser <* charP ' ') -- операция, окружённая пробелами
           <*> exprParser -- второй операнд

Подставим это выражение вместо знаков вопроса:


-- binOpExpr ::= '(' expr ' ' binOp ' ' expr ')'
binParser :: Parser Expr
binParser =
  charP '(' *>
    (BinaryExpr <$> exprParser
                <*> (charP ' ' *> binOpParser <* charP ' ')
                <*> exprParser
    )
  <* charP ')'

Бинарная операция — это либо символ +, который разбирается в значение Add, либо *, который разбирается в Mul:


-- binOp ::= '+' | '*'
binOpParser :: Parser Operator
binOpParser = plusParser <|> multParser
  where
    plusParser = charP '+' $> Add
    multParser = charP '*' $> Mul

Осталась самая простая часть грамматики, отрицание выражения. С символом - поступаем так же, как со скобками и пробелами. Далее применяем конструктор NegateExpr к результату рекурсивного разбора:


-- negExpr ::= '-' expr
negParser = charP '-' *> (NegateExpr <$> exprParser)

Итак, все части парсера реализованы. Код во многом напоминает грамматику и полностью совпадает с ней по структуре.


Исходный код доступен на GitLab: https://gitlab.com/fierce-katie/applicative-parsers-demo.


Там проще оценить его объём и степень выразительности, поскольку комментариев гораздо меньше. Проект можно собрать утилитой Stack и запустить примитивный интерпретатор, использующий парсер, который мы написали:


$ stack build
$ stack exec demo-parser

Тем, кто хочет потренироваться дальше самостоятельно, могу посоветовать следующее:


  • Грамматику можно всячески улучшить, например, допускать ведущие и висячие пробелы, добавить новые операции и т.д.
  • Парсер переводит строку во внутреннее представление выражения. Это выражение можно вычислить и преобразовать интерпретатор так, чтобы он печатал не результат разбора а результат вычисления.
  • Изучить возможности библиотек parsec, attoparsec, applicative-parsec и optparse-applicative, попробовать их применить.

Спасибо за внимание!


Полезные материалы


  1. Learn Haskell in Y minutes
  2. Денис Шевченко. "О Haskell по-человечески"
  3. Библиотека parsec
  4. Библиотека attoparsec
  5. Библиотека applicative-parsec
  6. Библиотека optparse-applicative
Поделиться публикацией

Комментарии 55

    +2

    Замечательно! Это очень вкусная тема — комбинаторный грамматический разбор. Не планируете ли вы продолжения, раскрывающего прочие достоинства аппликативного подхода: например, возможность статического анализа, невозможного в монадических парсерах. Я спрашиваю, поскольку сам подумывал написать об этом, но вдруг, у вас уже готов материал.
    В этой статье стоит сказать, что при вашем определении типа Parser возможен автоматический вывод экземпляра класса Funtor для него. Либо очень компактный и симметричный "ручной вариант":


    instance Functor Parser where
      fmap f = Parser . (fmap . fmap . fmap) f . unParse

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

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

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

        Я с удовольствием почитаю. Спасибо вам за статью!
          0

          f#
          Версия парсеров на другом языке. Практически один в один.

          0
          зачем такой изврат? если парсер комбинатор это StateT (трансформер монад) и тут можно какой угодно контейнер подставить
            0

            Затем, чтобы разобраться, что происходит. Проще всего использовать derive Functor, он выводится однозначно. StateT это верное решение, но не для туториала, придется слишком много тащить лишней инфраструктуры. Бесточечное определение, может быть, и выглядит колдовством, но оно отражает смысл преобразования: разворачиваем, заходим в "на дно" функтора, он у нас трехуровневый, и заворачиваем. При этом становится видно, что мы не делаем ничего лишнего.

          +3
          Может мне кто-нибудь объяснить, откуда в Haskell такая любовь к однобкувенным идентификаторам? Почему никто не пишет predicateParser predicate =… вместо predP p =…?
          Ни разу нигде не видел переменную типа больше одной буквы. Вот что, например, значат переменные типа в конструкции data SnapletInit b v, почему именно b и v а не a и z?
            +2
            Могу ошибаться, но думаю, что в данном случае «ноги растут» из алгебры. Там тоже иксы с игреками, а не CoordinateX, CoordinateY.
              +1
              Даже не знаю, как правильно ответить на ваш вопрос, кроме как руками помахать и сказать, что «так принято», «все так делают», «меня так научили», «я так привыкла» и т.п.
              Скорее всего это пришло из теории категорий. И сам язык располагает к использованию компактного синтаксиса, инфиксных синонимов и коротких имён в том числе.
              Но надо сказать, что многобуквенные переменные типа не так уж и редко встречаются.
                0
                В случае с объявлениями полиморфных типов, а уж тем более когда на типы налагаются ограничения классов типов, типа того, как здесь:
                showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String)

                причина как раз вполне понятна. Название этого параметра не несёт никакой смысловой нагрузки и лишь выступает в качестве местозаполнителя. И вряд ли особая польза была бы, если это записывали как:
                showVsPretty :: (Show itemToShow, PrettyPrint itemToShow) => itemToShow -> (String, String)

                А вот почему внутри реализаций функций такая тяга к коротким переменным — загадка. Вероятно как и в случае с C причина кроется в возрасте и наследственности языка. Во времена становления Haskell и уж тем более во времена становления ML о читаемости кода ещё так не пеклись, и люди просто привыкли.
                +4

                Если вы мне хотели показать какой haskell понятный, то вы сделали строго противоположное.


                applyP :: Parser (a -> b) -> Parser a -> Parser b
                applyP (Parser p1) (Parser p2) = Parser f
                    where f s = [ (sx, f x) | (sf, f) <- p1 s,  -- p1 применяется к исходной строке
                                              (sx, x) <- p2 sf] -- p2 применяется к строке, оставшейся после предыдущего разбора

                Что такое sx? Что такое p2 и зачем он, если есть p1? Что такое s? что такое x? Что такое f?


                (Я вижу 'where', но мне всё равно не понятно что вы подразумевали под f в рамках вашей предметной области).


                Да, если что, задача решается проще. Можно сделать композицию из f g h s d m l и всё получится. Что такое 'm' в данном примере вы вполне сами догадаетесь по контексту d и l.

                  +1
                  С Haskell дела не имел, но часть Ваших вопросов всё равно звучит странно. В начале же всё написано понятным английским языком: применяем парсер p1 к парсеру p2, чтобы получить парсер f, совмещающий возможности обоих, где f, применённый к s, по определению выглядит вот так. Дальше, да, начинается чёрная магия.
                    0
                    Но почему нельзя назвать переменные более читабельно, например parser1, parser2 и resultParser?
                      +3
                      Можно, но получится противоположная крайность (борщ борщ равно борщ фактори нью борщ, пожалуйста).
                      Здесь имена обладают такими особенностями:
                      * то что это «какой-то парсер» понятно и так — из конструкции (Parser p1) и из объявления типа.
                      * кроме того, что это какой-то парсер, в этом контексте про переменную ничего не известно — мы не можем её назвать там «bankAccountNumberParser». А имена «parser1» и «p1» несут примерно поровну информации (примерно нисколько — то, что это парсер, и так понятно).
                      * область видимости переменной — три строки. Если метод разрастётся до многих десятков строк, то лучше пусть будет «parser1», т.к. к середине метода читатель уже забудет, что видел конструкцию (Parser p1) в начале.

                      Вот имена «sx», «sf», имхо, выбраны не очень удачно. Но сходу не предложу значительно лучших имён.
                      Ещё тут зря используется одно имя «f» для разных переменных: одна для имени парсера, а другая в рамках list comprehension. Мой вариант:

                      applyP :: Parser (a -> b) -> Parser a -> Parser b
                      applyP (Parser p1) (Parser p2) = Parser $ \str ->
                          [ (p2remain, f a) | (p1remain, f) <- p1 str,  -- p1 применяется к исходной строке
                             (p2remain, a) <- p2 p1remain] -- p2 применяется к строке, оставшейся после предыдущего разбора
                      


                      (up: заменил совсем абстрактный икс на «a», так мне кажется лучше, потому что имя переменной совпадает с именем тИповой переменной — так понятно, что это то самое «а», которое в типе функции).
                        0
                        Ещё бы a/b p1/p2 осмыслено назвать. Чем они друг от друга отличаются?

                        Искусство придумывать названия — второе сложное искусство в IT.
                          +2
                          А ничем не отличаются. Кроме типа.
                          В том смысле, что нам про них в данном контексте ничего не известно — это «какой-то парсер» и «какой-то ещё парсер».
                          А тип виден в первой строке, енкодить его в имя переменной — излишне при небольшой области видимости.
                          Имхо.
                            –1
                            Если вы не знаете как «это» назвать — ваша абстракция фигня. (какой бы красивой не была математика).

                            Например, это может быть inner parser или outer parser. Имена переменных, функций, классов и модулей — это самое важное в языке программирования.
                              0
                              А чем отличается innerParser и parser1 (аналогично outerParser и parser2)? Только тем, что Ваши названия дополнительно подчёркивают семантику совершаемого действия? Так для этого у нас есть название метода, который ими оперирует.
                                0
                                Если нет разницы, значит абстрация плохая. Вплоть до самого алгоритма. Хорошая абстракция должна иметь вменяемые названия всего, чем оперирует, в каждый момент времени. Потому что альтернативой будет thing do thing to thing to make thing do things to things.
                                  0
                                  Так и запишем — последовательно применять несколько парсеров к одному участку исходных данных нельзя, всё надо делать за один раз, иначе у нас получается плохая абстракция.
                                    0
                                    Нет, это вы придумали. Я сказал, что плохая абстракция — это такая абстракция, в которой «жопа есть, а слова нет». Для серийных вещей есть списки и i-нотация, а для несерийных должны быть имена.

                                    Это требование не из CS, это требование из software engineering.
                                      0
                                      Ну, в данном случае «слово» есть — «парсер первый» и «парсер второй». Вы можете назвать какие-то другие их отличительные признаки, по которым можно назвать эти сущности? Если этих признаков нет — правильно ли я понимаю, что такая абстракция плоха?
                                        0
                                        Возможно, плоха реализация. Почему список из двух парсеров обрабатывается так, как будто это уникальные парсеры? Примените функцию «применить парсер» к списку парсеров.
                                          0
                                          А внутри неё будет точно такой же код, соединяющий их попарно, или гораздо более жуткий и громоздкий, в котором точно никаких вменяемых имён не придумать, который соединит все одним махом (второе — не уверен, что возможно, сам на Haskell не пишу). Или Вы полагаете, что как раз второй случай удастся реализовать более адекватно?
                                            0

                                            это разве не тривиальный foldl applyP parserList?

                                      +1
                                      Эта максима хороша, когда вы пишете прикладной код, где за каждой переменной стоит какая-то штука из вашего бизнеса (accountBalance это деньги на счету, numberOfBolts это количество болтов, итд).
                                      Когда вы пишете достаточно абстрактный библиотечный код (как в примере в статье), то очень часто оказывается, что вам почти или совсем не важно, что скрывается за переменными. В таком случае вы никогда не сможете придумать осмысленные имена. Ну, предположим, вы пишете функцию, складывающую два числа (именно не сумму на счёте с поступившими деньгами, а вообще, функцию сложения для стандартной библиотеки). Как вы назовёте её параметры? «слагаемое» и «прибавляемое»? seriously? :)
                                      В математике и среди программистов, пишущих абстрактный код, этот принцип несущественности назначения переменных (аргументов функций) настолько распространён, что есть противоположная максима: point-free notation, т.е. способ написания уравнений / кода, при котором имена переменных элиминируются полностью. Пример из хаскель-вики:
                                      it is clearer to write
                                      let fn = f . g . h

                                      than to write
                                      let fn x = f (g (h x))


                                      (имена fn, f, g и h в данном случае не обсуждаем). В данном примере нам настолько не важно, что такое «x», что мы его вообще предпочитаем не упоминать.

                                      Disclamer: всем и так очевидно, что прикладной код пишется гораздо чаще, чем абстрактный библиотечный.
                                        0

                                        Я бы сказал, что в этом месте у нас плохой язык. Почему? Потому что я вижу, что f, .g, h в этом примере — это объекты из списка. Для списочных данных (у каждого из которых нет имени) должны быть функции списочные же.


                                        Что-то вида: let chained_func = map(apply_in_chain, func_list)


                                        Для любителей значков: let chained_func = . func_list.


                                        Если кто-то в коде вам напишет:


                                        b = a[0] + a[1] + a[2]  + a[3] + a[4] + a[5] + a[6]

                                        Вы же его за это поругаете, правда? Так почему же для серийных объектов первого порядка (функий) такое исключение?

                                          0
                                          Я же написал: не обсуждаем имена f, g, h, fn; предположим, мы их заменили на какие-нибудь осмысленные:
                                          it is clearer to write
                                          let getAuthorSurname = getSurname . getAuthor . getBookById

                                          than to write
                                          let getAuthorSurname id = geSurname (getAuthor (getBookById id))


                                          Здесь «id» это какой-то идентификатор книги; в данном контексте нам не важно, откуда мы его достали и чему он равен; просто айди. Мы можем попытаться придумать более лучшее название, чем «id», потратить на это час и изобрести «anyBookIdentifier». Или мы можем вообще выкинуть его из кода.
                                            0
                                            Уже лучше. Сильно лучше. Об имени надо думать. Если вы имена выкидываете, у вас образуется нечитаемый код. И вы говорили не про «пример», а про абстрактный библиотечный код.

                                            Software engineering подразумевает, что код будут читать и перечитывать. И аннотации в виде осмысленных имён — это совершенно обязательное для промышленного кода.
                                            0
                                            А если у меня именно такой случай, что мне надо сделать композицию большого количества функций, природа каждой из которых мне неизвестна, так я примерно так и сделаю, как вы сказали: положу функции в список и применю к ним какую-нибудь свёртку, что-то типа foldr.
                                              –1
                                              Да, именно так. При этом вы всё равно что-то должны знать про функции с которыми работаете — и сам список должен будет называться осмысленно.

                                              Я повторю максиму: если не можете назвать что-то в коде, плохо думали.
                                            +1
                                            Очень плюсую. Как раз сидела думала, в какую бы ветку написать, что пост совсем не про коммерческую разработку и что к каждому вырванному из контекста куску кода с очень непонятными переменными прилагается несколько абзацев пояснений.
                                            0
                                            Или там будут одновременно функции startup(), startup2(), real_startup(). Или там prepareToSave(), beforeSave(), preSave(). Было бы смешно, но вот сам видел в продакшне.
                                              –1
                                              У меня, например, такие имена функций code review не пройдут. Есть этапы — с самого начала закладывай что они будут. Не заложил? Рефактори.
                                              0

                                              Мне кажется, вы прицепились к самому простому, тривиальному и неинтересному вопросу в программировании. Дискуссия вышла длинная, но с контексте статьи и CS ни о чем. Столько же времени и слов можно было бы потратить на что-либо другое.

                                              +1
                                              Если я в коде увижу вызов функции applyP p1 z, мне придется лезть или в документацию, или в исходники, или смотреть типы, чтобы понять, что это за функция. А, например, глядя в коде на вызов функции createSessionWebSocketMessageBrokerConfigurer messageBrokerConfigurerParams, сразу становится более-менее понятно, что тут происходит.
                                                –2
                                                ApplyP p1 — это уже непозволительная роскошь. Настоящие математики запишут как a p z.
                                        +2
                                        С перекрытием имени `f` и правда очень нехорошо вышло, спасибо, что ткнули, сама не заметила :( Но зато это иллюстрирует, как обстоят дела со связыванием в языке.

                                        По поводу одинаковых названий переменных типа и переменных в коде, такое лично меня запутывало на ранних стадиях обучения (и не только меня, видела ещё пару студентов с такой проблемой буквально в этом семестре). Начинает казаться, что тут типы first-class. Скорее всего это тоже дело вкуса, но с тех пор сама так не пишу.
                                        0
                                        А ещё, есть такой эффект, думаю его замечали на любом языке: новичок пытается писать «усиленно понятный» код, называет переменные «loopCounter» или пишет комментарии вида «увеличиваем переменную на 1» — просто потому, что самому ему написанный код понятен с трудом из-за слабого знакомства с языком. Потом это постепенно проходит.
                                          0
                                          С «усиленно понятными комментариями» соглашусь, у меня у самого было, когда программированию учился. А вот сейчас, когда есть некоторое количество опыта, я стараюсь писать усиленно понятный код на любых языках, и зачастую назвать переменную loopCounter может быть хорошей идеей. В идеале код должен читаться так, как будто это не код, а описание того, что он делает. Кстати, если вместо использования крутых мегаконструкций в одно выражение использовать что-то попроще, то это потом и дебажить в случае чего легче.
                                            0

                                            loopCounter — это по ушам за это бить. Потому что "счётчик в цикле" нам и так видно. А что этот цикл считает?


                                            Вот, смотрите:


                                            for i, v in enumerate(g(d)):
                                               f(v, i)

                                            Сравните с:


                                            for sequential_num, emploee_name in enumerate(get_emploees(department)):
                                               print_numbered_bage(emploee_name, sequential_num)

                                            В каком случае вы понимаете что я имел в виду?


                                            P.S. Я думал про имя счётчика долго. Это моя третья попытка придумать выразительное имя. Вот если у нас бейджи нумерованные, что такое "номер на бейдже"?

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

                                              А во втором — конкретная бизнес-логика.

                                              Именно это вам и пытаются донести.
                                                0
                                                Не надо использовать слово «бизнес-логика». Я предпочитаю «семантика». Смысловая нагрузка. Это может быть не бизнес-логика, а процесс машинного доказательства P!=NP, сути это не меняет. Имена переменных позволяют дать смысл коду, код без имён переменных смысла не имеет (т.к. никто не может сказать, что происходит, кроме IO).
                                                  +1
                                                  Не надо использовать слово «бизнес-логика». Я предпочитаю «семантика».

                                                  Что, если кто-то предпочитает иначе?
                                                    0
                                                    Если кто-то скажет «бизнес-логика» это тоже ок, но часто вслед за этим звучит «а раз мы тут бизнесом не занимаемся, то у нас бизнес-логики нет». А семантика есть у всех и всегда. Не всегда удаётся её передать, а есть она у всех, кроме как у результата генерации рандомного кода.
                                                      +2
                                                      И все же, что если кто-то предпочитает иначе?
                                                    +1
                                                    Вообще, можно привести контрпример. Сравните (раз уж вы используете питон):

                                                    def add(a, b):
                                                        return a+b
                                                    


                                                    С

                                                    def add_two_abstract_items(first_abstract_item, second_abstract_item):
                                                        return first_abstract_item + second_abstract_item
                                                    


                                                    Вы действительно считаете что второй вариант лучше?
                                                      –1
                                                      имя переменной «item» (thing, this, something) не информативно.

                                                      Что эта функция делает? Кто её использует?
                                                        +2
                                                        Эта функция складывает два объекта, для которых определена функция сложения. Это могут быть числа, вектора, матрицы, строки, файлы, множества и т.д.

                                                        Как вы предлагаете назвать функцию и параметры?
                                            0
                                            Именование переменных — это место, где программист может объяснить другому программисту что происходит. Я понимаю, что у хаскеля корни из математики и это заметно в нотации, но я обычно заворачиваю любые pull-request'ы у которых такой уровень информативности переменных.
                                              +4

                                              В ваших комментариях очень много личного: "я заворачиваю", "надавать по ушам", "у меня не пройдет ревью"… это имеет отношение к статье, к аппликативным функторам, к парсингу? Вышел долгий спор о привычках и вкусах, не несущий ничего нового, свежего, интересного.

                                              0
                                              В квадратных скобках это генераторное выражение, как например в Python. Слева от стрелки < — это деструктуризация результата применения парсера p1 к строке s. Т.е. кортеж из строки sf и функции f (которая в данном случае это значение (a -> b) для парсера p1). В втором кортеже x потому, что для парсера p2 нужно просто значение a (см. описание типа). Результат данного выражения это список кортежей из строк и результатов применения функции f из парсера p1 к значению из парсера p2 )))

                                              Это можно было бы написать с помощью 2 вложенных циклов, если бы они были в Haskell. Тут достаточно настроить свой внутренний интерпретатор и научится читать декларативный код Haskell. В первую очередь обращать внимание на аннотацию типов, а само данное выражение проще читать справа-налево и снизу-вверх, а не наоборот.
                                              +2
                                              Вот вы иронизируете, а вот документация к одной из самых известных библиотек на Хаскеле: hackage.haskell.org/package/lens-4.17/docs/Control-Lens-Lens.html
                                              А вот часть списка определённых в ней функций: hackage.haskell.org/package/lens-4.17/docs/doc-index-60.html

                                              Не встречала ещё тех, кто был бы к этой библиотеке равнодушен, её либо любят и везде используют (ведь названия операторов такие очевидные и интуитивно понятные), либо не используют никогда и другим не советуют.
                                                +1
                                                Вот это да!
                                                Воистину, «не тот язык назвали Brainfuck'ом» (с) не мое
                                                +3

                                                Тут две строчки. Всего две короткие симметричные строчки, все обозначения определены тут же. Типы объясняют что делает функция, компилятор подтверждает, что реализация верна. Да, нужно остановиться ненадолго, но с этим можно разобраться, и этот опыт будет полезен. И это не APL, не J в двух строчках на которых можно сломать ногу, здесь из абстракций только генерация списка.

                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                              Самое читаемое