Set the value of a node in a binary tree

Question

I have this algebraic data type for representing binary trees:

data Tree a = Empty | Node a (Tree a) (Tree a)
  deriving (Show, Eq)

Also, I have this simple type:

data Step = StepL | StepR
  deriving (Show, Eq)

Also, I need to define a function that:

1. takes a path of type [Step],
2. a value to set. The idea is that we start from the root, and follow the "directions" in [Step] in order to get to the target node.

If the path does not "fall off" the path, we reset the target value to the desired value. (Note: We rebuild the entire tree.) If, however, the path fall off, we return the input tree intact.

My best attempt:

-- path -> value -> current node -> original root -> new node
setHelper :: [Step] -> a -> Tree a -> Tree a -> Tree a 
setHelper [] value (Node _ l r) root = Node value l r
setHelper [StepL] value (Node _ Empty Empty) root = root
setHelper [StepR] value (Node _ Empty Empty) root = root
setHelper [StepL] value (Node nodeValue l Empty) root = setHelper [] value l root
setHelper [StepR] value (Node nodeValue Empty r) root = setHelper [] value r root
setHelper [StepL] value (Node nodeValue Empty _) root = root
setHelper [StepR] value (Node nodeValue _ Empty) root = root
setHelper [StepL] value (Node _ l r) root = setHelper [] value l root
setHelper [StepR] value (Node _ l r) root = setHelper [] value r root
setHelper (StepL:steps) value (Node _ l r) root = setHelper steps value l root 
setHelper (StepR:steps) value (Node _ l r) root = setHelper steps value r root

set :: [Step] -> a -> Tree a -> Tree a
set steps value root = setHelper steps value root root

Now, when I:

print (set [] 1 (Node 0 Empty Empty))
print (set [StepL, StepL] 1 (Node 0 (Node 0 (Node 0 Empty Empty) (Node 0 Empty Empty)) (Node 0 Empty Empty)))
print (set [StepL, StepR] 1 (Node 0 Empty Empty))

I get:

Node 1 Empty Empty
Node 1 Empty Emtpy
*** Exception: Main.hs: ... Non-exhaustive patterns in function setHelper

As you can see, my implementation is both not correct and buggy.

Q: How to fix the both issues?

Answer 1

The problem is none of your clauses match setHelper [StepR] 0 Empty root. If you enable the compiler warnings (for example ghc -Wall ...) it will tell you so, too:

tree.hs:20:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘setHelper’:
        Patterns not matched:
            [] _ Empty Empty
            [] _ Empty (Node _ _ _)
            (StepL:_:_) _ Empty Empty
            (StepL:_:_) _ Empty (Node _ _ _)
            ...

You probably just want to convert these:

setHelper [StepL] value (Node _ Empty Empty) root = root
setHelper [StepR] value (Node _ Empty Empty) root = root
setHelper [StepL] value (Node nodeValue l Empty) root = setHelper [] value l root
setHelper [StepR] value (Node nodeValue Empty r) root = setHelper [] value r root
setHelper [StepL] value (Node nodeValue Empty _) root = root
setHelper [StepR] value (Node nodeValue _ Empty) root = root
setHelper [StepL] value (Node _ l r) root = setHelper [] value l root
setHelper [StepR] value (Node _ l r) root = setHelper [] value r root

into the same form as the last 2 clauses ie [StepX] → (StepX:steps) etc.

There is also some redundant clauses for example

setHelper [StepL] value (Node _ Empty Empty) root = root
setHelper [StepL] value (Node nodeValue Empty _) root = root

both match with setHelper [StepL] 1 (Node 1 Empty Empty) Empty and do the exact same thing.

---

Now for the buggyness part: You've built yourself up quite a lot of (mostly redundant) clauses so let's step back and think about this problem. When we call set what are the cases where we know we're finished (aka base cases), there is nothing left to do, I come up with the following two:

1. We've walked off the path and landed on an Empty

   set steps value Empty = Empty
   

   in this case we just return the same thing as we want to change nothing in the tree. We don't need to return root as anything before us can be (and should be) handled by a prior invocation of set (i.e. the recursive call)

2. We've reached the end of our journey

   set [] value (Node _ l r) = Node value l r
   

   Here we just return a new node with the old subtrees as our children, no need to rebuild these as they'll stay the same. Again we don't care for anything that happened before us, the recursive cases will handle these.

Now that the base cases are properly handled we can look at the recursive steps:

1. We walk left

   set (StepL:steps) value (Node v l r) = Node v (set steps value l) r
   

   We don't have to check for l == Empty our base case will handle that, but what we have to do is put the newly generated case of our recursive call in place of the old l.
2. We walk right, but that's just the same with r instead of l so the implementation is left to the reader.

And with those 4 clauses the set function is total and produces the new tree.

Note especially:

• We don't have to match on [StepL] (a single step) as the combination of our recursive case (StepL:steps) with the [] base case will handle that for us.
• We don't need to string along root as we'll just always build up a new tree walking along the path.
• And since we don't need root in every invocation we also don't need the set <-> setHelper pair to simplify the invocation of set
• Base cases rarely need to match on an non empty list like your [StepX] matches. Usually a recursive (x:xs) and a [] will do the job just fine in combination.
• Sometimes it's not clear from the beginning what the base cases are, it's fine to pretend you have them implemented and start with the recursive case, just make sure to implement them eventually and put them first as clauses are checked top to bottom.

Answer 2

There are essentially two problems: you define two many cases. There are probably at most six cases: for the first the list can be empty [], start with StepL or StepR, so three cases. For the second value it can be Empty or a Node … …, so three cases for the first pattern, and two for the second means a total of six cases, approximately. Yes there are cases where you have to look deeper into a value than only the outer data constructor, but that actually happens not that much, so typically you can start with "shallow" patterns.

A second problem is, in Haskell everything is immutable. You thus do not change the value of a node, you construct a new Tree, where you can reuse parts of the old tree, and with a different node for the location we want to reset. Therefore passing the root and returning the root is strange as well.

With that in mind, we thus can design a function that looks like:

setHelper :: [Step] -> a -> Tree a -> Tree a
-- end of path, empty, we fall off the path
setHelper [] _ Empty = ...
-- end of path, node, replace value
setHelper [] v' (Node _ l r) = ...
-- turn left: construct new Node with left subtree modified
setHelper (StepL:steps) v' (Node v l r) = ...
-- turn right: construct new Node with right subtree modified
setHelper (StepR:steps) v' (Node v l r) = ...
-- we fall of the tree, just return the current node
setHelper (_:_) _ Empty = ...

and that should be sufficient: by filling the ... parts.