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

1 answer

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)




All Articles