sat函数中出现"Programming In Haskell“错误

Question

我在Graham Hutton的Haskell编程的第8章中，我正在复制代码并在GHC中测试它。

请在此处查看幻灯片：http://www.cis.syr.edu/~sueo/cis352/chapter8.pdf特别是幻灯片15

到目前为止我复制的相关代码是：

type Parser a = String -> [(a, String)]
pih_return :: a -> Parser a
pih_return v = \inp -> [(v, inp)]
failure :: Parser a
failure = \inp -> []
item :: Parser Char
item = \inp -> case inp of
                    [] -> []
        (x:xs) -> [(x,xs)]
parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp
sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then pih_return x else failure

我已经将return函数的名称从书中更改为pih_return，这样它就不会与Prelude return函数冲突。

错误在最后一个函数sat中。这是我直接从书上抄来的。

正如你可能看到的，p是一个从Char到Bool的函数(例如isDigit)，而x是[(Char, String)]类型的，所以这是第一个错误。

然后pih_return接受一个值v并返回[(v, inp)]，其中inp是一个String。这会在sat中导致错误，因为传递的v是x，而不是Char。

通过将inp显式地包含到sat中，我提出了这个解决方案

sat :: (Char -> Bool) -> Parser Char
sat p inp = do x <- item inp
               if p (fst x) then pih_return (fst x) inp else failure inp

这是解决问题的最好方法吗？

Answer 1

第一个sat不能工作，Parser必须是monad才能使用do表示法。为了使其成为monad实例，必须使用newtype。

我并不拥有这本书，但我猜作者想从一个简单的解析器类型开始，然后将其扩展到一个完整的Parser，我怀疑您将非一元版本的定义与monad monad之一(sat)混淆了，并在此过程中错过了monad实例声明。

这里有可用on the author's web site一章中的代码，其中为Parser定义了一个monad实例。

如果您必须为简单的Parser类型编写sat函数，我宁愿使用lambda风格(如item)，并且完全避免使用monad(您注意到最初的sat的do块是Parsermonad，而您的是List monad?)。我认为您的sat版本中有一个bug :我认为它应该是<do>d17Parser>。

Answer 2

如果没有monad，就不能使用do表示法；除非使用data或newtype，否则不能创建monad实例；如果不引入烦人的值构造函数，就不能使用data或newtype。毫无疑问，值构造函数被省略了，因为它很烦人。

在下面的示例中，您可以看到我使用了newtype并引入了烦人的值构造函数Parser。这就是instance声明工作的原因，此时您不仅可以使用do-notation，还可以使用标准的一元return和fail。

此代码编译时不会出现错误或警告：

module P
where

newtype Parser a = Parser (String -> [(a, String)])
instance Monad Parser where
  return a = Parser $ \inp -> [(a, inp)]
  fail _   = Parser $ \_   -> []
  Parser f >>= k = Parser $ \inp -> 
     [(b, inp'') | (a, inp') <- f inp, let Parser g = k a, (b, inp'') <- g inp']

item :: Parser Char
item = Parser $ \inp -> case inp of
                          [] -> []
                          (x:xs) -> [(x,xs)]
parse :: Parser a -> String -> [(a, String)]
parse (Parser p) inp = p inp
sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then return x else fail "predicate not satisfied"

Answer 3

这些幻灯片缺少Parser类型的Monad类型类的实现。

使用该声明，do表示法是正确的；x <- item实际上执行了从[(Char, String)]到(Char, String)的正确解包。

如果不编译它来查看错误，我似乎无法获得这个定义，但这是一个开始：

instance Monad (Parser a) where
  return x = pih_return x
  -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
  p >>= f = \inp -> case p inf of
                      [] -> []
                      (x:xs) -> (f x) xs -- this line is probably wrong
  fail message = [] -- message is ignored