parsing - 双递归函数中的 Haskell 类型错误

Question

我正在尝试定义一个贪婪的函数

greedy :: ReadP a -> ReadP [a]

解析一系列值，仅返回无法进一步扩展的“最大”序列。例如，

> readP_to_S (greedy (string "a" +++ string "ab")) "abaac"
[(["a"],"baac"),(["ab","a","a"],"c")]

我正在使用一种非常简单且可能很笨拙的方法。只需解析这些值，看看它们是否可以进一步解析；如果是，则再次重新应用该函数以获取所有可能的值并将其与先前的值连接，否则仅返回值本身。但是，似乎存在一些类型问题，下面是我的代码。

import Text.ParserCombinators.ReadP

addpair :: a -> [([a],String)] -> [([a],String)]
addpair a [] = []
addpair a (c:cs) = (a : (fst c), snd c ) : (addpair a cs)

greedy :: ReadP a -> ReadP [a]
greedy ap = readS_to_P (\s ->
    let list = readP_to_S ap s in 
    f list )
    where
        f :: [(a,String)] -> [([a],String)]
        f ((value, str2):cs) = 
            case readP_to_S ap str2 of
                [] -> ([value], str2) : (f cs)
                _ -> (addpair value (readP_to_S (greedy ap) str2)) ++ (f cs)

GHC 处理代码并说函数“f”的类型为 [(a1,String)] -> [([a1],String)]但贪婪是 ReadP a -> ReadP [a] .我想知道为什么会这样，因为我认为他们的类型应该同意。如果有人能想出一些聪明、更优雅的方法来定义函数贪婪，这也真的很有帮助(我的方法绝对是多余的)

Answer 1

要修复编译错误，您需要添加语言扩展

{-# LANGUAGE ScopedTypeVariables #-}

到您的源文件，或将相应的标志传递给编译器。您还需要更改 greedy 的类型签名到

greedy :: forall a. ReadP a -> ReadP [a]

这是因为你的两个 a类型变量实际上并不相同；它们在不同的范围内。随着扩展和 forall ，它们被视为相同的变量，并且您的类型正确统一。即便如此，代码也会出错，因为您在 f 的定义中没有详尽的模式匹配。 .如果添加

f [] = []

那么代码似乎按预期工作。
为了简化你的代码，我查看了提供的函数 munch , 定义为:

munch :: (Char -> Bool) -> ReadP String
-- ^ Parses the first zero or more characters satisfying the predicate.
--   Always succeeds, exactly once having consumed all the characters
--   Hence NOT the same as (many (satisfy p))
munch p =
  do s <- look
     scan s
 where
  scan (c:cs) | p c = do _ <- get; s <- scan cs; return (c:s)
  scan _            = do return ""

本着这种精神，您的代码可以重写为:

greedy2 :: forall a. ReadP a -> ReadP [a]
greedy2 ap = do
  -- look at the string
  s <- look
  -- try parsing it, but without do notation
  case readP_to_S ap s of
    -- if we failed, then return nothing
    [] -> return []
    -- if we parsed something, ignore it
    (_:_) -> do
      -- parse it again, but this time inside of the monad
      x <- ap
      -- recurse, greedily parsing again
      xs <- greedy2 ap
      -- and return the concatenated values
      return (x:xs)

这确实具有执行 ap 的速度劣势。需要两倍的频率；这对于您的用例来说可能太慢了。我确信我的代码可以进一步重写以避免这种情况，但我不是 ReadP专家。