对前 n 个字符应用解析器 n 次 (Haskell)

Question

我正在研究 Haskell 中的解析器，遵循 G. Hutton, E. Meijer - Monadic Parsing in Haskell.

中的定义

data Parser a = Parser { parseWith :: String -> [(a, String)] }

instance Functor Parser where
    fmap f (Parser p) = Parser $ \s -> [(f a, rest) | (a, rest) <- p s]

instance Applicative Parser where
    pure x = Parser $ \s -> [(x, s)]
    (Parser p1) <*> (Parser p2) = Parser $ \s -> [(f x, r2) | (f, r1) <- p1 s, (x, r2) <- p2 r1]

instance Monad Parser where
    return = pure
    p >>= f = Parser $ \s -> concatMap (\(x, r) -> parseWith (f x) r) $ parseWith p s

instance Alternative Parser where
    empty = failure
    p1 <|> p2 = Parser $ \s ->
        case parseWith p1 s of
        []  -> parseWith p2 s
        res -> res

基本上我有一个 (parsed :: a, remaining :: String) 上下文。

作为一个简单的应用程序，我定义了以下ADT来解析：

data Arr = Arr Int [Int] -- len [values]

和一个可以从字符串构造 Array 值的解析器，例如：

"5|12345" -> Arr 5 [1,2,3,4,5]

首先，为了解析n这样的Array值（字符串输入在第一个位置包含n），例如：

"2 3|123 4|9876 2|55" -> [Arr 3 [1,2,3], Arr 4 [9,8,7,6]]

我可以做到以下几点：

arrayParse :: Parser Arr
arrayParse = do
    len <- digitParse
    vals <- exactly len digitParse
    return $ Arr len vals

nArraysParse :: Parser [Arr]
nArraysParse = do
    n <- digitParse
    exactly n arrayParse

其中 exactly n p 通过应用 p n 次构造一个新的解析器。

接下来，我想解析一个不同的方案。假设第一个字符表示定义数组的子字符串的 长度，例如：

"9 3|123 4|9876 2|55" -> [Arr 3 [1,2,3], Arr 4 [9,8,7,6]]

意味着我必须在前 n 个字符（不包括 | 和空格）上应用 arrayParse 以获得前 2 个数组：

3|123 -> 4 chars (excluding | and whitespace) 4|9876 -> 5 chars (excluding | and whitespace)

因此，应用解析器 n 次 很简单：

exactly :: Int -> Parser a -> Parser [a] exactly 0 _ = pure [] exactly n p = do v <- p -- apply parser p once v' <- exactly (n-1) p -- apply parser p n-1 times return (v:v')

但是我如何表达 对前 n 个字符应用解析器的意图？

我最初的方法是这样的：

foo :: Parser [Arr] foo = do n <- digitParse substring <- consume n -- what to do with substring? -- can I apply arrayParse on it?

我该如何处理？

Answer 1

按照@jlwoodwa的建议，我实现了以下目标：

innerParse :: Parser a -> String -> Parser a
innerParse p s = case parseWith p s of
    [(arr, "")] -> return arr
    _ -> failure

substringParse :: Parser [Arr]
substringParse = do
    n <- digitParse
    substring <- consume n
    innerParse (zeroOrMore arrayParse) substring

适用于我的用例。

对前 n 个字符应用解析器 n 次 (Haskell)

Apply parser n times vs on the first n characters (Haskell)

parsing

haskell