Handling starred and non-starred nodes in a tree transformation

Problem:

Starred Nodes:

• Nodes with names ending in "*" are considered "starred."

Requirement:

• Any starred node that is not a direct child of another starred node should become a direct child of the root node.
• Starred nodes that are children of other starred nodes remain in their positions.

Starting from this tree,

Node
  "Root"
  [ Node
      "Alpha"
      [ Node "Beta*" -- A starred node
          [ Node "Gamma" [], -- Unstarred child of a starred node
            Node "Delta*" -- Starred child of another starred node
              [ Node "Epsilon" [] ] -- Unstarred child of "Delta*"
          ],
        Node "Zeta" [] -- Unstarred node
      ],
    Node
      "Theta"
      [ Node "Iota" [],
        Node "Kappa*" [] -- Starred node that does not descend from other starred nodes
      ]
  ]

I would like to produce:

Node
  "Root"
  [ Node
      "Beta*" -- A starred node
      [ Node "Delta*" -- Starred child of another starred node
          [] 
      ],
    Node "Kappa*" [] -- Starred node that does not descend from other starred nodes
  ]

• Is this tree transformation technically possible in Haskell ?
• An as aside, is the concept of "direct child" common in Tree recursion ?

Here's one straightforward answer. The spec is a little unclear about what should happen if the root node has a star (a literal reading says Node "*" [] should result in Node "*" [Node "*" []], which doesn't seem right), so I've fudged it: we'll return the direct children of the new root rather than a single tree with those as direct children. We're doing a recursion with two possible states: either we're the child of a starred node or not. If we're not under a starred node, we return the new direct children of the root. If we're under a starred node, we return the children of the parent and the children of the new root separately.

handleUnstarred :: Tree String -> Forest String
handleUnstarred t@(Node label children)
  | hasStar label = uncurry (++) . handleStarred $ t
  | otherwise = children >>= handleUnstarred

handleStarred :: Tree String -> (Forest String, Forest String)
handleStarred t@(Node label children)
  | hasStar label = ([Node label (rec >>= fst)], rec >>= snd)
  | otherwise = ([], handleUnstarred t)
  where rec = map handleStarred children

That's it; handleUnstarred is the function you want (because the root node is not under a starred node). Try it in ghci:

> handleUnstarred example
[Node {rootLabel = "Beta*", subForest = [Node {rootLabel = "Delta*", subForest = []}]},Node {rootLabel = "Kappa*", subForest = []}]