动机
当我刚开始学习Haskell时，我对复杂抽象而不是任何特定解决方案的广泛使用感到非常恼火。 在我看来，始终遵循KISS原则并使用基本语言构造编写自行车要比理解所有这些类型类更好，以便在某个地方编写一个据认为方便的构造要好得多。
我没有一个很好的例子，花在发展“物资”上的努力会得到回报。 对我来说，最成功的例子之一就是解析器。 现在，当他们问我可以使用Haskell完成哪些常见任务时，我经常谈论它们。
我想为初学者提供这种方法，并从头开始创建一个小的函数库，以方便解析器的实现，然后使用它编写自己的解析器，其代码几乎会真正地重复用于解析的语法。
我希望这可以帮助某人克服对抽象的恐惧，并教他们如何适当地使用它们（是的，我仍然认为编写自行车有时会更有效率）。
我没有目的，也不想从头开始编写Haskell课程，因此我假设读者熟悉语法并独立开发了简单程序。 以防万一，在继续介绍实现之前，我将简要讨论类型类。
对于从未写过Haskell但想了解此处发生情况的用户，建议您先在Y分钟内查看Learn X的相应页面。 作为适合初学者的优秀俄语书籍，我建议丹尼斯·舍甫琴科（ Denis Shevchenko）撰写的“关于人类的哈斯克尔” 。
我将尝试使用初学者可以理解的最简单的语言构造。 在文章的结尾，给出了到源存储库的链接，其中在代码的某些部分中使用了更方便，更短的条目，乍一看可能不太清楚。
是的，Haskellist先生们，很多情况下都非常简单明了，对于特殊情况，不是很抽象，没有使用类别理论的术语和其他令人恐惧的词。 我很高兴您认识他们，当然他们很容易掌握它们。 我也知道它们，但是在这种情况下，我认为没有必要抛弃对准备不足的读者来说不必要的大量信息。
类型类别
Haskell类型类与C ++和其他面向对象语言中的类无关。 如果我们用OOP做一个类比，则类型类更像是方法和函数的重载。
类确定可以对组成该类的类型的对象执行哪些操作。 例如，可以对所有数字进行相等性比较，但可以对所有数字进行排序（复杂数字除外），并且通常根本无法对函数进行比较。 可以比较的类型类别称为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 xy) = "(" ++ 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 (ps) of [("", val)] -> Just val _ -> Nothing
简单解析器
我们实现了几个简单的解析器，这些解析器将在构建更复杂的组合时派上用场。
我们首先分析一个必须满足谓词的字符。 如果输入字符串为空，则工作结果为空列表。 否则，我们在字符串的第一个字符上检查谓词的值。 如果返回True ，则解析结果为该字符；否则为false。 将其与其余字符串一起返回。 否则，解析也会失败。
predP :: (Char -> Bool) -> Parser Char predP p = Parser f where f "" = [] f (c : cs) | pc = [(cs, c)] | otherwise = []
现在，我们可以编写一个解析器，该解析器在该行的开头采用一个特定的字符。 为此，请使用刚刚编写的predP并将其作为参数传递给一个函数，该函数将其参数与所需的字符进行比较：
charP :: Char -> Parser Char charP char = predP (\c -> c == char)
以下是最简单的情况：整体上仅接受特定字符串的解析器。 stringP称它为stringP 。 解析器中的函数将输入行与所需行进行比较，如果行相等，则返回一个元素的列表：一对空行（输入中不留任何内容）和原始行。 否则，解析将失败，并返回一个空结果列表。
stringP :: String -> Parser String stringP s = Parser f where fs' | s == s' = [("", s)] | otherwise = []
通常，在行首时需要跳过具有特定属性的字符（例如，空白字符）。 此外，分析的结果对我们并不重要，将来也将无用。 我们编写了一个skip函数，该函数在保留谓词的真实值的同时跳过字符串的初始字符。 作为分析结果，我们使用一个空的元组。
skip :: (Char -> Bool) -> Parser () skip p = Parser (\s -> [(dropWhile ps, ())])
接下来的两个解析器彼此非常相似。 两者都检查输入行前缀，只有第一个（如果成功的话）返回该前缀，第二个返回空的元组，即 允许您在输入的开头跳过任意行。 该实现使用Data.List模块中定义的isPrefixOf函数。
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- a -> b函数，并获得[b]类型的列表。
这种类型的类称为Functor ；该类具有一个fmap方法：
class Functor f where fmap :: (a -> b) -> fa -> fb
假设我们已经知道如何将字符串解析为某种类型a对象，此外，我们知道如何将a类型a对象转换为b类型a对象。 是否可以说存在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 fx == f <$> x 。
如果我们使用函数作为fmap的参数，只是将其第一个参数替换为新值，那么即使在两个实例中，我们也将为所有函子实现另一个有用的操作（它们仅在参数顺序上有所不同）：
(<$) :: Functor f => a -> fb -> fa ($>) :: Functor f => fa -> b -> fb
还记得跳过特定行的分析器（ skipString ）吗？ 现在，您可以按以下方式实现它：
skipString :: String -> Parser () skipString s = () <$ prefixP s
解析器组合
在Haskell中，默认情况下所有函数都是咖喱的，并且部分可用。 这意味着n参数的函数实际上是一个参数的函数，返回n-1参数的函数：
cons :: Int -> [Int] -> [Int] cons = (:) cons1 :: [Int] -> [Int] cons1 = cons 1
我们使用fmap将三个参数中的函数应用于解析器中的某个值。 类型如下：
f :: c -> a -> b p :: Parser c (fmap fp) :: Parser (a -> b)
函数解析器原来是？！ 当然，当函数的表示确实在输入行中时，可能会出现这种情况，但是我希望能够使用此函数，或者更确切地说，将Parser (a -> b)和Parser a解析器组合以获得Parser b ：
applyP :: Parser (a -> b) -> Parser a -> Parser b
此函数的类型与fmap类型非常相似，只有需要应用的函数本身也位于容器中。 这可以直观地了解applyP函数的实现方式：从容器中获取函数（作为应用第一个解析器的结果），获取函数应应用的值（应用第二个解析器的结果），然后将使用此函数转换后的值“打包”放入容器中（创建一个新的解析器）。 在实现中，我们将使用列表推导：
applyP :: Parser (a -> b) -> Parser a -> Parser b applyP (Parser p1) (Parser p2) = Parser f where fs = [ (sx, fx) | (sf, f) <- p1 s,
有一个Applicative类，该类的方法具有相同的原型。 该类的第二种方法称为pure函数，用于“包装”或“提升”（ lift ）一个值，包括一个功能值。 对于解析器的实现， pure函数将其参数添加到解析器的结果中，而无需更改输入字符串。
class Functor f => Applicative f where pure :: a -> fa (<*>) :: f (a -> b) -> fa -> fb instance Applicative Parser where pure x = Parser (\s -> [(s, x)]) pf <*> px = Parser (\s -> [ (sx, fx) | (sf, f) <- unParser pf $ s, (sx, x) <- unParser px $ sf])
applyP函数是Applicative类中的<*> 。 属于此类的类型称为应用函子。
对于应用函子，实现了两个对我们有用的辅助功能：
(*>) :: fa -> fb -> fb (<*) :: fa -> fb -> fa
这些函数执行两个连续的动作，并仅返回其中一个的结果。 对于解析器，可以使用它们来例如在分析承载语义负载的字符串的一部分之前跳过前导空格。
通过组合<$>和<*> ，可以创建非常方便的设计。 考虑以下数据类型：
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
如果我们已经知道如何解析整数和标识符（例如，在C语言中），那么我们需要一个解析器来解析可以互斥的一个操作数。 此解析器是其他两个解析器的替代方案，因此我们需要一个可以组合解析器的功能，以便合并其工作结果。 解析器的结果是一个列表，合并列表就是它们的串联。 我们实现结合两个解析器的altP函数：
altP :: Parser a -> Parser a -> Parser a altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)
然后，可以使用此函数来实现操作数解析器（此处假定parserInt和parserIdent已经在某处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 :: fa (<|>) :: fa -> fa -> fa instance Alternative Parser where empty = Parser (const []) px <|> py = Parser (\s -> unParser px s ++ unParser py s)
操作<|>仅是后缀表示法中的altP函数，通过将多个解析器组合成一行，使用起来更方便。
对于此类中的所有类型，都实现了两个函数， some函数many类型为fa -> f [a] 。 它们每个都可以通过另一个表达：
some v = (:) <$> v <*> many v many v = some v <|> pure []
就解析器而言，如果您知道如何解析单个数据元素，这些函数就可以解析数据序列。 如果使用some序列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
您可以开始解析！ 该表达式本身包含三种选择。 所以我们写：
常数是一个正整数。 在我们的数据类型中，它在构造函数中被“包装”，因此我们不能直接将解析器用于整数，但是可以使用fmap获取所需类型的值。
根据语法，整数表示为数字的非空序列。 要解析一位数字，我们使用辅助函数predP和Data.Char模块中的谓词isDigit 。 现在，要构建用于解析数字序列的解析器，我们使用some功能（不多，因为必须至少有一个数字）。 这样的解析器的结果从最长的记录开始，返回所有可能的解析选项的列表。 例如，如果输入字符串为“ 123ab”，则结果列表如下： [("ab", "123"), ("3ab", "12"), ("23ab", "1")] 。 我们需要解析最长的数字序列并将其转换为Int类型。 整个实现如下：
编写表达式的另一种方法是使用二进制运算。 根据语法，开括号必须首先包括开括号，第一个操作数，空格，运算符，另一个空格，第二个操作数和闭括号。 为了解析单个字符（括号和空格），我们使用charP函数。 操作数是表达式，并且已经有一个解析器（ exprParser ）来解析它们。 为了解析二进制运算符号，我们在下面描述辅助解析器。 整齐地组合这组解析器仍然有待解决。 表达式的开头和结尾应该有方括号：您需要检查一下，但要丢弃结果本身。 为此，请使用*>和<* ：
binParser :: Parser Expr binParser = charP '(' *> ??? <* charP ')'
在这些用于括号的解析器之间，必须使用BinaryExpr构造函数以及用于表达式和操作的解析器BinaryExpr构造表达式。 使用与方括号相同的方法，不要忘记操作符号周围的空格。 这部分如下：
BinaryExpr <$> exprParser
我们用以下表达式代替问号：
二进制运算符可以是+字符来解析Add值，或者是*来解析Mul ：
剩下的就是语法中最简单的部分，即表达的否定。 使用符号-与使用方括号和空格的操作相同。 接下来，将NegateExpr构造函数应用于递归解析的结果：
因此，解析器的所有部分均已实现。 该代码很像一个语法，并且在结构上与之完全一致。
可以从GitLab获得源代码： https ://gitlab.com/fierce-katie/applicative-parsers-demo。
由于注释少得多，因此更容易评估其表达量和表达程度。 您可以使用Stack实用程序来编译项目，并使用我们编写的解析器运行基本解释器：
$ stack build $ stack exec demo-parser
对于那些想自己进一步练习的人，我可以提供以下建议：
- 语法可以通过各种方式进行改进，例如，允许前导和悬挂空格，添加新操作等。
- 解析器将字符串转换为表达式的内部表示形式。 可以计算该表达式，并转换解释器，以便它不输出解析结果，而是输出计算结果。
- 探索
parsec ， attoparsec ， applicative-parsec和optparse-applicative applicative-parsec的可能性，并尝试使用它们。
感谢您的关注！
有用的材料
- 在Y分钟内学习Haskell
- 丹尼斯·舍甫琴科。 “关于Haskell作为人类”
- Parsec库
- Attoparsec库
- 应用视差库
- Optparse应用程序库