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

Question

我是函数式编程的新手。
我面临的挑战是关于二叉搜索树如何在 Haskell 中工作的思维导图。

在其他程序(C、C++)中，我们有一个叫做 root 的东西。我们将它存储在一个变量中。我们将元素插入其中并进行平衡等。

程序暂停做其他事情(可能是处理用户输入，创建线程)，然后确定它需要在 中插入一个新元素。已创建树 .它知道根(存储为变量)并使用根和新值调用插入函数。

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

我看到了实现将列表转换为二叉树、插入值等的函数。这一切都很好

我希望此功能成为更大程序的一部分，因此我需要知道根是什么，以便我可以使用它再次插入它。那可能吗？如果有怎么办？

注意:这根本不可能，因为数据结构是不可变的，所以我们根本不能使用根来插入一些东西。在这种情况下，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))