我正在嘗試通過 Haskell 撰寫一個簡單的決議器，但陷入了無限回圈。代碼是：
import Control.Applicative (Alternative, empty, many, (<|>))
data Parser a = Parser {runParser :: String -> [(a, String)]}
instance Functor Parser where
fmap f (Parser p) = Parser $ \s -> [(f x', s') | (x', s') <- p s]
instance Applicative Parser where
pure x = Parser $ \s -> [(x, s)]
(Parser pf) <*> (Parser p) = Parser $ \s -> [(f' x, ss') | (f', ss) <- pf s, (x, ss') <- p ss]
instance Alternative Parser where
empty = Parser $ \s -> []
(Parser p1) <|> (Parser p2) = Parser $ \s ->
case p1 s of
[] -> p2 s
xs -> xs
singleSpaceParser :: Parser Char
singleSpaceParser = Parser $ \s ->
( case s of
x : xs -> if x == ' ' then [(' ', xs)] else []
[] -> []
)
multiSpaceParser :: Parser [Char]
multiSpaceParser = many singleSpaceParser
我只是在 ghci 中加載這個檔案，然后運行：
runParser multiSpaceParser " 123"
我希望它得到[(" ", "123")]，但實際上它有一個無限回圈
我用trace來除錯，好像many是錯的
我該如何修復這個錯誤？
uj5u.com熱心網友回復：
讓我們假設
many p = (:) <$> p <*> many p <|> pure []
并考慮電話
many singleSpaceParser " 123"
（字串在這里實際上并不重要，many singleSpaceParser呼叫將始終回圈。）
一個還原步驟產量
((:) <$> singleSpaceParser <*> many singleSpaceParser <|> pure []) " 123"
現在觀察到，為了減少對 的呼叫(<|>)，我們必須評估 to 的兩個引數(<|>)的形狀Parser ...。
讓我們考慮為(:) <$> singleSpaceParser <*> many singleSpaceParser. (<$>)和兩者(<*>)一樣infixl 4，這是<*>最外層的應用程式。
但現在觀察到，為了減少(<*>)，我們再次必須評估兩個引數(<*>)的形狀Parser ...，特別是遞回呼叫many singleSpaceParser。
這就是我們得到無限回圈的地方。
通過切換data到newtype（或者，至少避免Parser在所有第二個引數中對建構式進行積極的模式匹配），可以避免這些問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/495981.html