0

我试图理解解析器。因此，我创建了自己的解析器。不幸的是，它不起作用。为什么？

type Parser a = String -> [(a, String)]

preturn :: a -> Parser a 
preturn t = \inp -> [(t,inp)] 

pfailure :: Parser a 
pfailure = \inp -> []

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


parse :: Parser a -> Parser a 
--parse :: Parser a -> String -> [(a,String)]

parse p inp = p inp

{-
combine :: Parser a -> Parser b -> Parser (a,b)
combine p1 p2 = \inp -> p2 t output
    where
        p1 inp = ([


-}
-- firstlast :: Parser (Char,Char)
firstlast = do 
    x <- pitem
    z <- pitem
    y <- pitem
    preturn (x,y)

another = do
    x <- pitem
    y <- pitem

Firstlast 应该接受一个字符串并返回第一个和第三个字符。不幸的是，它返回奇数值，并且它不接受它的类型（Parser (Char,Char)）

例如，

*Main> firstlast "abc"
[(([('a',"bc")],[('a',"bc")]),"abc")]

应该发生的是：

*Main> firstlast "abc"
[("ac",[])]
4

1 回答 1

8

请使用可编译的代码。你的another功能没有。

有什么问题？

您的代码用于firstlast并another使用do-notation。而你在pitem这里使用的方式，看起来好像你期望Parser成为一个单子。但它不是，至少不是你期望的那样。

有一个预定义的 monad 实例使 GHC 认为这Parser是一个 monad，即

instance Monad ((->) r) where
  return = const
  f >>= k = \ r -> k (f r) r

这个实例的意思是，对于任何类型r，函数类型r -> ...都可以被认为是一个 monad，即通过将参数分布在任何地方。因此，在这个 monad 中返回一些东西相当于产生一个忽略 type 参数的值r，并且绑定一个值意味着您r将它获取并传递给左右计算。

这不是您想要的解析器。输入字符串将分发给所有计算。所以每个pitem都会对原始输入字符串进行操作。此外，作为

pitem :: String -> [(Char, String)]

你的一元计算的结果将是 type [(Char, String)]，所以x和y都是这种类型。这就是你得到结果的原因

[(([('a',"bc")],[('a',"bc")]),"abc")]

您在pitem同一个输入字符串上调用了三次。你把两个结果放在一对中，你就是preturn在做整个事情。

如何解决？

您需要为该Parser类型定义自己的 monad 实例。你不能直接这样做，因为Parser是类型同义词，并且类型同义词不能部分应用，所以你不能写

instance Monad Parser where
  ...

相反，您必须包装Parser一个新的数据类型或新类型：

newtype Parser a = Parser { parse :: String -> [(a, String)] }

这为您提供了一个构造函数Parser和一个函数parse，用于在未包装和已包装的解析器类型之间进行转换：

Parser :: String -> [(a, String)] -> Parser a
parse  :: Parser a -> String -> [(a, String)]

这意味着您必须调整其他功能。例如，preturn变成

preturn :: a -> Parser a 
preturn t = Parser (\inp -> [(t,inp)])

变化pfailure和pitem类似。然后，您必须定义Monad实例：

instance Monad Parser where
  return = preturn
  (>>=)  = ... -- to be completed by you

该函数(>>=)不包含在您上面的代码中。您需要实现将输入传递给第一个解析器的行为，并且对于每个结果，结果和剩余的输入都传递给(>>=). 完成此操作后，调用parse firstlast "abc"将产生以下结果：

[(('a','c'),"")]

这不是你想要的问题，但我相信这就是你真正想要的。

于 2013-10-14T19:00:24.917 回答