I have the following implementation of a rose tree:

data Rose a = Empty | Branch a [Rose a] deriving (Show, Eq)

So I wanna get all of the paths in the tree, what I have done so far is the following:

paths :: Rose a -> [[a]]
paths Empty = [[]]
paths (Branch n []) = [[n]]
paths (Branch n ns) = map ((:) n . concat . paths) ns

This is my tree

sample2:: Rose String
sample2 = Branch "/" [Branch "dir1" [Branch "file1" [Empty], Branch "dir3" [Empty]], Branch "dir2" [Branch "file2" [Empty], Branch "file3" [Empty]]]

And the output of paths sample2 is the following: [["/","dir1","file1","dir1","dir3"],["/","dir2","file2","dir2","file3"]]

But I want it to be :

[["/","dir1","file1"],["/", "dir1","dir3"],["/","dir2","file2"],["/", "dir2","file3"]]

How to achieve this result?

CodePudding user response：

You should concatenate the end product, not the paths of the individual childs, so:

paths :: Rose a -> [[a]]
paths Empty = [[]]
paths (Branch n []) = [[n]]
paths (Branch n ns) = concatMap (map (n :) . paths) ns

CodePudding user response：

paths :: Rose a -> [[a]]
paths Empty = [[]]
paths (Branch n ns) = map (n :) (concat $ map paths ns)