Haskell: recursive data type - parse [String] into n-ary tree
I'm trying to parse a list of strings into an n-ary tree, which is defined as:
data Tree = Leaf Int | Node [Tree] deriving (Show)
If I have [String] = ["(", "1", "(", "2", "3", ")", ")"]
, I want this to be parsed into a tree with Node with one Sheet (1) and another nested Node with other Sheets (2, 3).
I've tried for a couple of days, but I can't seem to think about inserting an arbitrary number of children. Earlier I wrote an AST for simple grammar, but then I had a number of children already defined in Data.
[String] in "(Tree, [String])" is for keeping track of strings that have not yet been parsed.
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?
I would really appreciate some help or some hints to get me a little further.
source to share
Let's change the bit in the resulting type from (Tree, [String])
to [Tree]
.
We use an extra argument as an accumulator and use recursion:
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)
source to share