如果您无法在Haskell中更改变量的值,那么如何创建数据结构？

Question

根据标题.

我有以下代码创建二叉搜索树,但如果我想用用户输入动态创建和更改,如果我不能在haskell中更改变量的值,我该怎么做？!？

find :: (Ord a) => Node a -> a -> Bool
find (Node val left right) s
    | s == val      = True
    | s < val       = find left s
    | s > val       = find right s

find Empty s = False

data Node a = Node a (Node a) (Node a)
              | Empty

myTree = Node "m"   (Node "a" Empty Empty)
                    (Node "z" Empty Empty)

提前致谢!

Answer 1

纯函数数据结构背后的想法是计算新值而不是更改它们并在参数中递归(递归)而不是全局存储它们.

所以给出了一个功能

insert :: Ord a => Node a -> a -> Node a

你的程序可能看起来像这样

-- Let the user enter k values that are stored in a tree structure
addTreeItems :: Int -> Node Int -> IO (Node Int)
addTreeItems 0 tree = return tree
addTreeItems k tree = do
    putStr "Enter new item: "
    item <- readLn
    addTreeItems (k - 1) (insert tree item) -- Recursively pass the tree

main = do
    tree <- addTreeItems 10 Empty
    -- ...

使用monadic辅助函数,可以将其简化为类似的东西

(foldl insert Empty) `liftM` (sequence $ replicate k (putStr "Enter new item: " >> readLn))

如果你想更新某个位置的值,你需要更高级的数据结构,比如拉链,但仍然是纯粹的功能!

Answer 2

达里奥给出了一个很好的直接答案.如果你想要更深入的信息,那就是Chris Okasaki 的纯功能数据结构,这是一本关于这个主题的完整书籍.我自己买了它,但遗憾的是,我没有时间试验这些想法.