使用GHCi的Haskell中的函数解析器示例

Question

我是学习Haskell的初学者。这是使用GHCi时遇到的问题。

p :: Parser (Char, Char) 
p = do x <- item 
     item 
     y <- item 
     return (x,y) 

item :: Parser Char 
item = P (\inp -> case inp of 
         []  -> [] 
         (x:xs) -> [(x,xs)]) 

产品另一个语法分析器，其中项目::分析器CHAR，简单地产品当我加载文件解析字符串

然后执行

parse p "abcdef" 

然后将execption所示：

*** Exception: You must implement (>>=) 

解决这个问题的任何想法？

---

更新信息：

解析器定义如下：

newtype Parser a = P (String -> [(a,String)]) 

instance Monad Parser where 
    return  :: a -> Parser a 
    return v = P (\inp -> [(v,inp)]) 

    (>>=)  :: Parser a -> (a -> Parser b) -> Parser b 
    p >>= f  = --... 

Answer 1

为了使用do符号，你Parser必须是Monad一个实例：

instance Monad Parser where 
    return :: a -> Parser a 
    return = -- ... 
    (>>=) :: Parser a -> (a -> Parser b) -> Parser b 
    p >>= f = -- ... 

编译器需要你o填写return和>>=的定义。

do符号是脱糖使用>>=（发音为“bind”）的合成糖。例如，你的代码desugars到：

p :: Parser (Char, Char) 
p = item >>= \x -> 
    item >>= \_ -> 
    item >>= \y -> 
    return (x,y) 

或者，用更为露骨的括号：

p = item >>= (\x -> item >>= (\_ -> item >>= (\y -> return (x,y)))) 

>>=介绍如何在Parser a连同功能a -> Parser b结合起来，创造一个新的Parser b。

使用您的Parser定义，工作Monad实例

instance Monad Parser where 
    return a = P $ \s -> [(a,s)] 
    p >>= f = P $ concatMap (\(a,s') -> runParser (f a) s') . runParser p 
    -- which is equivalent to 
    -- p >>= f = P $ \s -> [(b,s'') | (a,s') <- runParser p s, (b,s'') <- runParser (f a) s'] 

考虑一下>>=确实在p :: Parser a方面和功能f :: a -> Parser b。

• 解开时，p需要String，并返回(a,String)对

  runParser p :: String -> [(a,String)] 
  

• 每个(a,String)对，我们可以在a运行f得到一个新的解析器q列表：

  map go . runParser p :: String -> [(Parser b,String)] 
      where go :: (a, String) -> (Parser b, String) 
       go (a,s') = let q = f a in (q, s') 
  

• 如果我们解开q，我们得到了一个函数，它接受一个String并返回(b, String)双列表：

  map go . runParser p :: String -> [(String -> [(b,String)],String)] 
      where go :: (a, String) -> (String -> [(b,String)],String) 
       go (a,s') = let q = f a in (runParser q, s') 
  

• 我们可以运行上是与a配对的String该功能让我们的`名单（B，弦乐立即对）：

  map go . runParser p :: String -> [[(b,String)]] 
      where go :: (a, String) -> [(b,String)] 
       go (a,s') = let q = f a in runParser q s' 
  

• ，如果我们弄平列表中，列出了结果，我们得到一个String -> [(b,String)]，这仅仅是解开Parser b

  concat . map go . runParser p :: String -> [(b,String)] 
      where go :: (a, String) -> [(b,String)] 
       go (a,s') = let q = f a in runParser q s'