我想根據John Hughes的論文Generalizing Monads to Arrows.當通讀并試圖重新實作他的代碼時，我發現有些東西不太合理。在其中一節中，他根據Swierstra和Duponchel的論文使用Arrows的確定性、糾錯組合器決議器列出了一個決議器實作。他所描述的決議器型別看起來是這樣的：
data StaticParser ch = SP Bool [ch]
data DynamicParser ch a b = DP （a, [ch]) -> (b, [ch])。
data Parser ch a b = P (StaticParser ch) title">ch）（DynamicParser ch a b）
組成運算子看起來像這樣：
(.) :: Parser ch b c -> Parser ch a b -> Parser ch a c
P (SP e2 st2) (DP f2) 。P (SP e1 st1) (DP f1) =
P (SP (e1 && e2) (st1 `union` if e1 then st2 else [ ] )
(DP $ f2 . f1)
問題是決議器的組成q . p"忘記 "了q的起始符號。我想到的一個可能的解釋是，Hughes'希望我們所有的DynamicParser都是總的，這樣一個符號分析器的型別簽名將是symbol :: ch -> Parser ch a (Maybe ch)而不是symbol :: ch -> Parser ch a ch。但這仍然顯得很笨拙，因為我們必須在StaticParser和DynamicParser中重復放置起始符號資訊。另一個問題是，幾乎所有的決議器都有可能拋出，這意味著我們將不得不在Maybe或Either中花費大量的時間，這實質上是 "單體不組成問題"。這可以通過重寫DynamicParser本身來處理失敗，或者作為Arrow transformer,來補救，但這已經偏離了論文的內容。論文中沒有提到這些問題，而且決議器被介紹得好像它顯然是有效的，所以我覺得我一定是錯過了一些基本的東西。如果有人能抓住我遺漏的東西，那將是非常有幫助的。
uj5u.com熱心網友回復：
我認為Swierstra和Duponcheel所描述的確定性分析器與傳統的分析器有些不同：他們根本不處理失敗，只處理選擇。
也請看S&D論文中的invokeDet函式：
invokeDet :: Symbol s => DetPar s a -> Input s -> a
invokeDet (_, p) inp = case p inp [] of （a, _）-> a
這個函式顯然假定它總是能夠找到一個有效的決議。
使用 Hughes 所描述的箭頭版本的決議器，你可以寫一個這樣的例子：
main = do
let p = symbol 'a' >> > (symbol 'b' < > symbol 'c')
print $ invokeDet p "ab".
print $ invokeDet p "ac".
這將列印預期：
'b'
'c'
然而，如果你寫一個 "失敗的 "決議：
main = do
let p = symbol 'a' >> > (symbol 'b' < > symbol 'c')
print $ invokeDet p "ad"。
它仍然會列印：
'c'
為了使這種行為更加合理，Swierstra和Duponcheel還引入了糾錯功能。如果我們假設輸入中的錯誤字符d已經被糾正為c，那么輸出'c'就是預期的。這需要一個額外的機制，而這個機制可能過于復雜，無法包含在 Hughes 的論文中。
我在這里上傳了我用來獲得這些結果的實作。https://gist.github.com/noughtmare/eced4441332784cc8212e9c0adb68b35
關于同一風格的更實用的決議器的更多資訊（但不再是確定性的，也不再限于LL(1)），我非常喜歡"組合器決議。A Short Tutorial"，作者Swierstra。從第9.3節摘錄了一段有趣的內容：
這里的一個微妙之處在于如何處理單體分析器的問題。正如我們在[13]中所描述的，靜態分析與單體計算并不相配，因為在這種情況下，我們會根據迄今為止產生的輸入動態地建立新的決議：靜態分析的整個想法就是它是靜態的。這一觀察導致John Hughes提出了處理這種情況的箭頭[7]。直到最近，我們才意識到，盡管我們的論點在一般情況下仍然成立，但它們并不適用于LL(1)分析的情況。如果我們想計算能被p >>= q形式的決議器識別為第一個符號的符號，那么我們只對右手邊的起始符號感興趣，如果左手邊能識別空字串的話；好訊息是，在這種情況下，我們靜態地知道將回傳什么值作為見證，并可以將這個值傳遞給q，也可以靜態地分析這個呼叫的結果。不幸的是，我們將不得不采取特別的預防措施，以防左邊的運算子在其中一個空派生中包含對pErrors的呼叫，因為那樣的話，這個備選方案的見證就不再是可以靜態確定的了。
Swierstra 的完整決議器實作可以在 uu-parsinglib 包中找到，盡管我不知道有多少擴展在那里實作。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/316956.html
標籤：