哈斯克爾插入特定的樹

-1

我有以下問題與我在哈克斯克樹的實現。我有正確的數據類型，我的插入和搜索方法工作。但是，當涉及到測試時，我相當有限。例如，如果我在代碼中聲明一棵樹，例如testtree，並給它一些值，當試圖插入testree時，它實際上從不會更新testree。請允許我解釋一下。如果我在ghci窗口insert 5 testtree中聲明，它會返回一個新的樹，它是testree的所在，並且將5添加到正確的位置。快樂的時光。如果我嘗試將另一個元素添加到testree中，它會返回原始測試用例添加的新元素的內容。 5消失了。所以問題是我不能改變testree的原始實例，這是一個痛苦的屁股。測試我的插入方法包括創建許多樹，其中包括爲它們添加元素的所有可能性。如果我只能有一棵樹，我可以繼續添加它會更方便。任何幫助將非常感激！繼承人是一個突出顯示我的問題的示例，它是一個我正在實現的2-3-4樹，爲了突出顯示問題，我從中取出了很多代碼。哈斯克爾插入特定的樹

data Tree t = Empty 
       | Root1 t (Tree t)(Tree t) 
       | Root2 t t (Tree t)(Tree t)(Tree t) 
       deriving (Eq, Ord, Show) 

leaf1 x = Root1 x (Empty) (Empty) 
leaf2 x y = Root2 x y (Empty) (Empty) (Empty) 

insert :: Ord t => t -> Tree t -> Tree t 
insert t Empty = leaf1 t 
insert t (Root1 a Empty Empty) 
      | t <= a = leaf2 t a 
      | otherwise = leaf2 a t 

insert t (Root1 a left right) 
      | t <= a = Root1 a (insert t(left)) (right) 
      | otherwise = Root1 a (left) (insert t(right)) 

testtree = Root1 5 (Root1 3 (Empty) (Empty)) (Root1 7 (Empty) (Empty))

來源

2014-12-06 mcgovec9

歡迎來到Stack Overflow。向我們展示一些代碼... – Jubobs 2014-12-06 19:10:04

Haskell值是不可變的。當您定義testtree = ...時，您無法更改testtree的值。

相反，你必須做這樣的事情：

tree1 = insert 5 testtree 
tree2 = insert 6 tree1 
tree3 = insert 7 tree2 
...

請注意，如果你嘗試：

testtree = insert 5 testtree

你只是進入一個無限循環作爲testtree在RHS指正在定義相同的testtree。

來源

2014-12-06 20:23:57 ErikR

歡迎來到持久數據結構的奇妙世界。持久數據結構的基本定義特徵是所有更新都是非破壞性的。您無法更改數據結構，只能將其用作新數據結構的基礎。

事實證明，在代碼維護，並行代碼執行和併發代碼的正確性方面具有巨大的優勢。這是一件好事。

來源

2014-12-06 20:21:35 Carl

哈斯克爾插入特定的樹

回答

相關問題