“Haskell编程”错误sat函数

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

这是解决问题的最佳方法是什么？

Answer 1

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

我没有这本书，但我想作者想从一个简单的解析器类型开始，然后将其扩展到一个完整的monad，我怀疑你已经混淆了一个非monadic版本的定义monad（sat），并且一路上错过了monad实例声明。

有章节可用的代码on the author's web site其中monad实例已被定义为Parser。

如果必须写的简单Parser型我宁愿做在λ-风格（如item），并完全避免单子一个sat功能（你是否注意到，原来sat的do块为Parser单子和你的是一个List monad？）。而我认为你有一个错误在你的sat版本：而不是pih_return (fst x) inp，我认为它应该是pih_return (fst x) (snd x)。

Answer 2

该幻灯片缺少Monad类型Parser类型的实施。

对于该声明，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 

Answer 3

不能使用do符号没有单子，你不能让一个除非您使用data或newtype，并且不能使用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 4

我读了非常同一本书，并试图做excercises当同样的问题来了。我恢复使用'do ...'符号到>> =。对于任何有兴趣的人，我都会使用nat函数。为了避免与前奏名称冲突，我在前面加上了所有我的函数并修改了>> = to >>> =。

type AParser a = String -> [(a, String)] 
areturn :: a -> AParser a 
areturn v = \inp -> [(v, inp)] 
afailure :: AParser a 
afailure = \inp -> [] 
aitem :: AParser Char 
aitem = \inp -> case inp of 
        [] -> [] 
        (x:xs) -> [(x, xs)] 
aparse :: AParser a -> String -> [(a, String)] 
aparse p inp = p inp 
(>>>=) :: AParser a -> (a -> AParser b) -> AParser b 
p >>>= f = \inp -> case aparse p inp of 
        [] -> [] 
        [(v, out)] -> aparse (f v) out 
(+++) :: AParser a -> AParser a -> AParser a 
p +++ q = \inp -> case aparse p inp of 
        [] -> aparse q inp 
        [(v, out)] -> [(v, out)] 
asat :: (Char -> Bool) -> AParser Char 
asat p = aitem >>>= (\x -> if p x then areturn x else afailure) 
adigit :: AParser Char 
adigit = asat isDigit 
amany :: AParser a -> AParser [a] 
amany p = amany1 p +++ areturn [] 
amany1 :: AParser a -> AParser [a] 
amany1 p = p >>>= (\v -> (amany p) >>>= (\vs -> areturn (v:vs))) 
anat :: AParser Int 
anat = amany1 adigit >>>= (\xs -> areturn (read xs))