当前位置：文江博客话题详情

Haskell 为树增加价值

发布于 2024-10-26 10:38:03 字数 156 浏览 4 评论 0原文

我试图创建一个函数，如果给定路径上的值等于 ND （无数据），它允许我向树添加新值，这是我的第一次尝试。

它检查值等，但问题是我希望能够使用新数据打印修改后的树。任何人都可以给我任何指示吗？我还尝试创建第二个函数来检查路径以查看是否可以添加数据，但我只是不知道如何打印出修改后的树？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

哀由 2024-11-02 10:38:03

正如 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)。然后在递归调用中使用 Maybe 的 Functor 实例。注意：

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

您应该尝试自己解决实现问题！

As iuliux points out, your problem is that you are treating your BTree as though it were a mutable structure. Remember functions in haskell take arguments and return a value. That is all. So when you "map over" a list, or traverse a tree your function needs to return a new tree.

The code you have is traversing the recursive tree and only returning the last leaf. Imagine for now that the leaf at the end of the path will always be ND. This is what you want:

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)

Notice how in your original code you discard the Branch you pattern match against, when what you need to do is return it "behind you" as it were.

Now, on to the issue of handling situations where the leaf you arrive it is not a ND constructor:

This type of problem is common in functional programming. How can you return your recursive data structure "as you go" when the final result depends on a leaf far down the tree?

One solution for the trickiest of cases is the Zipper, which is a data structure that lets you go up down and sideways as you please. For your case that would be overkill.

I would suggest you change your function to the following:

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

which means at each level you must return a Maybe (Btree a). Then use the Functor instance of Maybe in your recursive calls. Notice:

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

You should try to puzzle out the implementation for yourself!

回复收藏 0 原文

岁吢 2024-11-02 10:38:03

我不是 Haskell 专家，但函数式编程只适用于函数。所以任何东西都是函数。
现在，您的函数接受一些输入并返回一些内容，而不是修改输入。您必须将返回的树保留在某处，这将是您的新树，其中插入了元素的树

回复收藏 0 原文

攀登最高峰 2024-11-02 10:38:03

我们确实需要查看 Path 和 Error 数据类型来回答您的问题，但您可以使用 IO Monad 打印出您的树：

main :: IO()
main = do let b = Branch ND (Branch (Data 1) (Data 2))
          let b1 = add 10 [L] b --actual call depends on definition of Path
          (putStrLn . show) b1

We really need to see the Path and Error data types to answer your question, but you can print out your trees using the IO Monad:

main :: IO()
main = do let b = Branch ND (Branch (Data 1) (Data 2))
          let b1 = add 10 [L] b --actual call depends on definition of Path
          (putStrLn . show) b1

回复收藏 0 原文

~没有更多了~