Haskell为树增加了价值

Question

我试图创建一个函数,允许我向树添加一个新的值,如果给定路径的值等于ND(没有数据),这是我的第一次尝试.

它会检查值等,但问题是,我希望能够使用新数据打印修改后的树.谁能给我任何指针？我还试过制作第二个函数来检查路径,看它是否可以添加数据,但我只是输掉了如何打印出修改过的树？

Answer 1

正如iuliux指出的那样,你的问题是你正在将你的BTree看作是一个可变的结构.记住haskell中的函数接受参数并返回一个值.就是这样.因此,当您"映射"列表或遍历树时,您的函数需要返回一个新树.

您拥有的代码是遍历递归树,只返回最后一个叶子.想象一下,现在道路尽头的树叶将永远存在ND.这就是你想要的:

add :: a -> Path -> Btree a -> Btree a
add da xs ND = Data da
add _  [] _  = error "You should make sure this doesn't happen or handle it"
add da (x:xs) (Branch st st2) = 
               case x of 
                    L -> Branch (add da xs st) st2
                    R -> Branch st (add da xs st2)

请注意,在您的原始代码Branch中,如果您需要执行的操作是丢弃" 模式匹配",请将其丢弃.

现在,关于处理你到达的叶子的情况的问题,它不是ND构造函数:

这种类型的问题在函数式编程中很常见.当最终结果取决于远在树下的叶子时,如何"随时"返回递归数据结构？

最棘手案例的一个解决方案是Zipper,它是一种数据结构,可让您随意向上和向下移动.对于你的情况,这将是矫枉过正.

我建议你将功能改为以下内容:

add :: a -> Path -> Btree a -> Maybe (Btree a)

这意味着你必须在每个级别返回一个Maybe (Btree a).然后在递归调用中使用Functor实例Maybe.注意:

fmap (+1) (Just 2) == Just 3
fmap (+1) (Nothing) == Nothing

你应该试着自己解决这个问题!