How to get all the paths of a tree
Hello, I can't find the right recursive function to get a list of all the possible paths of a multi-way tree like this: data Tree= Node String [Tree] root = Node "root" [x, y] x = Node "x" [x1, x2] x1 = Node "x1" [] x2 = Node "x2" [x21, x22] x21 = Node "x21" [] x22 = Node "x22" [] y = Node "y" [] This is the Data.Tree.drawTree output: root | +- x | | | +- x1 | | | `- x2 | | | +- x21 | | | `- x22 | `- y And this is the list I'm trying to obtain: [ [x, x1] ,[x, x2, x21] ,[x, x2, x22] ,[y] ] Well, the actual problem I'm trying to solve is to print a set of lines like these: "leaf: x -> x1 \n" "leaf: x -> x2 -> x21 \n" ... and I thought I first need the list above. I'll be very grateful for any help Enrico
In this case, I think all you need is:
type Path = [String]
allPaths :: Path -> Tree -> [Path] allPaths p (Node s []) = [s:p] allPaths p (Node s subTrees) = concatMap (allPaths (s:p)) subTrees
paths = map reverse . allPaths []
In your test case, "root" will be at the beginning of each path produced, but you can map tail over the list if you don't want it. /g
participants (2)
-
J. Garrett Morris -
Santoemma Enrico