使用 parsec 解析递归数据

Question

import Data.Attoparsec.Text.Lazy
import Data.Text.Lazy.Internal (Text)
import Data.Text.Lazy (pack)
data List a = Nil | Cons a (List a)
list :: Text
list = pack $ unlines
  [ "0"
  , "1"
  , "2"
  , "5"
  ]

如何实现List Int解析器库德来解析list Cons 0 (Cons 1 (Cons 2 (Cons 5 Nil)))？

PS：不解析[Int]并将其转换为List Int的纯解析器更可取。

Answer 1

像这样：

import Control.Applicative
-- rest of imports as in question
data List a = Nil | Cons a (List a)
  deriving Show -- for testing
-- definition of list as in question
parseList :: Parser (List Int)
parseList = foldr Cons Nil <$> many (decimal <* endOfLine)

GHCi 检测：

*Main> parse parseList list
Done "" Cons 0 (Cons 1 (Cons 2 (Cons 5 Nil)))

Answer 2

无需从整数列表转换它：

import Data.Attoparsec.Text.Lazy
import Data.Text.Lazy (Text, pack)
import Control.Applicative
data List a = Nil | Cons a (List a)
  deriving Show
input :: Text
input = pack $ unlines [ "0", "1", "2", "5"]
list :: Parser (List Int)
list = cons <|> nil
  where
    cons = Cons <$> (decimal <* endOfLine) <*> list
    nil  = pure Nil 
main = print $ parse list input

如您所见，列表解析器看起来几乎与它正在解析的数据类型完全相同。

Answer 3

正如其他人指出的那样，您实际上不需要使用递归(尽管您可以(来解析列表。但是如果你有一个递归语法要解析，你可以在解析器中使用递归(参见 bzn 的答案和 Petr 的答案(，或者你可以递归解析器的结果(对于你在 Markdown 中看到的嵌套(。我在这里介绍的后者：http://www.youtube.com/watch?v=nCwG9ijQMuQ&t=17m32s

Answer 4

我想

说我们可以通过检查many'来做到这一点：

many' :: (MonadPlus m) => m a -> m [a]
many' p = many_p
  where
    many_p = some_p `mplus` return []
    some_p = liftM2' (:) p many_p

我们可以类似地制作自己的变体：

many'' :: (MonadPlus m) => m a -> m (List a)
many'' p = many_p
  where
    many_p = some_p `mplus` return Nil
    some_p = liftM2 Cons p many_p

并将其应用于任何一元解析器。

(请注意，many'使用自己的liftM2'，该在第一个操作的结果中是严格的。它不是由模块导出的，所以我使用了一个普通的liftM2。

或者我们可以制作一个更通用的变体来使用 Alternative ：

many'' :: (Alternative f) => f a -> f (List a)
many'' p = many_p
  where
    many_p = some_p <|> pure Nil
    some_p = Cons <$> p <*> many_p