Traversing a binary tree in Haskell and return a tree that satisfies a condition

Question

I am trying to traverse a tree in Haskell where the idea is to return a new tree that satisfies a predefined condition. If a node's value x >= a and x < b, then this node should be included in the new tree. I must be able to traverse the entire tree and all branches to make sure that all valid nodes are included.

However, now I am struggling to come up with a solution on how to traverse both left and right branch when the precondition is not met in a node.

For example for a = -5 and b = 0 so that -5 <= x <0 :

Should return -5. So the solution should just discard any node not meeting the precondition, and if the precondition is met, it should add that node to the new tree.

This code is what I got so far.

data Tree = Void | Node Tree Integer Tree 
  deriving (Eq, Show) 

nextTree :: Integer -> Integer -> Tree -> Tree
nextTree _ _ Void = Void
nextTree a b (Node Void x Void) = if x >= a && x < b then Node Void x Void else Void
nextTree a b (Node l x Void) = if x >= a && x < b then Node (nextTree a b l) x Void else nextTree a b l
nextTree a b (Node Void x r) = if x >= a && x < b then Node Void x (nextTree a b r) else nextTree a b r
nextTree a b (Node l x r)  
  |  x >= a && x < b = Node (nextTree a b l) x (nextTree a b r) 
  | not (x >= a && x < b) = undefined
  | otherwise = undefined

It is where undefined is written that I need some way to traverse both left and right branch and then return next subtree to nextTree. I a just do

| not (x >= a && x < b) = nextTree (a b r)

it will only traverse the right branch. I would like to to something like

| not (x >= a && x < b) = nextTree (a b r) && nextTree (a b r)

But I am not sure how to do it in Haskell. Or if it is even possible?

Maybe try something like case (nextTree a1 b1 r1, nextTree a2 b2 r2) of (Void, Void) -> ... ; (Void, Node ...) -> ; ... — chi
– chi, Commented Sep 25, 2022 at 9:21

amalloy · Accepted Answer · 2022-09-25 12:58:26Z

First of all, I would simplify your branching logic. Instead of repeating the keep condition and recursive cases many times, write them once and pattern match on their results. Also, we can avoid repeatedly passing lo and hi up and down the chain if we capture them in a closure:

nextTree :: Integer -> Integer -> Tree -> Tree
nextTree lo hi = go
  where go Void = Void
        go (Node l x r) = case (x >= lo && x < hi, go l, go r) of
          (True, l', r') -> Node l' x r'
          (False, Void, r') -> r'
          (False, l', Void) -> l'
          (False, l', r') -> undefined

This is the same logic as in your question, but with the repetition boiled away so we can see the forest instead of getting bogged down in trees and bools. I've also removed the Node Void x Void case, as it is already covered by your other cases.

Now we can see clearly what remains to be handled: you have two subtrees (already recursively trimmed), but the node that used to be their parent is disappearing. So, what you need is some function that turns two trees into one tree. Of course, you can't always do this while preserving the structure perfectly: at some point you'll have to make some arbitrary decision about where in one of the subtrees to put the original node's value.

Let's call this function graft:

nextTree :: Integer -> Integer -> Tree -> Tree
nextTree lo hi = go
  where go Void = Void
        go (Node l x r) = case (x >= lo && x < hi, go l, go r) of
          (True, l', r') -> Node l' x r'
          (False, Void, r') -> r'
          (False, l', Void) -> l'
          (False, l', r') -> graft l' r'
        graft a Void = a
        graft Void b = b
        graft (Node l x r) n = Node (graft l r) x n

If we find a Void, we drop that tree and return the other one. Otherwise, we have two non-Void trees. We arbitrarily choose to leave the right tree alone, lift the value of the left node to be the new parent node, and then graft the left node's two children together.

I didn't have any particular plan in mind while writing this function. In nextTree, I just removed duplication until I was left with something simple, and the unimplemented case has a clear "hole" in it, where we have two Tree values and need one Tree as a result. So, try writing a function of that type. Again, apply pattern matching: the first two cases are simple, and the last case isn't bad either: once you realize it's all that's left, the only thing you can really do is make a Node, promote x, and call graft recursively. This approach is often called Hole-oriented programming, and is worth trying out.

Collectives™ on Stack Overflow

Traversing a binary tree in Haskell and return a tree that satisfies a condition

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related