parsing - 使用替代方案的纯应用解析器

Question

在之前的post中，一位用户为 Haskell 提供了一个纯应用解析器的实现(代码最初来自 here )。下面是该解析器的部分实现:

{-# LANGUAGE Rank2Types #-}

import Control.Applicative (Alternative(..))
import Data.Foldable (asum, traverse_)

类型:

newtype Parser a = Parser {run :: forall f. Alternative f => (Char -> f ()) -> f a}

实例:

instance Functor Parser where
    fmap f (Parser cont) = Parser $ \char -> f <$> cont char

instance Applicative Parser where
    pure a = Parser $ \char -> pure a
    (Parser contf) <*> (Parser cont) = Parser $ \char -> (contf char) <*> (cont char)

instance Alternative Parser where
    empty = Parser $ \char -> empty
    (Parser cont) <|> (Parser cont') = Parser $ \char -> (cont char) <|> (cont' char)
    some (Parser cont) = Parser $ \char -> some $ cont char
    many (Parser cont) = Parser $ \char -> many $ cont char

一些示例解析器:

item = Parser $ \char -> asum $ map (\c -> c <$ char c) ['A'..'z']
digit = Parser $ \char -> asum $ map (\c -> c <$ char (head $ show c)) [0..9]
string s = Parser $ \char -> traverse_ char s

不幸的是，我很难理解如何使用这个解析器实现。特别是，我不明白 Char -> f () 应该/可能是什么，以及如何使用它来进行简单的解析，例如从输入字符串中额外添加一个数字。如果可能的话我想要一个具体的例子。有人可以解释一下吗？

Answer 1

在 forall f. Alternative f => (Char -> f ()) -> f a ，Char -> f ()是您提供的东西。如果您选择接受它，您的任务就是将其变成 f a仅使用这两位:

• Char -> f ()函数(即解析单个字符的方法:如果下一个字符与参数匹配，则解析成功；否则解析失败。)
• Alternative f 的实例

那么如何将单个数字解析为 Int ？它必须采用以下形式

digit :: Parser Int
digit = Parser $ \parseChar -> _

在 _ ，我们必须创建一个 f Int使用套件parseChar :: Char -> f ()和Alternative f 。我们知道如何解析单个 '0'字符:parseChar '0'当且仅当下一个字符是 '0' 时成功。我们可以把它变成值Int通过f的Functor实例，到达

digit0 :: Parser Int
digit0 = Parser $ \parseChar -> fmap (const 0) (parseChar '0')

但是f不仅仅是Functor ，也是 Alternative ，所以我们可以写 digit长格式为

digit :: Parser Int
digit = Parser $ \parseChar -> fmap (const 0) (parseChar '0') <|>
                               fmap (const 1) (parseChar '1') <|>  
                               fmap (const 2) (parseChar '2') <|>  
                               fmap (const 3) (parseChar '3') <|>  
                               fmap (const 4) (parseChar '4') <|>  
                               fmap (const 5) (parseChar '5') <|>  
                               fmap (const 6) (parseChar '6') <|>  
                               fmap (const 7) (parseChar '7') <|>  
                               fmap (const 8) (parseChar '8') <|>  
                               fmap (const 9) (parseChar '9')

从这里开始，这只是一个简单的 Haskell 编程的问题，以减少多余的东西，达到类似的效果

digit :: Parser Int
digit = Parser $ \parseChar -> asum [fmap (const d) (parseChar c) | d <- [0..9], let [c] = show d]

我们可以通过注意到 fmap (const x) f 来进一步简化。可以写成x <$ f ，给予

digit :: Parser Int
digit = Parser $ \parseChar -> asum [d <$ parseChar c | d <- [0..9], let [c] = show d]