title: Update a tree based on index Haskell
body: <p>I have trees of the form:</p>
  
  <pre><code>data Tree a = Leaf | Node (Tree a) a (Tree a)
  </code></pre>
  
  <p>I created a function to look up the value of a node in a tree based on an in-order, left-to-right traversal.</p>
  
  <pre><code>getElem :: Tree a -&gt; Int -&gt; Maybe a
  getElem Leaf _ = Nothing
  getElem (Node l x r) n
      | s == n     = Just x
      | n &lt; s      = getElem l n 
      | otherwise  = getElem r (n - s - 1)
    where
      s = size l
  </code></pre>
  
  <p>I now want to write a method to be able to update a tree. It should be able to take in a tree, an index and a value and update the node at that index with the value. So far I have:</p>
  
  <pre><code>update :: Tree a -&gt; Int -&gt; a -&gt; Tree a
  update Leaf _ _ = Leaf
  update (Node l x r) index c
      | s == index      = (Node l c r)
      | index &lt; s       = update l index c
      | otherwise       = update r (index - s - 1) c
    where
      s = size l
  </code></pre>
  
  <p>This function is able to add but it obviously returns just the added node itself. I want to be able to return the entire tree post the 'update' with the new node or return the tree as is if the index is out of bounds.</p>
  
  <p>Could anybody give me some idea how to proceed with this?</p>
  
  <p>Edit 1:</p>
  
  <p>Okay, I understand that I am basically discarding the remainder of my tree when recursing here. So:</p>
  
  <pre><code>update :: Tree a -&gt; Int -&gt; a -&gt; Tree a
  update Leaf _ _ = Leaf
  update (Node l x r) index c
      | s == index      = (Node l c r)
      | index &lt; s       = update (Node l2 x r) index c
      | otherwise       = update (Node l x r2) (index - s - 1) c
    where
      s = size l
      l2 = l
      r2 = r
  </code></pre>
  
  <p>Edit 2(Silly me!):</p>
  
  <pre><code>update :: Tree a -&gt; Int -&gt; a -&gt; Tree a
  update Leaf _ _ = Leaf
  update (Node l x r) index c
      | s == index      = (Node l c r)
      | index &lt; s       = (Node (upd l index c) x r)
      | otherwise       = (Node l x (upd r (index - s - 1) c)) 
    where
      s = size l
  </code></pre>
  
  <p>It took me a bit to wrap my head around it. Thank you for the comments!</p>