Haskell文本解析器组合器可以像正则表达式一样贪婪地解析范围

Question

在正则表达式中，您可以通过执行类似 d{1,5} 的操作来获取解析范围，这会贪婪地解析数字 1 到 5 次。或者你做d{1,5}?让它变得懒惰。

你会如何在Haskell的Text.ParserCombinators.ReadP中做到这一点？

我的尝试给出了这个：

rangeParse :: Read a => ReadP a -> [Int] -> ReadP [a]
rangeParse parse ranges = foldr1 (<++) $ fmap (n -> count n $ parse) ranges

如果你像rangeParse (satisfy isDigit) ([5,4..1])那样做，将执行 1 到 5 次数字的贪婪解析。而如果你交换数字顺序到[1..5]，你会得到一个延迟解析。

有没有更好或更惯用的方法可以使用解析器组合器来做到这一点？

Answer 1

更新：以下内容是错误的 - 例如 rangeGreedy 2 4 a <* string "aab"，相当于正则表达式a{2,4}aab，不匹配。 提问者的解决方案是正确的。 我不会删除答案，以防它阻止其他人犯同样的错误。

=======

==

这不是一个完整的答案，只是写贪婪的可能方式版本。 我还没有找到做懒惰版本的好方法。

定义一个返回 Maybes 的左偏option版本：

greedyOption :: ReadP a -> ReadP (Maybe a)
greedyOption p = (Just <$> p) <++ pure Nothing

然后，我们最多可以用其中的replicateM做n件事：

upToGreedy :: Int -> ReadP a -> ReadP [a]
upToGreedy n p = catMaybes <$> replicateM n (greedyOption p)

要允许最小计数，请单独执行必填部分并附加它：

rangeGreedy :: Int -> Int -> ReadP a -> ReadP [a]
rangeGreedy lo hi p = (++) <$> count lo p <*> upToGreedy (hi - lo) p

我的其余测试代码，以防对任何人都有用：

module Main where
import Control.Monad (replicateM)
import Data.Maybe (catMaybes)
import Text.ParserCombinators.ReadP
main :: IO ()
main = mapM_ go ["aaaaa", "aaaab", "aaabb", "aabbb", "abbbb", "bbbbb"]
   where
     go = print . map fst . readP_to_S test
test :: ReadP [String]
test = ((++) <$> rangeGreedy 2 4 a <*> many aOrB) <* eof
  where
    a = char 'a' *> pure "ay"
    aOrB = (char 'a' +++ char 'b') *> pure "ayorbee"