我是函式式編程的新手。
我面臨的挑戰是關于二叉搜索樹如何在 Haskell 中作業的思維導圖。
- 在其他程式（C、C ）中，我們有一個叫做 root 的東西。我們將它存盤在一個變數中。我們將元素插入其中并進行平衡等。
- 程式暫停做其他事情（可能是處理用戶輸入，創建執行緒），然后確定它需要在已經創建的樹中插入一個新元素。它知道根（存盤為變數）并使用根和新值呼叫插入函式。
到目前為止，其他語言都很好。但是我如何在 Haskell 中模仿這樣的事情，即
- 我看到實作將串列轉換為二叉樹、插入值等的函式。這一切都很好
- 我希望此功能成為更大程式的一部分，因此我需要知道根是什么，以便我可以使用它再次插入它。那可能嗎？如果是這樣怎么辦？
注意：這根本不可能，因為資料結構是不可變的，所以我們根本不能使用根來插入一些東西。在這種情況下，Haskell 中如何處理上述情況？
uj5u.com熱心網友回復：
實際上，這一切都以相同的方式發生，除了我們沒有改變現有的樹變數，而是從中派生一棵新樹，并記住那棵新樹而不是舊樹。
例如，您描述的程序的 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))
uj5u.com熱心網友回復：
用 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 []
uj5u.com熱心網友回復：
“做平衡”......“它知道根本”不。重新平衡后根是新的。該函式balance_bst必須回傳新的根。
在 Haskell 中也是如此，但在insert_bst. 它也將回傳新的根，你將使用的是新的根，從該點向前。
即使新根的值相同，在 Haskell 中它也是一個新根，因為它的一個子節點已經改變。
請參閱此處的“如何“思考功能性” ” 。
uj5u.com熱心網友回復：
即使在 C （或其他命令式語言）中，使用單個全域變數來保存二叉搜索樹的根通常也被認為是一個糟糕的主意。
相反，需要訪問樹的代碼通常應該在它操作的特定樹上引數化。這是一種花哨的說法：它應該是一個將樹作為引數的函式/方法/程序。
因此，如果您這樣做，那么不需要太多想象力就可以弄清楚幾個不同的代碼部分（或一個部分，在幾種情況下）如何訪問不可變樹的不同版本。而不是將相同的樹傳遞給這些函式中的每一個（在兩者之間進行修改），您只需每次傳遞不同的樹。
想象一下你的代碼需要做什么來“修改”一棵不可變的樹，只需要多做一點作業。顯然，您不會通過直接改變樹來生成新版本的樹，而是會生成一個新值（可能通過呼叫為您實作樹的類上的方法，但如有必要，可以自己手動組裝新節點），然后你將回傳它以便你的呼叫者可以將它傳遞給它 - 通過將它回傳給它自己的呼叫者，通過將它提供給另一個函式，或者甚至再次呼叫你。
綜上所述，您可以讓您的整個程式操縱（連續版本）這棵二叉樹，而無需將其存盤在“the”樹的全域變數中。早期函式（可能是 even main）創建樹的第一個版本，將其傳遞給第一個使用它的東西，取回樹的新版本并將其傳遞給下一個用戶，依此類推。樹的每個用戶都可以根據需要呼叫其他子函式，在回傳到頂層之前，可能會在內部生成許多新版本的樹。
請注意，我實際上并沒有在這里描述 Haskell 的任何特殊功能。您幾乎可以使用任何編程語言（包括 C ）完成所有這些作業。這就是當人們說學習其他型別的編程使他們成為更好的程式員時的意思，即使他們使用他們已經知道的命令式語言。你可以看到你的思維習慣比他們需要的要有限得多；你無法想象如何在你的程式程序中處理一個“改變”的結構，而沒有一個包含變異結構的變數，而實際上這只是 C 為你提供的工具的一小部分接近問題。如果您只能想象這是一種處理方式，那么您將永遠不會注意到其他方式何時會更有幫助。
Haskell也有多種工具可以解決這個問題，這些工具在命令式語言中并不常見，例如（但不限于）：
- 使用
Statemonad 來自動化和隱藏傳遞樹的連續版本的大部分樣板。 - 函式引數允許給一個函式一個未知的“樹消費者”函式，它可以給它一棵樹，??而沒有任何地方既擁有樹又知道它傳遞給哪個函式。
- 惰性求值有時甚至不需要樹的連續版本；如果修改是在您發現需要它們時擴展樹的分支（例如游戲的移動樹），那么即使它是無限的，您也可以預先生成“整棵樹”，并依賴于惰性求值將生成樹的作業量限制為您需要查看的數量。
- Haskell實際上確實有可變變數，它只是沒有可以訪問可變變數而不暴露它們可能有副作用的型別的函式。因此，如果您真的想像在 C 中那樣構建您的程式，您可以；它只是不會真正“感覺”你正在撰寫 Haskell，不會幫助你正確學習 Haskell，也不會讓你從 Haskell 型別系統的許多有用特性中受益。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/405247.html
標籤：
上一篇：在C中搜索二維陣列會出錯
下一篇：來自命令的Makefile變數值