Haskell/实用单子
在本章节中，我们将展示一些单子被用于实际任务的不同示例。可以将其视为额外资料，并根据自己的节奏学习。如果某些部分（例如关于并发的最后示例）现在看起来过于陌生，你可以随时回来查看。
本节内容基于 Jonathan Tang 的 在 48 小时内编写 Scheme 中的“解析”章节。
在前面的章节中，我们看到了单子是如何用于 IO 的，并开始更广泛地使用一些更基础的单子，如 Maybe，List 或 State。现在让我们尝试一些本质上“实用”的东西：编写一个简单的解析器。单子提供了一种干净的方式，将特定于领域的解析语言直接嵌入到 Haskell 中，而无需使用外部工具或代码生成器。为了简要介绍该主题，我们建议阅读 Graham Hutton 和 Erik Meijer 的论文 函数式珠玑：Haskell 中的单子解析。不过现在，是该亲自动手的时候了，为此，我们将使用 Parsec 库，版本 3 或更高版本。
我们需要为这段代码添加一个扩展：FlexibleContexts。这使我们可以编写诸如 (Stream s u Char) => 这样的类约束，其中一个类型变量被定义，而不是多态的。
{-# LANGUAGE FlexibleContexts #-}
从在导入部分添加以下行开始
import Control.Monad import Control.Monad.Identity (Identity) import System.Environment (getArgs) import Text.Parsec hiding (spaces)
这使我们能够使用 Parsec 库函数和 getArgs，除了“spaces”函数，它的名称与我们将定义的另一个函数冲突。此外，Identity 单子也变得可用，这样我们就可以在 Identity 上使用 ParsecT。
现在，我们将定义一个解析器，它可以识别 Scheme 标识符中允许使用的符号之一
symbol :: Stream s m Char => ParsecT s u m Char symbol = oneOf "!#$%&|*+-/:<=>?@^_~"
这是另一个单子的示例：在这种情况下，被隐藏的“额外信息”是关于输入流中的位置、回溯记录、first 和 follow 集等的所有信息。Parsec 3 使用单子转换器来为我们处理所有这些。我们只需要使用 Parsec 库函数 oneOf（参见 Text.Parsec.Char），它将识别传递给它的字符串中的任意一个字符。正如你即将看到的，你可以将原始解析器组合成更复杂的生成式。
该函数的类型有点令人困惑。Stream s m Char 定义了一个类型为 s 的 Char 的“流”，封装在单子 m 中。s 的示例是 String 或 ByteString。适应 String 和 ByteString 是我们定义函数在 String 周围多态化的主要原因。Parsec 包含一个名为 Parser 的类型，但它不像我们通常希望的那样多态 - 它明确要求流类型为 String。
ParsecT 定义了一个流类型为 s，状态类型为 u（我们实际上不需要使用状态，但它对于将我们的函数定义为状态多态非常有用），内部单子为 m（如果我们不希望将其用作转换器，通常是 Identity），结果类型为 Char，它是 Monad 的“普通”类型参数的解析器。
让我们定义一个函数来调用我们的解析器并处理任何可能的错误
readExpr :: Stream s Identity Char => s -> String
readExpr input = case parse symbol "lisp" input of
Left err -> "No match: " ++ show err
Right val -> "Found value"
如你从类型签名中看到的，readExpr 是一个从 Stream（通常是 String 或 ByteString）到 String 的函数（->）。我们将参数命名为 input，并将其与我们上面定义的 symbol 操作以及解析器名称“lisp”一起传递给 Parsec 函数 parse。
Parse 可以返回解析的值或错误，因此我们需要处理错误情况。遵循典型的 Haskell 惯例，Parsec 返回一个 Either 数据类型，使用 Left 构造函数来指示错误，使用 Right 构造函数来指示正常值。
我们使用 case...of 结构来将 parse 的结果与这些备选方案进行匹配。如果我们得到一个 Left 值（错误），那么我们将错误本身绑定到 err 并返回包含错误字符串表示形式的“无匹配项”。如果我们得到一个 Right 值，那么我们将它绑定到 val，忽略它，并返回字符串“找到值”。
case...of 结构是模式匹配的一个示例，我们将在 [evaluator1.html#primitiveval 稍后] 中更详细地讨论它。
最后，我们需要更改我们的 main 函数以调用 readExpr 并打印出结果
main :: IO ()
main = do args <- getArgs
putStrLn (readExpr (args !! 0))
要编译并运行它，你需要在命令行中指定“-package parsec -package mtl”，否则会出现链接错误。例如
debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o simple_parser [../code/listing3.1.hs listing3.1.hs] debian:/home/jdtang/haskell_tutorial/code# ./simple_parser $ Found value debian:/home/jdtang/haskell_tutorial/code# ./simple_parser a No match: "lisp" (line 1, column 1): unexpected "a"
接下来，我们将对我们的解析器进行一系列改进，使其能够识别越来越复杂的表达式。当前的解析器如果在我们的符号之前有空格，则会出错
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser " %" No match: "lisp" (line 1, column 1): unexpected " "
让我们修复它，以便忽略空格。
首先，让我们定义一个解析器，它可以识别任意数量的空格字符。顺便说一下，这就是我们在导入 Parsec 时包含“hiding (spaces)”子句的原因：该库中已经存在一个名为 "spaces" 的函数，但它不能完全满足我们的要求。（就此而言，还有一个名为 lexeme 的解析器，它可以完全满足我们的要求，但出于教学目的，我们将忽略它。）
spaces :: Stream s m Char => ParsecT s u m () spaces = skipMany1 space
正如函数可以传递给函数一样，操作也可以传递给操作。在这里，我们将 Parser 操作 space 传递给 Parser 操作 skipMany1，以获得一个可以识别一个或多个空格的 Parser。
现在，让我们编辑我们的解析函数，使其使用这个新的解析器
readExpr input = case parse (spaces >> symbol) "lisp" input of
Left err -> "No match: " ++ show err
Right val -> "Found value"
我们在第一课中简要提到了 >>（“然后”）运算符，我们提到它是在幕后用于组合 do 块的各行代码的。在这里，我们显式地使用它来组合我们的空格和符号解析器。但是，然后在 Parser 和 IO 单子中具有完全不同的语义。在 Parser 单子中，然后意味着“尝试匹配第一个解析器，然后尝试匹配第二个解析器并使用剩余的输入，如果任一解析器失败，则失败”。一般来说，然后在不同的单子中会有截然不同的效果；它的目的是作为一种通用方式来构建计算，因此需要足够通用，以适应所有不同类型的计算。阅读该单子的文档以确切了解它的作用。
编译并运行这段代码。请注意，由于我们用 skipMany1 定义了 spaces，因此它不再识别普通的单字符。相反，你必须用一些空格来作为符号的前缀。我们很快就会看到这如何有用
debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o simple_parser [../code/listing3.2.hs listing3.2.hs] debian:/home/jdtang/haskell_tutorial/code# ./simple_parser " %" Found value debian:/home/jdtang/haskell_tutorial/code# ./simple_parser % No match: "lisp" (line 1, column 1): unexpected "%" expecting space debian:/home/jdtang/haskell_tutorial/code# ./simple_parser " abc" No match: "lisp" (line 1, column 4): unexpected "a" expecting space
现在，解析器并没有真正执行任何操作 - 它只是告诉我们一个给定的字符串是否可以被识别。一般来说，我们希望从解析器中获得更多东西：我们希望它们将输入转换为可以轻松遍历的数据结构。在本节中，我们将学习如何定义数据类型，以及如何修改我们的解析器，使其返回这种数据类型。
首先，我们需要定义一个数据类型，它可以保存任何 Lisp 值
data LispVal = Atom String
| List [LispVal]
| DottedList [LispVal] LispVal
| Number Integer
| String String
| Bool Bool
这是一个代数数据类型的示例：它定义了一组类型为 LispVal 的变量可以保存的值。每个备选方案（称为构造函数，并用 | 分隔）包含构造函数的标签以及该构造函数可以保存的数据类型。在本例中，LispVal 可以是
- 一个 Atom，它保存一个用于命名该原子的 String
- 一个 List，它保存其他 LispVal 的列表（Haskell 列表用方括号表示）
- 一个 DottedList，表示 Scheme 表达式 (a b . c)。它保存了所有元素的列表，除了最后一个元素，然后将最后一个元素保存为另一个字段
- 一个 Number，包含一个 Haskell 整数
- 一个 String，包含一个 Haskell 字符串
- 一个 Bool，包含一个 Haskell 布尔值
构造函数和类型具有不同的命名空间，因此你可以同时拥有一个名为 String 的构造函数和一个名为 String 的类型。类型和构造函数标签始终以大写字母开头。
接下来，让我们添加几个解析函数，以创建这些类型的值。字符串是一个双引号，后面跟着任意数量的非引号字符，最后跟着一个闭合的引号
parseString :: Stream s m Char => ParsecT s u m LispVal
parseString = do char '"'
x <- many (noneOf "\"")
char '"'
return $ String x
我们又回到了使用 do 表示法而不是 >> 运算符。这是因为我们将检索解析的值（由 many (noneOf "\"") 返回）并对其进行操作，同时插入其他一些解析操作。一般来说，如果操作不返回值，则使用 >>；如果将该值立即传递给下一个操作，则使用 >>=；否则使用 do 表示法。
一旦我们完成了解析并从 many 函数中获得了 Haskell 字符串，我们应用 String 构造函数（来自我们的 LispVal 数据类型）将其转换为 LispVal。代数数据类型中的每个构造函数也像一个函数一样，将它的参数转换为其类型的值。它也充当一个模式，可以在模式匹配表达式左侧使用；我们在 [#symbols Lesson 3.1] 中看到了一个例子，当时我们将解析器结果与 Either 数据类型中的两个构造函数匹配。
然后我们应用内置函数 return 将我们的 LispVal 提升到 Parser monad 中。请记住，do 块中的每一行都必须具有相同的类型，但我们的 String 构造函数的结果只是一个普通的 LispVal。Return 让我们将其包装在一个 Parser 操作中，该操作不消耗任何输入，而是将其作为内部值返回。因此，整个 parseString 操作将具有 Parser LispVal 类型。
$ 运算符是中缀函数应用：它与我们写 return (String x) 相同，但 $ 是右结合的，让我们可以消除一些括号。由于 $ 是一个运算符，因此您可以对它做任何您通常对函数做的事情：传递它、部分应用它等等。在这方面，它像 Lisp 函数 apply 一样。
现在让我们继续讨论 Scheme 变量。一个 原子 是一个字母或符号，后面跟着任意数量的字母、数字或符号
parseAtom :: Stream s m Char => ParsecT s u m LispVal
parseAtom = do first <- letter <|> symbol
rest <- many (letter <|> digit <|> symbol)
let atom = [first] ++ rest
return $ case atom of
"#t" -> Bool True
"#f" -> Bool False
otherwise -> Atom atom
这里，我们介绍了另一个 Parsec 组合器，选择运算符 <|>。它尝试第一个解析器，如果失败，则尝试第二个。如果任一解析器成功，则返回该解析器返回的值。第一个解析器必须在消耗任何输入之前失败：我们将在后面看到如何实现回溯。
一旦我们读取了第一个字符和原子的其余部分，我们需要将它们放在一起。"let" 语句定义了一个名为 "atom" 的新变量。为此，我们使用列表连接运算符 ++。请记住 first 只是一个字符，因此我们通过在它周围加上方括号将其转换为单元素列表。如果我们想创建一个包含多个元素的列表，我们只需用逗号将它们隔开。
然后我们使用一个 case 语句来确定要创建和返回哪个 LispVal，与 true 和 false 的字面字符串匹配。otherwise 备选方案是一个可读性技巧：它绑定一个名为 otherwise 的变量，我们忽略它的值，然后始终返回 atom 的值。
最后，我们创建另一个解析器，用于数字。这展示了处理单子值的另一种方法
parseNumber :: Stream s m Char => ParsecT s u m LispVal parseNumber = liftM (Number . read) $ many1 digit
从后往前读最容易，因为函数应用 ($) 和函数组合 (.) 都是右结合的。parsec 组合器 many1 匹配其参数的一个或多个，因此这里我们匹配一个或多个数字。我们想从结果字符串中构造一个数字 LispVal，但我们有一些类型不匹配。首先，我们使用内置函数 read 将该字符串转换为数字。然后我们将结果传递给 Number 以获得 LispVal。函数组合运算符 "." 创建一个函数，它应用其右参数，然后将结果传递给左参数，因此我们使用它来组合这两个函数应用。
不幸的是，many1 digit 的结果实际上是 Parser String，因此我们组合的 Number . read 仍然无法对其进行操作。我们需要一种方法告诉它只对单子内部的值进行操作，并将 Parser LispVal 返回给我们。标准函数 liftM 正好可以做到这一点，因此我们将 liftM 应用于我们的 Number . read 函数，然后将结果应用于我们的 Parser。
这种编程风格 - 大量依赖函数组合、函数应用以及将函数传递给函数 - 在 Haskell 代码中非常常见。它通常允许您在一行代码中表达非常复杂的算法，将中间步骤分解成其他函数，这些函数可以以各种方式组合。不幸的是，这意味着您通常必须从右到左阅读 Haskell 代码，并仔细跟踪类型。我们将在本教程的其余部分看到更多示例，因此希望您能对此感到很舒适。
让我们创建一个解析器，它接受字符串、数字或原子
parseExpr :: Stream s m Char => ParsecT s u m LispVal
parseExpr = parseAtom
<|> parseString
<|> parseNumber
并编辑 readExpr 以便它调用我们的新解析器
readExpr :: String -> String
readExpr input = case parse parseExpr "lisp" input of
Left err -> "No match: " ++ show err
Right _ -> "Found value"
编译并运行此代码，您会注意到它接受任何数字、字符串或符号，但不接受其他字符串
debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o simple_parser [.../code/listing3.3.hs listing3.3.hs]
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "\"this is a string\""
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser 25 Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser symbol
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser (symbol)
bash: syntax error near unexpected token `symbol'
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(symbol)"
No match: "lisp" (line 1, column 1):
unexpected "("
expecting letter, "\"" or digit
| 练习 |
|---|
|
递归解析器：添加列表、点式列表和引用的数据
[edit | edit source]接下来，我们向解释器添加一些解析器操作。从 Lisp 中著名的带括号的列表开始
parseList :: Stream s m Char => ParsecT s u m LispVal parseList = liftM List $ sepBy parseExpr spaces
这类似于 parseNumber，首先解析一系列由空格分隔的表达式（sepBy parseExpr spaces），然后在 Parser monad 中应用 List 构造函数。还要注意，我们可以将 parseExpr 传递给 sepBy，即使它是我们自己编写的操作。
点式列表解析器稍微复杂一些，但仍然只使用我们已经熟悉的概念
parseDottedList :: Stream s m Char => ParsecT s u m LispVal
parseDottedList = do
head <- endBy parseExpr spaces
tail <- char '.' >> spaces >> parseExpr
return $ DottedList head tail
注意如何使用 >> 将一系列 Parser 操作连接在一起，然后在 do 语句的右侧使用整个序列。表达式 char '.' >> spaces 返回一个 Parser ()，然后将它与 parseExpr 组合得到一个 Parser LispVal，这正是 do 块所需的类型。
接下来，让我们添加对 Scheme 的单引号语法糖的支持
parseQuoted :: Stream s m Char => ParsecT s u m LispVal
parseQuoted = do
char '\''
x <- parseExpr
return $ List [Atom "quote", x]
这大部分都是我们已经熟悉的东西：它读取一个单引号字符，读取一个表达式并将其绑定到 x，然后返回 (quote x)，使用 Scheme 符号。Atom 构造函数像普通函数一样工作：您将要封装的 String 传递给它，它会返回一个 LispVal。您可以对这个 LispVal 做任何您通常可以做的事情，例如将其放在列表中。
最后，编辑 parseExpr 的定义以包含我们的新解析器
parseExpr :: Stream s m Char => ParsecT s u m LispVal
parseExpr = parseAtom
<|> parseString
<|> parseNumber
<|> parseQuoted
<|> do char '('
x <- (try parseList) <|> parseDottedList
char ')'
return x
这说明了 Parsec 的一个最后的功能：回溯。parseList 和 parseDottedList 识别到点为止相同的字符串；这违反了选择备选方案在失败之前不能消耗任何输入的要求。 try 组合器尝试运行指定的解析器，但如果失败，则回退到之前状态。这允许您在选择备选方案中使用它，而不会影响其他备选方案。
编译并运行此代码
debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o simple_parser [../code/listing3.4.hs listing3.4.hs] debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a test)" Found value debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a (nested) test)" Found value debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a (dotted . list) test)" Found value debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a '(quoted (dotted . list)) test)" Found value debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a '(imbalanced parens)" No match: "lisp" (line 1, column 24): unexpected end of input expecting space or ")"
注意，通过在我们的解析器中引用 parseExpr，我们可以将它们任意嵌套。因此，我们只用几个定义就得到了一个完整的 Lisp 阅读器。这就是递归的力量。
| 练习 |
|---|
|
用于并发应用程序的有状态单子
[edit | edit source]您必须了解 Monad transformers 才能执行这些操作。虽然这个例子是因为 Concurrency 而出现的，但如果您意识到 TVar 是一种可变变量，那么这个例子出现的原因就说得通了。
这是一个我发现的小技巧，它使得编写有状态的并发应用程序变得更容易，特别是对于网络应用程序。让我们看一个虚构的有状态服务器。
每个当前连接的客户端都有一个线程，允许客户端更新状态。
服务器也有一个主逻辑线程，它也转换状态。
所以你想允许客户端更新程序的状态。
有时将程序的整个状态暴露在 TVar 中非常简单和容易，但我发现这会变得非常混乱，尤其是当状态的定义发生变化时！
此外，如果你必须执行任何条件操作，这也会非常烦人。
所以为了帮助整理（假设你的状态称为 World）
在状态上创建一个 Monad
[edit | edit source]首先，在 World 类型上创建一个 Monad
import Control.Monad.State.Lazy
-- heres yer monad -- it can liftIO too type WorldM = StateT World IO
data World =
World { objects :: [ WorldObject ] }
现在你可以在 WorldM 中编写一些访问器
-- maybe you have a bunch of objects each with a unique id import Data.Unique import Data.Maybe import Prelude hiding ( id )
data WorldObject =
WorldObject { id :: Unique }
-- check Control.Monad.State.Lazy if you are confused about get and put addObject :: WorldObject -> WorldM ( ) addObject wO = do wst <- get put $ World $ wO : ( objects wst )
-- presuming unique id
getObject :: Unique -> WorldM ( Maybe WorldObject )
getObject id1 = do
wst <- get
return $ listToMaybe $ filter ( \ wO -> id wO == id1 )
( objects wst )
现在这里有一个类型代表对 World 的更改
data WorldChange = NewObj WorldObject |
UpdateObj WorldObject | -- use the unique ids as replace match
RemoveObj Unique -- delete obj with named id
看起来剩下要做的就是
type ChangeBucket = TVar [ WorldChange ]
mainLoop :: ChangeBucket -> WorldM ( )
mainLoop cB =
-- do some stuff
-- it's probably fun
-- using your cheeky wee WorldM accessors
mainLoop cB -- recurse on the shared variable
记住，你的主线程是 World 和 IO 的转换器，所以它可以“原子地”运行并读取 changeBucket。
现在，假设你有一个函数可以将 WorldChange 合并到现有的 WorldM 中，你的“等待客户端输入”线程可以与程序的主线程通信，而且它看起来并不那么糟糕。
使对状态的外部更改本身成为 Monadic
[edit | edit source]然而！由于你的主线程中的所有状态现在都对程序的其余部分隐藏，并且你通过单向通道进行通信——数据从客户端到服务器，但主循环保持其状态秘密——你的客户端线程将永远无法做出关于环境的条件选择——客户端线程在 IO 中运行，但主线程在 WorldM 中运行。
所以你共享变量的真正类型是
type ChangeBucket =
TVar [ WorldM ( Maybe WorldChange ) ]
这可以从客户端输入线程生成，但你将能够在代码中包含条件语句，这些语句只在从主线程运行时针对状态进行评估。
这一切听起来有点随机，但这让我的生活变得容易多了。这里有一些基于这个想法的真实工作代码
- 它从客户端获取命令，并尝试更改游戏状态中表示客户端的对象。
- 然后将此函数的输出写入 ChangeBucket（使用本节中定义的 ChangeBucket，上面）并在游戏主循环的 DState 中运行。
（你可能想在脑海中用 DState 替换 WorldM）
-- cmd is a command generated from parsing network input
mkChange :: Unique -> Command -> DState ( Maybe WorldChange )
mkChange oid cmd = do
mp <- getObject oid -- this is maybe an object, as per the getObject definition earlier in the article
-- enter the maybe monad
return $ do p <- mp -- if its Nothing, the rest will be nothing
case cmd of
-- but it might be something
Disconnect ->
Just $ RemoveObject oid
Move x y ->
Just $ UpdateObject $ DO ( oid )
( name p )
( speed p )
( netclient p )
( pos p )
[ ( x , y ) ]
( method p )
一些说明和更多想法。
[edit | edit source]另一种设计可能只是有
type ChangeBucket = TVar [ WorldM ( ) ]
因此，只需在它们运行时更新游戏世界。我还有其他用途 WorldM (Maybe Change) 类型。
所以我的结论是——我只有我的 Monad 和我的话，所以去有创意地使用你的 Monad 并编写一些电脑游戏 ;)
 |
本节是一个存根。你可以通过扩展它来帮助Haskell。 |