我有一个定义为的搜索树:
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 :: (Ord a) => (b -> a -> b -> b) -> b -> Stree a -> b
我不完全明白发生了什么,也不知道如何做到这一点。
最佳答案
您希望您的 map 将一个函数应用于您的树携带的任何标签。这意味着任何 a
的出现都将更改为 b
的出现,使用作为转换函数给出的函数。
为此,您需要弄清楚如何处理 Stree
的每个可能的构造函数。现在,Null
很简单——它首先不依赖于 a
。棘手的是如何处理 Fork
。在 Fork
中,有一个 a
和另外两个 Stree
,因此您需要使用 a -> b
和 Stree a -> Stree b
的函数。对于前者,mapStree
的调用为您提供了一个函数,而对于后者,mapStree f
具有您需要的调用签名(通过部分应用!)。
对于 foldStree
,您有一些累积类型 b
和标签类型 a
,以及一个累积函数,该函数采用 b
类型的两个值和 a
类型的值并生成 b
。这很有帮助,尤其是因为该累积函数反射(reflect)了您在树中任何给定 Fork
处可能拥有的内容:通过递归,您可以假设您拥有左右 Stree
的结果,并且只需要将它们与 a
结合起来中间的值可以提供一个新的 b
值来执行递归。 b
的 foldStree
参数为您提供了足够的标准值,通过获取每个叶子的值来开始整个事情。
因此,您的 foldStree
还需要在可能的构造函数上定义:为 Null
值挑选参数,然后对于 Fork
值,它需要在将所有内容与参数组合函数组合之前递归到两个 Stree
值。
请在评论中澄清这是否足以帮助您解决问题:我(和这里的许多其他人)可以澄清,但希望您学习如何做到这一点,而不是仅仅交给您代码。
关于search - 如何在搜索树上定义 map 和折叠?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3982968/