我如何记住Haskell中二叉搜索树的根

Question

我是函数式编程的新手。

我面临的挑战是关于二叉搜索树在 Haskell 中如何工作的思维导图。

1. 在其他程序（C、C++）中，我们有一个称为 root 的东西。我们将其存储在一个变量中。我们将元素插入其中并进行平衡等。
2. 程序会休息一下，做其他事情（可能是处理用户输入、创建线程），然后发现需要在已创建的树中插入一个新元素。它知道根（存储为变量）并使用根和新值调用插入函数。

到目前为止，其他语言的表现都很好。但是我如何在 Haskell 中模仿这样的事情，即

3. 我看到函数实现将列表转换为二叉树、插入值等。这都很好
4. 我希望此功能成为更大程序的一部分，因此我需要知道根是什么，以便我可以使用它再次插入它。那可能吗？如果是这样怎么办？

注意：这是不是根本不可能，因为数据结构是不可变的，所以我们根本不能使用根来插入东西。在这种情况下，Haskell 中如何处理上述情况？

Answer 1

实际上，这一切都以相同的方式发生，只不过我们不是改变现有的树变量，而是从中派生出一棵新树，并记住新树而不是旧树。

例如，您描述的过程的 C++ 草图可能如下所示：

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

一个变量、一个读取操作以及带有 mutate 步骤的循环。在 haskell 中，我们做同样的事情，但是使用递归进行循环和递归变量而不是改变局部变量。

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

如果您需要doSomethingWith能够“变异”t并读取它，您可以将程序提升到状态：

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

Answer 2

用 BST 编写一个例子会花费太多时间，但我给你一个使用列表的类似例子。

让我们发明一个updateListN更新列表中第 n 个元素的方法。

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

现在我们的程序：

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]

看看我们如何“更新”列表但它仍然可用？Haskell 中的大多数数据结构都是持久的，因此更新是非破坏性的。只要我们有周围旧数据的参考，我们就可以使用它。

至于你的评论：

我的程序正在尝试以下操作 a) 将列表转换为二叉搜索树 b) 执行一些 I/O 操作 c) 要求用户输入以在创建的二叉搜索树中插入新值 d) 将其插入到已创建的二叉搜索树中列表。这就是该程序想要做的。不知道如何在 Haskell 中完成这件事（或者）我是否陷入了旧的思维模式。欢迎任何想法/提示。

我们可以画出一个程序：

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 []