如何定义搜索树上的地图和折叠？
我有一个搜索树，其定义为：
data (Ord a) => Stree a = Null | Fork (Stree a) a (Stree a) deriving Show
我必须定义两个函数，mapStree:
mapStree :: (Ord b, Ord a) => (a -> b) -> Stree a -> Stree b
和foldStree:
foldStree :: (Ord a) => (b -> a -> b -> b) -> b -> Stree a -> b
我不完全理解发生了什么，也不知道如何做到这一点。
I have a search tree that's defined as:
data (Ord a) => Stree a = Null | Fork (Stree a) a (Stree a) deriving Show
and I have to define two functions, mapStree:
mapStree :: (Ord b, Ord a) => (a -> b) -> Stree a -> Stree b
and foldStree:
foldStree :: (Ord a) => (b -> a -> b -> b) -> b -> Stree a -> b
I don't fully understand what's going on and don't know how to do this.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您希望地图将函数应用于树所带有的任何标签。这意味着使用作为转换函数给出的函数，将
a的任何出现更改为b的出现。为此，您需要弄清楚如何处理
Stree的每个可能的构造函数。现在，Null很简单——它一开始就不会依赖于a。更棘手的是如何使用Fork。在Fork中，有一个a和另外两个Stree，因此您需要采用a ->; 的函数。 b并采取Stree a ->街b。对于前者，mapStree的调用会为您提供一个函数，对于后者，mapStree f具有您需要的调用签名（通过部分应用！）。对于
foldStree，您有一些累积类型b和标签类型a，以及一个采用两个b< 类型值的累积函数/code> 和a类型的值并生成b。这很有帮助，至少是因为该累积函数反映了树中任何给定Fork处可能拥有的内容：通过递归，您可以假设您从左侧和右侧Stree< 都获得了结果/code>，只需将它们与中间的a值组合起来，即可给出新的b值来进行递归。foldStree的b参数为您提供了足够的标准值，以便通过获取每个叶子的值来开始整个事情。因此，您的
foldStree还需要在可能的构造函数上定义：选择Null值的参数，然后选择Fork的参数值，在使用参数组合函数组合所有内容之前，它需要递归到两个Stree值。请在评论中澄清这是否足以帮助您解决问题：我（和这里的许多其他人）可以澄清，但希望您学习如何做到这一点，而不是仅仅交给您代码。
You want your map to apply a function to any label carried by your tree. This means that any occurrence of
ais to be changed to an occurrence tob, using the function given as a transformation function.To do this, you'll need to figure out what to do with each possible constructor of the
Stree. Now,Nullis easy -- it won't depend onain the first place. Trickier is what to do withFork. InFork, there is onea, and two furtherStrees sitting around, so you need functions that takea -> band that takeStree a -> Stree b. For the former, the invocation ofmapStreegives you a function, and for the latter,mapStree fhas the call signature you need (by partial application!).For
foldStree, you have some accumulation typeband your labeltypea, and an accumulation function that takes two values of typeband a value of typeaand produces ab. This is helpful, not in the least because that accumulation function mirrors what you might have at any givenForkin the tree: by recursion you can assume you have results from both left and rightStree, and it only remains to combine those with theavalue you have in the middle to give a newbvalue to hand up the recursion. Thebparameter tofoldStreeprovides you with enough of a standard value to get the whole thing started by getting a value for each leaf.Thus, your
foldStreewill also need to be defined on the possible constructors: picking out the parameter for aNullvalue, and then for aForkvalue, it needs to recurse into bothStreevalues before combining everything with the parameter combining function.Please clarify in comments whether this helps you enough to deal with the problem: I (and many others here) can clarify, but the hope is for you to learn how to do it rather than to just hand you code.
我强烈推荐本课程中的讲座 5。
I highly recommend Lecture 5 from this course.