variables - 如果你不能在 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
    -- ...

使用一元辅助函数，这可以简化为

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

如果要更新某个位置的值，则需要更高级的数据结构，例如 zipper ，但仍然纯粹是功能性的!