哈斯克爾：遞歸數據類型 - 解析[字符串]爲n叉樹

Question

我試圖解析字符串列表爲N叉樹，其定義爲：

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

，如果我有[字符串] = ["(", "1", "(", "2", "3", ")", ")"]，我希望這被解析成一棵樹與一個葉子（1）和另一個葉子（2,3）嵌套的另一個節點的樹。

我一直在嘗試幾天，但我無法繞過插入任意數量的孩子。我之前曾爲一個簡單的語法編寫了AST，但之後我已經在數據中定義了一些兒童。

「（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? 

我真的很感謝一些幫助或一些提示，讓我更進一步。

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)