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。 |