How do I remember the root of a binary search tree in Haskell

Question

I am new to Functional programming.

The challenge I have is regarding the mental map of how a binary search tree works in Haskell.

1. In other programs (C,C++) we have something called root. We store it in a variable. We insert elements into it and do balancing etc..
2. The program takes a break does other things (may be process user inputs, create threads) and then figures out it needs to insert a new element in the already created tree. It knows the root (stored as a variable) and invokes the insert function with the root and the new value.

So far so good in other languages. But how do I mimic such a thing in Haskell, i.e.

3. I see functions implementing converting a list to a Binary Tree, inserting a value etc.. That's all good
4. I want this functionality to be part of a bigger program and so i need to know what the root is so that i can use it to insert it again. Is that possible? If so how?

Note: Is it not possible at all because data structures are immutable and so we cannot use the root at all to insert something. in such a case how is the above situation handled in Haskell?

Answer 1

It all happens in the same way, really, except that instead of mutating the existing tree variable we derive a new tree from it and remember that new tree instead of the old one.

For example, a sketch in C++ of the process you describe might look like:

int main(void) {
  Tree<string> root;
  while (true) {
    string next;
    cin >> next;
    if (next == "quit") exit(0);
    root.insert(next);
    doSomethingWith(root);
  }
}

A variable, a read action, and loop with a mutate step. In haskell, we do the same thing, but using recursion for looping and a recursion variable instead of mutating a local.

main = loop Empty
  where loop t = do
    next <- getLine
    when (next /= "quit") $ do
      let t' = insert next t
      doSomethingWith t'
      loop t'

If you need doSomethingWith to be able to "mutate" t as well as read it, you can lift your program into State:

main = loop Empty
  where loop t = do
    next <- getLine
    when (next /= "quit") $ do
      loop (execState doSomethingWith (insert next t))