将括号的字符串解析为 Haskell 中的嵌套列表

Question

我的目标是编写一个函数来将嵌套括号的字符串解析为相应的列表：

parseParens "()" --> []
parseParens "(())" --> [[]]
parseParens "((()()))" --> [[[],[]]]

首先我发现我无法轻松指定定义 return 值的类型。我可以这样做：

parseParens :: String -> [[[[t]]]]

可是怎么说是无限嵌套呢？我想 Haskell 不允许这样做。

我的解决方案

我想出了自己的数据类型：

data InfiniteList = EmptyList | Cons InfiniteList InfiniteList deriving (Show)

和一个使用这个的解析器函数：

parseParens :: String -> InfiniteList
parseParens ('(':xs) =
    if remainder == ""
        then result
        else error "Unbalanced parenthesis"
    where (result, remainder) = parseToClose EmptyList xs
parseParens _ = error "Unbalanced parenthesis"

parseToClose :: InfiniteList -> String -> (InfiniteList, String)
parseToClose acc "" = error "Unbalanced parenthesis!"
parseToClose acc (')':xs) = (acc, xs)
parseToClose acc ('(':xs) = parseToClose (concatInfLists acc (Cons result EmptyList)) remainder
    where (result, remainder) = parseToClose EmptyList xs

concatInfLists :: InfiniteList -> InfiniteList -> InfiniteList
concatInfLists EmptyList ys = ys
concatInfLists (Cons x xs) ys = Cons x (concatInfLists xs ys)

像这样工作：

parseParens "()" --> EmptyList
parseParens "(())" --> Cons EmptyList EmptyList
parseParens "((()()))" --> Cons (Cons EmptyList (Cons EmptyList EmptyList)) EmptyList

如何改进？

肯定有更好的方法来做到这一点。也许甚至有一种方法可以为此使用内置的 List 数据类型？

Answer 1

编辑：修正了我对本杰明回答的错误描述。

@Benjamin Hodgson 评论中的答案：

data Nested a = Flat a | Nested (Nested [a]) deriving (Show)

提供了一种表示任意嵌套深度的同质列表的好方法（即，有点像 [a] 加上 [[a]] 加上 [[[a]]] 加上所有其余部分的总和类型），这似乎是您问题的不寻常表示，特别是在这样的情况下：

parseParens "(()(()))"

"child nodes" 的嵌套深度不同。这将表示为：

Nested (Nested (Nested (Flat [[],[[]]]))) :: Nested a

所以它确实允许您将解析结果表示为所需的列表，给定足够的 Nested 构造函数，但它有一些奇怪的属性。例如，最里面的空列表实际上有不同的类型：第一个是 [[a]] 类型，第二个是 [a].

类型

作为替代方法，我认为您实际上想要的数据类型可能只是：

data Nested = N [Nested] deriving (Show)

其中每个节点 N 是一个（可能为空的）节点列表。然后，你会得到：

> parseParens "()"
N []
> parseParens "(())"
N [N []]
> parseParens "((()()))"
N [N [N [],N []]]
> parseParens "(()(()))"
N [N [],N [N []]]

如果您只是忽略这些结果中的 N 构造函数，则前三个构造函数与问题开头的 "corresponding list" 个测试用例相匹配。

附带说明：上面的 Nested 数据类型实际上是 "rose tree" 不包含任何数据，相当于 Tree () 使用 Tree 数据类型 Data.Tree 在 containers 包中。

最后，我怎么强调学习和使用 monadic 解析库的帮助都不为过，即使对于简单的解析工作也是如此。例如，使用 parsec 库，您可以在一行中为您的语法编写一个解析器：

nested = N <$> between (char '(') (char ')') (many nested)

我 parseParens 的完整代码是：

import Data.Tree
import Text.Parsec
import Text.Parsec.String

data Nested = N [Nested] deriving (Show)

nested :: Parser Nested
nested = N <$> between (char '(') (char ')') (many nested)

parseParens :: String -> Nested
parseParens str =
  let Right result = parse (nested <* eof) "" str
  in  result

将括号的字符串解析为 Haskell 中的嵌套列表

Parsing String of parenthesis to nested List in Haskell

parsing

haskell

list

infinite

我的解决方案

如何改进？