Get all of the children of a specific parent in a rose tree in Haskell

user_17588651 0
Viewed 103

I am trying to get all of the children of a specific root by a given name in Haskell.

The declaration of the tree:

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

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

and what I have tried:

childrenOf _ Empty = []
childrenOf name (Branch x xs) = if name == x then xs else childrenOf name xs

I want to call childrenOf "dir1" sample2 and get ["file1", "dir3"]

However, I get the error:

[1 of 1] Compiling Main ( tree.hs, interpreted )

tree.hs:47:1: error:
    * Couldn't match type Rose t' with [Rose t]'
      Expected type: t -> [Rose t] -> [Rose t]
        Actual type: t -> Rose t -> [Rose t]
    * Relevant bindings include
        childrenOf :: t -> [Rose t] -> [Rose t] (bound at tree.hs:47:1)
Failed, modules loaded: none.
haskell
1 Answers

You can obtain that are children of a given directory with:

childrenOf :: Eq a => a -> Rose a -> [Rose a]
childrenOf _ Empty = []
childrenOf name (Branch x xs) = if name == x then xs else concatMap (childrenOf name) xs

This will produce the direct branches of all Branches with the given name as Rose elements. You can also obtain the corresponding names with:

names :: [Rose a] -> [a]
names xs = [ x | Branch x _ <- xs ]

namesOfChildren :: Eq a => a -> Rose a -> [a]
namesOfChildren name = names . childrenOf name
user_675790
Related