Haskell：递归数据类型 - 将[字符串]解析为n叉树

Question

我将尝试将一组字符串解析为一个n叉树，该树的定义如下：

data Tree = Leaf Int | Node [Tree] deriving (Show)

如果我有一个 [String] = ["(", "1", "(", "2", "3", ")", ")"]，我希望将其解析成一棵树，其中包含具有一个叶子节点 1 和另一个嵌套节点的节点，该节点具有其他叶子 (2、3)。

我已经尝试了几天，但我无法理解如何插入任意数量的子节点。我之前为简单的语法编写了一棵 AST，但是在 Data 中已经定义了子节点的数量。

"(Tree, [String])" 中的 [String] 是用来跟踪尚未解析的字符串的。

data Tree = Leaf Int | Node [Tree] deriving (Show)
tree :: [String] -> (Tree, [String])
tree [] = error "I can't let you do that, Dave"
tree (x:xs) | all isDigit x = (Leaf (read x), xs)
            | -- <- Node?

我很希望能得到一些帮助或提示，以便让我有些进展。

- Spaceburger

---

我喜欢 tree [] = error "我不能让你这样做，Dave"。 - AndrewC

Answer 1

让我们将结果类型从(Tree，[String])稍作更改为[Tree]。

我们使用附加参数作为累加器，并进行递归：

tree :: [String] -> [Tree]
tree xs = let (Node ts, zs) = treenode (xs ++ ")") [] in ts

treenode :: [String] -> [Tree] -> (Tree, [String])
treenode []       _  = error "I can't let you do that, Dave"
treenode ("(":xs) ts = let (n, xs') = treenode xs [] in treenode xs' (n : ts)
treenode (")":xs) ts = (Node ts, xs)
treenode (x:xs)   ts = treenode xs (Leaf (read x) : ts)

- viorior

---

谢谢，那真的帮了很多。 - Spaceburger