如何记住Haskell中二进制搜索树的根？
我对函数式编程很陌生。
我面临的挑战是关于在Haskell中二进制搜索树是如何工作的心理地图。
- 在其他程序(C，C++)中，我们有一个叫做根的东西。我们把它存储在一个变量中。我们将元素插入其中并进行平衡等等。
- 这个程序需要休息一下，做其他事情(可能是进程用户输入，创建线程)，然后计算出它需要在已经创建的树中插入一个新元素。它知道根(存储为变量)，并使用根和新值调用插入函数。
到目前为止其他语言都很好。但是我在Haskell怎么模仿这样的东西呢？
- 我看到一些函数实现了将列表转换为二叉树、插入值等等。一切都很好
- 我希望这个功能成为一个更大的程序的一部分，所以我需要知道根是什么，以便我可以使用它再次插入它。这有可能吗？如果是的话，怎么做？
注意:难道根本不可能因为数据结构是不可变的，因此我们根本不能使用根来插入某些内容。在这种情况下，Haskell是如何处理上述情况的？
回答 4
Stack Overflow用户
发布于 2022-01-05 23:36:51
这一切都是以同样的方式发生的，只是我们没有改变现有的树变量，而是从它派生出一棵新树，并记住新树而不是旧树。
例如，您所描述的流程的C++草图可能如下所示：
int main(void) {
Tree<string> root;
while (true) {
string next;
cin >> next;
if (next == "quit") exit(0);
root.insert(next);
doSomethingWith(root);
}
}一个变量，一个读操作，和一个变异步骤的循环。在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))Stack Overflow用户
发布于 2022-01-05 23:48:11
用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 []Stack Overflow用户
发布于 2022-01-06 00:03:32
“做平衡”。“它知道根”不知道。在重新平衡后，根是新的。函数balance_bst必须返回新的根。
在Haskell也是如此，但insert_bst也是如此。它也将返回新的根，您将从这一点开始使用这个新根。
即使新根的值是相同的，在Haskell中也是一个新根，因为它的一个子根已经改变了。
参见''How to‘think“’‘这里。
https://stackoverflow.com/questions/70603384
复制
相似问题
Haskell中二进制搜索树的实现
Python中二进制搜索树的深度
haskell二进制搜索树
python中二进制搜索树的总深度
C++中二进制搜索树的实现
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
