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?

CodePudding user response：

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))

CodePudding user response：

Writing an example with a BST would take too much time but I give you an analogous example using lists.

Let's invent a updateListN which updates the n-th element in a list.

updateListN :: Int -> a -> [a] -> [a]
updateListN i n l = take (i - 1) l    n : drop i l

Now for our program:

list = [1,2,3,4,5,6,7,8,9,10] -- The big data structure we might want to use multiple times

main = do
  -- only for shows
  print $ updateListN 3 30 list -- [1,2,30,4,5,6,7,8,9,10]
  print $ updateListN 8 80 list -- [1,2,3,4,5,6,7,80,9,10]
  -- now some illustrative complicated processing
  let list' = foldr (\i l -> updateListN i (i*10) l) list list
  -- list' = [10,20,30,40,50,60,70,80,90,100]
  -- Our crazily complicated illustrative algorithm still needs `list`
  print $ zipWith (-) list' list
  -- [9,18,27,36,45,54,63,72,81,90]

See how we "updated" list but it was still available? Most data structures in Haskell are persistent, so updates are non-destructive. As long as we have a reference of the old data around we can use it.

As for your comment:

My program is trying the following a) Convert a list to a Binary Search Tree b) do some I/O operation c) Ask for a user input to insert a new value in the created Binary Search Tree d) Insert it into the already created list. This is what the program intends to do. Not sure how to get this done in Haskell (or) is am i stuck in the old mindset. Any ideas/hints welcome.

We can sketch a program:

data BST
readInt :: IO Int; readInt = undefined
toBST :: [Int] -> BST; toBST = undefined
printBST :: BST -> IO (); printBST = undefined

loop :: [Int] -> IO ()
loop list = do
  int <- readInt
  let newList = int : list
  let bst = toBST newList
  printBST bst
  loop newList

main = loop []

CodePudding user response：

"do balancing" ... "It knows the root" nope. After re-balancing the root is new. The function balance_bst must return the new root.

Same in Haskell, but also with insert_bst. It too will return the new root, and you will use that new root from that point forward.

Even if the new root's value is the same, in Haskell it's a new root, since one of its children has changed.

See ''How to "think functional"'' here.